⚛️ quantum physics

AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates

This paper introduces AlchemQ v0.5, a proof-of-concept system that ensures the reliability of quantum circuit optimization by coupling an untrusted optimizer with a machine-checkable certification layer that generates self-contained, tamper-evident equivalence certificates for every output, thereby guaranteeing that all optimized circuits are verified for correctness and non-regression.

Original authors: Adam Laabs

Published 2026-09-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Adam Laabs

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet, controlled world of quantum computing, scientists build intricate sequences of instructions to manipulate the smallest units of matter. These instructions, called circuits, are designed to solve problems that are impossible for ordinary computers. However, the path from a theoretical idea to a working quantum program is fraught with danger. To make these circuits run efficiently, software tools must constantly rewrite and simplify them, stripping away unnecessary steps. The problem is that these tools are not perfect. They are complex programs written by humans, and like any software, they contain hidden errors. When a tool silently changes a circuit in a way that breaks its logic, the result is a failed experiment that wastes expensive time and resources on hardware that cannot be easily reset. The scientific community has long needed a way to guarantee that a simplified circuit is truly equivalent to the original, not just a guess that looks right.

A new system called AlchemQ offers a different approach to this problem. Instead of trying to prove that the software tool itself is perfect, the researchers built a system that treats every single output as a suspect until it is proven innocent. They created a process where an optimizer suggests a simplified version of a quantum circuit, and then a separate, independent checker immediately verifies that the new version does exactly the same thing as the old one. If the checker finds even a tiny difference, the suggestion is thrown away. If it passes, the system issues a digital certificate, a self-contained document that proves the two circuits are identical. This certificate is designed to be read by anyone, anywhere, without needing to trust the original software that created it. It is a method of proof-carrying optimization, where the evidence travels with the result.

The researchers tested this system on a large collection of one hundred different quantum circuits, ranging from standard benchmarks to complex, randomly generated examples. They ran the optimizer to find better versions of these circuits and then subjected every single result to the strict verification process. The system worked without fail. Every one of the four hundred optimization attempts completed without error, and every single circuit that was returned came with a valid certificate proving it was equivalent to the original. The system also caught a subtle bug in a widely used library that the researchers were using for the verification itself. In one specific case, the library's standard method for comparing two circuits was amplifying tiny numerical noise, causing it to incorrectly reject a perfectly good optimization. The AlchemQ system detected this failure, identified the source of the error, and corrected it, demonstrating that the verification layer could find problems that the optimization tools themselves would have missed.

Beyond catching errors, the system proved that it could find genuine improvements. On average, the optimized circuits were significantly shorter and used fewer complex gates than the original versions. In one specific test on real quantum hardware from IBM, a circuit that had been optimized by the system was seventy-eight percent shallower and used sixty-five percent fewer two-qubit gates than the unoptimized version. When the researchers ran both the original and the optimized circuits on the physical machine, the results were nearly identical, showing that the drastic simplification did not harm the quality of the output. While the difference in performance was not large enough to be statistically certain with the limited number of runs, the trend pointed clearly toward the optimized circuit being better.

The researchers also explored how different mathematical rules for deciding which circuit was "best" affected the outcome. They tested three distinct methods for weighing the various improvements, such as reducing the number of gates versus reducing the depth of the circuit. Surprisingly, for the standard set of circuits they tested, all three methods produced the exact same final result. The choice of rule only mattered when they tested a specially designed set of difficult, adversarial circuits where the improvements were in direct conflict. In those rare cases, the different rules led to different choices, but the system handled this by ensuring that no matter which rule was used, the final circuit never performed worse than the original in any single category.

This work positions itself not as a replacement for the complex software that drives the optimization, but as a safety net that sits on top of it. The researchers are clear that their optimizer is a simple, experimental tool and that the real power lies in the certificate. By making the proof of correctness a standard part of the output, they allow anyone to verify the work independently. The system is designed to be transparent; the certificate includes all the necessary data, such as the exact version of the software used and the specific mathematical tolerances applied, so that the proof can be reproduced on any computer. The researchers have released the certificate format and the verification software to the public, inviting others to check their work and use the system for their own experiments.

The ultimate goal of this research is to build trust in the quantum software pipeline. By ensuring that every optimized circuit comes with a machine-checkable guarantee of correctness, the system removes the risk of silent failures. It acknowledges that the tools used to build quantum software will always have bugs, but it provides a way to catch those bugs before they cause real damage. The system does not claim to be the final word on quantum optimization, nor does it promise to solve every problem. Instead, it offers a practical, verifiable step forward, proving that it is possible to build a system where the results are always accompanied by their own proof of truth.

Technical Summary: AlchemQ v0.5

Problem Statement

Quantum circuit optimization is a correctness-critical transformation where an optimized circuit replaces the original, often on hardware where a single error invalidates expensive experiments. Current toolchains rely on heuristic or learned rewriting passes (e.g., template matching, ZX-calculus simplification, reinforcement learning) that offer weak evidence of correctness. Production compilers apply long sequences of rewrites without per-result guarantees, and historical bugs in widely used compilers (e.g., Qiskit) have silently corrupted circuits. Formal verification of entire compilers is resource-intensive and often lags behind heuristic state-of-the-art, while existing equivalence checkers typically operate as in-pipeline assertions rather than emitting independent, machine-checkable evidence for individual results. The core problem is the lack of a mechanism to attach self-contained, tamper-evident, and independently verifiable equivalence proofs to every optimized circuit artifact.

Methodology

AlchemQ v0.5 proposes a proof-carrying optimizer architecture that decouples the untrusted optimization engine from a trusted certification layer. The system operates on the principle that the optimizer is untrusted, but the contract (the certificate) is the only trusted component.

System Architecture

The system consists of seven modules, including a beam-search optimizer, a scoring engine using fuzzy t-norms, and a dual-layer certification protocol.

Optimizer: A fixed-seed beam search agent explores rewrite suggestions (gate merging, commutation, inverse cancellation, and PyZX-based extraction). It is structurally incapable of returning an uncertified circuit.
Certification Hard Gate: Every candidate circuit must pass a certification check before entering the beam. The certifier proves equivalence up to global phase using a two-path pipeline:
- ZX-Path: Converts circuits to ZX-diagrams and applies full_reduce and normalize. If the result is a strict identity diagram, equivalence is proven exactly, and the graph scalar yields the global phase.
- Numeric Fallback: For circuits with $\le 6$ qubits where the ZX path is inconclusive, the system computes dense tensors and estimates the relative phase via the optimal Hilbert–Schmidt overlap ( $\phi^* = \arg\langle t_0, t_1 \rangle$ ). It uses a normalized residual metric rather than a single pivot element to avoid noise amplification.
Safety Guarantees: Since v0.4, the agent enforces componentwise non-regression. A candidate is rejected if it worsens any objective (T-count, two-qubit count, or depth) compared to the original circuit, not just the baseline.
Aggregation: The agent evaluates candidates using three fuzzy t-norms (Gödel, Product, Łukasiewicz) to aggregate per-objective scores.

Certification Protocols

AlchemQ introduces two certificate protocols:

Protocol 0.1.1: The legacy format used internally during the search loop.
Protocol 0.2.0: The release format, designed for offline third-party verification. It features:
- Self-contained JSON artifacts with canonical hashes (gate-canon-v1) for tamper detection.
- Tri-state verdicts: certified, rejected, or inconclusive (avoiding silent boolean rounding).
- Versioned schemas for phase notes and canonicalizers to ensure cross-platform reproducibility.
- Structured verification results with reason codes.

Key Contributions

Open Certification Protocol: A versioned, tamper-evident artifact format (Protocol 0.2.0) that allows independent third parties to re-verify equivalence from the embedded circuits alone. It includes a strict migration path from legacy versions.
Reference Certifier and Verifier: An implementation that proves equivalence up to global phase using ZX-calculus full reduction with a numeric tensor fallback. It explicitly records how the global phase was determined (measured, from witness, or not tracked).
Structurally Safe Search Agent: A toy agent that guarantees no uncertified circuits are returned, never scores below a PyZX-based baseline, and never regresses any objective componentwise against the original circuit.
Empirical Validation of Defects: The system successfully identified and diagnosed two critical defects:
- A false negative in a widely used upstream library (PyZX's compare_tensors), where pivot normalization amplified numerical noise by $\sim 2 \times 10^8$ , causing a correct optimization to be rejected.
- Eight certificates that failed only on macOS due to BLAS-dependent raw float rendering in phase notes, resolved by the versioned phase-note schema.

Results

The system was evaluated on a benchmark of 100 circuits (QASMBench, Feynman, and generated Clifford+T instances), resulting in 400 optimizations.

Correctness and Robustness: All 400 optimizations terminated without errors or timeouts. Every returned circuit was certified equivalent. The 2998-test suite passed on both Linux (Python 3.12) and macOS (Python 3.14).
Performance vs. Baseline: The PyZX baseline reduced T-count by 21.4% on average for circuits with non-zero T-count. Under current score semantics, the agent was never worse than the baseline and was strictly better on 9/100 circuits (under Gödel and Product norms).
T-Norm Analysis: On the standard 100-circuit benchmark, all three t-norms returned identical final circuits. Divergence occurred only on 4/38 instances in an adversarial ablation suite, where Pareto fronts offered genuine trade-offs between objectives.
Hardware Experiment: A pilot experiment on IBM Heron r2 (ibm_kingston) showed that the certified-optimized circuit was 78% shallower and had 65% fewer two-qubit gates than the original. While point estimates favored the optimized circuit on all quality metrics (Total Variation Distance, Hellinger Fidelity, Simon constraint rate), the differences were not statistically significant at 1024 shots per arm due to shot noise.

Significance and Claims

The paper positions AlchemQ as a proof-carrying optimizer, distinct from a formally verified compiler.

Artifact-Centric Trust: Unlike verified compilers (e.g., VOQC, CertiQ) that prove the compiler code correct, AlchemQ attaches machine-checkable evidence to individual results. This allows any optimizer (even unverified or learned ones) to sit behind the same trust contract.
Failure Detection: The system's primary value is demonstrated not just in optimization gains, but in its ability to surface defects in the underlying toolchain (PyZX) and in cross-platform reproducibility issues (BLAS dependencies) that standard benchmarks would miss.
Modest Scope: The author explicitly states that AlchemQ is not a competitive replacement for industrial passes, nor is it a learned optimizer. It is a pilot study demonstrating that a small, untrusted optimizer coupled with a rigorous certification layer can produce outputs that are independently verifiable, byte-reproducible, and guaranteed to be non-regressing. The system is designed to be "adversarial toward the optimizer itself," treating the certificate as the sole interface of trust.