Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks

arXiv:2606.31791 · quant-ph · Submitted 2026-06-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks".

Mira: Here's the gist of the paper. The paper presents a compiler pass that selects per-Toffoli decompositions to minimize hardware two-qubit infidelity error budget while admitting context-dependent decompositions only when a per-instance, context-conditioned equivalence check certifies them.

Kai: Context and Soundness Layer The central contribution is a soundness layer that reframes aggressive Toffoli optimization as a soundness problem and contributes the missing layer—a pass that makes error-budget-driven selection of context-dependent decompositions provably safe per instance The pass rests on three pillars: (i) context analysis that marks, for each Toffoli, which cheaper decompositions are admissible given the surrounding circuit (exact always; relative-phase iff the residual phase is uncomputed downstream; approximate iff within tolerance on the reachable subspace); (ii) a perinstance verification gate that discharges an exact (or bounded-error) equivalence obligation conditioned on the context before any substitution is committed; and (iii) an error-budget objective that selects decompositions to minimize summed two-qubit-gate infidelity under a hardware error model, rather than gate count The technical centerpiece is pillar (i)’s reachable-subspace admissibility: a decomposition need only match the Toffoli on the states that actually reach it in context, not on all 2n inputs—both weaker than whole-unitary approximate compiling

5: (more decompositions become admissible) and the leastcovered sub-claim in the literature How Admissibility is Determined For each Toffoli g, the set A(g) of admissible decompositions is computed based on context analysis The criteria for admissibility depend on the decomposition type: exact decompositions are always admissible, a relative-phase decomposition U˜ = D UCCX is admissible iff its diagonal phase D is unobservable downstream of g within the circuit, and an approximate decomposition with error U˜ − UCCX is admissible iff that error stays within tolerance on the reachable subspace R(g)—the span of states that can reach g’s input given the upstream circuit and initial 0⟩ ancillae—rather than on all 2n inputs The reachable-subspace admissibility criterion (§4.1) is the technical centerpiece, which certifies decompositions against the states reachable in context rather than all 2n inputs—demonstrated by an exact-onreachable control-drop that halves the two-qubit count again on top of relative-phase Error Budget and Selection Strategy The error budget objective selects decompositions to minimize summed two-qubit-gate infidelity under a hardware error model, rather than gate count The greedy selection is optimal in the separable case, where the minimum of a separable sum is attained by minimizing each term independently In the separable regime, the per-gate greedy d⋆g = arg mind∈A(g) I(d) is globally optimal The method confirms that whenever a context-dependent d is admissible it also minimizes the per-gate budget, and for any plausible (p2q, p1q) the greedy reduces to “take the cheapest certified decomposition” Empirical Results and Safety Claims The work demonstrates that pattern-matched relative-phase substitution is silently incorrect, exhibiting 66 non-equivalent library rewrites in a deployed open optimizer The safety ablation shows that count-greedy relative-phase substitution breaks 6 of 12 circuits, whereas the full pass is certified error-free (0/12) The budget objective outperforms count-based selection on infidelity, reaching reductions of 39.5% / -36.7% over exact-only on a compute/uncompute heavy suite Scalability and Workload Dependence The reduction is real but workload-dependent: up to 39.5% fewer two-qubit gates and 36.7% lower infidelity over exact-only on a compute/uncompute heavy suite On a larger, machine-verified suite of 20 reversible-arithmetic and oracle circuits at 12–24 qubits, the verified compute/uncompute-pair reduction over exactonly is 15.6% in two-qubit gates and 11.7% in infidelity across all circuits The crossover for verification time occurs near n ≈ 11–12, where the decision-diagram check stays under 25 ms—a >3000× speedup at the crossover (n ≈ 11–12), and effectively flat in circuit size thereafter The hardware coupling topology is orthogonal: selection consumes only the per-gate two-qubit infidelity, never the device connectivity graph, so the certified decisions are unchanged under any routing and compose with a noise-aware mapper

11: Future Directions Future work includes tighter sound over-approximations of R to push the verification scalability boundary and enlarge the admissible set, certified synthesis of bounded-approximate decompositions to a target ϵ-budget (Corollary 1), extension from CCX to multi-controlled-X (MCX) networks

18: , and coupling the budget selector with noise-aware routing

11: The bounded-approximate regime is inert under current set-based reachability, necessitating an amplitude-aware reachability frontend that propagates amplitude bounds for a genuine budget vs.

Mira: epsilon trade The decision-diagram backend (QCEC

10: ) or ZX normalization

12: can fail to certify an equivalence that holds, but never certify a false one, ensuring Theorem 1 holds regardless of the backend used for discharge Code and Data Availability The optimizer, the exact and scalable equivalence verifiers, the reachable-subspace and phaseobservability admissibility checks, and the complete benchmark and evaluation scripts that reproduce every table and figure are opensource at https://github.com/barkol/toptoffoli The safety ablation and the count-greedy baseline (Figs.

Kai: 2, 3) from the baseline/ablation scripts; the scale and verification-crossover data (Fig.

Paper summary: Kai: So looking at the whole paper, "Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks", the main point is that they've moved beyond just optimizing gate count.

Mira: They introduced a compiler pass that minimizes two qubit infidelity error budget by only admitting context dependent decompositions if they pass a per instance equivalence check.

Lev: It’s about making aggressive optimization sound by coupling an error budget objective with per instance verification, which is what they call the soundness layer in this paper <ref:2606.31791#pg1>.

Kai: The implication is that we can use these cheaper decompositions without worrying about them being silently incorrect because the system proves their validity for that exact circuit context.

Mira: It means we can safely deploy these decompositions to lower the dominant error budget term in physical quantum computing runs, which makes those experiments much more feasible.

Lev: They show that this leads to a reduction of thirty six point four percent to forty three point four percent in estimated circuit infidelity across five different platforms <ref:2606.31791#pg3>.

Kai: The only cost of scaling is missed optimization opportunities, like more fallbacks to exact decompositions, but they claim this never causes a regression in correctness.

Mira: And the hardware coupling topology is orthogonal, so the certified decisions hold true regardless of how you route the circuit later on.

Conclusion: Kai: So, to wrap up this whole thing: this paper is about making sure that when we try to optimize these complex quantum circuits using Toffoli gates, we aren't just chasing the fastest gate count anymore.

Mira: Exactly. They’ve created a method where you only use these cheaper decompositions if you can prove they are safe for that specific part of the circuit context.

Lev: It means they’re linking the error budget directly to a formal soundness check, so we aren't just guessing about which decomposition is better under noise.

Kai: The authors put this called a Soundness Layer on top of aggressive optimization, and they did that by defining admissibility based on what states can actually reach a given gate in the circuit.

Mira: They focus on the reachable subspace, which is important because it means we only need to worry about errors for the states that are actually going to be there when we run the experiment.

Lev: From an engineering standpoint, this sounds like a huge win because it lets us trade gate count for actual error reduction without risking a silent bug in our compiled circuit.

Kai: The authors show that this approach actually works in practice, and they found that using the error budget objective cuts infidelity by about forty percent over just using the cheapest gates.

Mira: That level of certified reduction is significant because it shows that optimizing for physical reality, not just abstract gate count, leads to much more feasible quantum computation.

Lev: It’s also interesting how they show that this selection method is independent of the specific hardware coupling topology or routing you might use later on.

Kai: So, the main thing here is that we can now make these circuit rewrites sound and get real error budget savings guaranteed for physical devices.

Karol Bartkiewicz, Patrycja Tulewicz

Institute of Spintronics and Quantum Information, Adam Mickiewicz University · Poznań Supercomputing and Networking Center, IBCH PAS

quant-ph

Submitted: 2026-06-30

Updated: 2026-10-30

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The paper presents a compiler pass that selects per-Toffoli decompositions to minimize hardware two-qubit infidelity error budget while admitting context-dependent decompositions only when a…

Key concepts

Context Analysis
This step identifies which cheaper Toffoli decompositions are allowed based on the surrounding circuit structure. It checks if a decomposition is exact, if its diagonal phase is unobservable downstream, or if its error remains within tolerance on the states that can actually reach it in context.
Reachable-Subspace Admissibility
This technical check determines admissibility by only verifying a decomposition against the states that can actually reach the Toffoli gate given the upstream circuit. This is weaker than checking all possible inputs and allows for more admissible decompositions, making the optimization more flexible.
Error Budget Objective
Instead of minimizing the total number of gates, this objective selects decompositions that minimize summed two-qubit-gate infidelity under a specific hardware error model. This focuses on reducing physical errors directly, leading to substantial improvements in circuit reliability.

Terminology

Summary

The paper presents a compiler pass that selects per-Toffoli decompositions to minimize hardware two-qubit infidelity error budget while admitting context-dependent decompositions only when a per-instance, context-conditioned equivalence check certifies them. p. 1

Where the paper says it

First, a compiler pass that selects per-Toffoli decompositions to minimize a hardware two-qubit-infidelity error budget—the first to make this objective, rather than gate count, the target for context-dependent Toffoli selection. Second, a per-instance verification gate that admits a relative-phase or reachable-subspace decomposition only after an equivalence obligation conditioned on the surrounding circuit is discharged, making aggressive selection sound, with a soundness theorem (Theorem 1) and a composed ϵ-budget bound for the approximate regime (Corollary 1).

Context and Soundness Layer

The central contribution is a soundness layer that reframes aggressive Toffoli optimization as a soundness problem and contributes the missing layer—a pass that makes error-budget-driven selection of context-dependent decompositions provably safe per instance The pass rests on three pillars: (i) context analysis that marks, for each Toffoli, which cheaper decompositions are admissible given the surrounding circuit (exact always; relative-phase iff the residual phase is uncomputed downstream; approximate iff within tolerance on the reachable subspace); (ii) a perinstance verification gate that discharges an exact (or bounded-error) equivalence obligation conditioned on the context before any substitution is committed; and (iii) an error-budget objective that selects decompositions to minimize summed two-qubit-gate infidelity under a hardware error model, rather than gate count The technical centerpiece is pillar (i)’s reachable-subspace admissibility: a decomposition need only match the Toffoli on the states that actually reach it in context, not on all 2n inputs—both weaker than whole-unitary approximate compiling [5] (more decompositions become admissible) and the leastcovered sub-claim in the literature

How Admissibility is Determined

For each Toffoli g, the set A(g) of admissible decompositions is computed based on context analysis The criteria for admissibility depend on the decomposition type: exact decompositions are always admissible, a relative-phase decomposition U˜ = D UCCX is admissible iff its diagonal phase D is unobservable downstream of g within the circuit, and an approximate decomposition with error U˜ − UCCX is admissible iff that error stays within tolerance on the reachable subspace R(g)—the span of states that can reach g’s input given the upstream circuit and initial 0⟩ ancillae—rather than on all 2n inputs The reachable-subspace admissibility criterion (§4.1) is the technical centerpiece, which certifies decompositions against the states reachable in context rather than all 2n inputs—demonstrated by an exact-onreachable control-drop that halves the two-qubit count again on top of relative-phase

Error Budget and Selection Strategy

The error budget objective selects decompositions to minimize summed two-qubit-gate infidelity under a hardware error model, rather than gate count The greedy selection is optimal in the separable case, where the minimum of a separable sum is attained by minimizing each term independently In the separable regime, the per-gate greedy d⋆g = arg mind∈A(g) I(d) is globally optimal The method confirms that whenever a context-dependent d is admissible it also minimizes the per-gate budget, and for any plausible (p2q, p1q) the greedy reduces to “take the cheapest certified decomposition”

Empirical Results and Safety Claims

The work demonstrates that pattern-matched relative-phase substitution is silently incorrect, exhibiting 66 non-equivalent library rewrites in a deployed open optimizer The safety ablation shows that count-greedy relative-phase substitution breaks 6 of 12 circuits, whereas the full pass is certified error-free (0/12) The budget objective outperforms count-based selection on infidelity, reaching reductions of 39.5% / -36.7% over exact-only on a compute/uncompute heavy suite

Scalability and Workload Dependence

The reduction is real but workload-dependent: up to 39.5% fewer two-qubit gates and 36. p. 0

Where the paper says it

The two-qubit-gate reduction is real but workload-dependent: up to 39. 5% fewer two-qubit gates and 36.

7% lower infidelity over exact-only on a compute/uncompute heavy suite On a larger, machine-verified suite of 20 reversible-arithmetic and oracle circuits at 12–24 qubits, the verified compute/uncompute-pair reduction over exactonly is 15. p. 7
Where the paper says it

We use two suites, both built so that each Toffoli’s structure—whether it sits in a compute/uncompute pair, stays live (its result read out or kept), or is mixed—is known by construction, since that structure is exactly what governs admissibility. The primary suite is the 12 small circuits (≤ 8 qubits) of Table 3, sized for exhaustive per-instance verification; it drives the safety ablation (Fig.

6% in two-qubit gates and 11. p. 0
Where the paper says it

The two-qubit-gate reduction is real but workload-dependent: up to 39. 5% fewer two-qubit gates and 36.

7% in infidelity across all circuits The crossover for verification time occurs near n ≈ 11–12, where the decision-diagram check stays under 25 ms—a >3000× speedup at the crossover (n ≈ 11–12), and effectively flat in circuit size thereafter The hardware coupling topology is orthogonal: selection consumes only the per-gate two-qubit infidelity, never the device connectivity graph, so the certified decisions are unchanged under any routing and compose with a noise-aware mapper [11]

Future Directions

Future work includes tighter sound over-approximations of R to push the verification scalability boundary and enlarge the admissible set, certified synthesis of bounded-approximate decompositions to a target ϵ-budget (Corollary 1), extension from CCX to multi-controlled-X (MCX) networks [18], and coupling the budget selector with noise-aware routing [11] The bounded-approximate regime is inert under current set-based reachability, necessitating an amplitude-aware reachability frontend that propagates amplitude bounds for a genuine budget vs. epsilon trade The decision-diagram backend (QCEC [10]) or ZX normalization [12] can fail to certify an equivalence that holds, but never certify a false one, ensuring Theorem 1 holds regardless of the backend used for discharge

Code and Data Availability

The optimizer, the exact and scalable equivalence verifiers, the reachable-subspace and phaseobservability admissibility checks, and the complete benchmark and evaluation scripts that reproduce every table and figure are opensource at https://github.com/barkol/toptoffoli The safety ablation and the count-greedy baseline (Figs. p. 1

Where the paper says it

1), the technical centerpiece, which certifies decompositions against the states reachable in context rather than all 2 n inputs—demonstrated by an exact-onreachable control-drop that halves the two-qubit count again on top of relative-phase. Fourth, a safety result: pattern-matched relative-phase substitution is silently incorrect—we exhibit 66 non-equivalent library rewrites in a deployed open optimizer and a count-greedy / no-gate / gated ablation in which only the gated pass is certified error-free (§5)—alongside an honest scalability boundary for per-instance verification and a decision-diagram (QCEC) fallback for circuits beyond exhaustive reach.

2, 3) from the baseline/ablation scripts; the scale and verification-crossover data (Fig. p. 7
Where the paper says it

We use two suites, both built so that each Toffoli’s structure—whether it sits in a compute/uncompute pair, stays live (its result read out or kept), or is mixed—is known by construction, since that structure is exactly what governs admissibility. The primary suite is the 12 small circuits (≤ 8 qubits) of Table 3, sized for exhaustive per-instance verification; it drives the safety ablation (Fig.

6) from the decision-diagram evaluation; the noisemodel validation from a Qiskit Aer densitymatrix run; and the state-resetting application (Table 4, Fig. p. 8
Where the paper says it

qubits, four per family—Grover AND-ladder oracles, carry-lookahead (CLA) adders, ripple adders, modular-increment blocks, and array multipliers—that extend the same structures past the exhaustive-verification limit, certified by the decision-diagram backend (Fig. These are standard reversible-arithmetic and oracle constructions, not instances tuned to the method; as a guard against favourable selection we report the non-improving families (0%: array multipliers, modular-increment) as openly as the improving ones, and the state-resetting circuit of §5.

4) from a generator following [3] The scalable equivalence-checking fallback uses MQT QCEC [10]

Conclusion

The framework first rewrites the Toffoli network and then reduces its total count of native two-qubit gates (by up to 39.5% on compute/uncompute heavy workloads), lowering the dominant error-budget term and thereby improving the feasibility of error-budget-limited physical quantumcomputing runs, with every reduction certified sound The pass removes 48. p. 3

Where the paper says it

4 Method The pass takes a Toffoli network and a hardware error model and returns a decomposed circuit annotated with a certified error-budget figure. It has four stages: structural reduction (annihilation of adjacent CCX pairs, fan-out common-subexpression elimination (CSE), and permutation-equivalence simplification), context analysis (§4.

8% of the native two-qubit gates on a state-resetting (synchronizing word) circuit, every substitution verified, bringing an otherwise budget-limited synchronization experiment within reach The two-qubitgate count after selection is device-independent; only the estimated infidelity magnitude moves, with reductions of 36–43% across all five platforms The two-qubit gate count after selection is identical across all five (the substitutions do not depend on the noise rates), and the estimated circuitinfidelity reduction ranges from 36. p. 0
Where the paper says it

At current superconducting and trapped-ion error rates the certified substitutions lower estimated circuit infidelity by 36–43%, and on a quantum stateresetting (synchronizing-word) circuit the pass removes 48. 8% of the native two-qubit gates, every substitution verified.

4% to 43.4%

References

[1] John Preskill. “Quantum Computing in the NISQ era and beyond”. p. 0

Where the paper says it

1 Introduction On near-term (NISQ) hardware the dominant contribution to circuit failure is two-qubit-gate error: entangling-gate infidelities are one to two orders of magnitude worse than single-qubit ones, so the effective fidelity of a compiled circuit is governed by how many—and which— two-qubit gates it executes [1]. The Toffoli (CCX) gate is the workhorse non-Clifford primitive of quantum arithmetic, oracles, and reversible logic, and it admits many decompositions that trade ancillae, depth, and two-qubit-gate count against one another.

p. 0
Where the paper says it

1 Introduction On near-term (NISQ) hardware the dominant contribution to circuit failure is two-qubit-gate error: entangling-gate infidelities are one to two orders of magnitude worse than single-qubit ones, so the effective fidelity of a compiled circuit is governed by how many—and which— two-qubit gates it executes [1]. The Toffoli (CCX) gate is the workhorse non-Clifford primitive of quantum arithmetic, oracles, and reversible logic, and it admits many decompositions that trade ancillae, depth, and two-qubit-gate count against one another.

Quantum 2, 79 (2018)

[4] Dmitri Maslov. “Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization”. p. 5

Where the paper says it

The objective is the error budget, yet on the taxonomy of §3. 1 the admissible cheap gadgets are strictly dominant in the dominant cost term: a relative-phase Toffoli (3 two-qubit gates) or an exact-onreachable control-drop (1 or 0) never increases the two-qubit count.

p. 5
Where the paper says it

The objective is the error budget, yet on the taxonomy of §3. 1 the admissible cheap gadgets are strictly dominant in the dominant cost term: a relative-phase Toffoli (3 two-qubit gates) or an exact-onreachable control-drop (1 or 0) never increases the two-qubit count.

Phys. Rev. A 93, 022311 (2016)

[5] Liam Madden and Andrea Simonetto. “Best approximate quantum compiling problems”. p. 2

Where the paper says it

MQT QCEC [10] is the equivalencechecking backend our gate can call; it is a checker, not a selector. 3 Error-budget / fidelity objectives (pillar iii) Approximate quantum compiling (AQC) [5] is the nearest fidelity-objective rival: it minimizes a fidelity distance to a target unitary, but over the whole unitary, with no notion of circuit context and no verification.

p. 2
Where the paper says it

MQT QCEC [10] is the equivalencechecking backend our gate can call; it is a checker, not a selector. 3 Error-budget / fidelity objectives (pillar iii) Approximate quantum compiling (AQC) [5] is the nearest fidelity-objective rival: it minimizes a fidelity distance to a target unitary, but over the whole unitary, with no notion of circuit context and no verification.

ACM Transactions on Quantum Computing3 (2022)

[7] Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. “A verified optimizer for quantum circuits”. p. 8

Where the paper says it

Every emitted circuit is exactly verified (exhaustive for small; QCEC/ZX otherwise). 2 Q1 — the safety ablation We first audit a deployed open Toffoli optimizer with our exact verifier: 66 of its pattern-library simplifications—every relative-phase one-/multiancilla variant applied as a standalone CCX replacement with no context check—are nonequivalent and would silently corrupt circuits.

p. 8
Where the paper says it

Every emitted circuit is exactly verified (exhaustive for small; QCEC/ZX otherwise). 2 Q1 — the safety ablation We first audit a deployed open Toffoli optimizer with our exact verifier: 66 of its pattern-library simplifications—every relative-phase one-/multiancilla variant applied as a standalone CCX replacement with no context check—are nonequivalent and would silently corrupt circuits.

Proc. ACM Program. p. 4
Where the paper says it

The minimum of a separable sum is attained by minimizing each term independently, so the per-gate greedy d ⋆ g = arg mind∈A(g) I(d) is globally optimal, and the pass costs O P g |A(g)| selection time on top of the per-gate verification. No integer program is needed.

p. 4
Where the paper says it

The minimum of a separable sum is attained by minimizing each term independently, so the per-gate greedy d ⋆ g = arg mind∈A(g) I(d) is globally optimal, and the pass costs O P g |A(g)| selection time on top of the per-gate verification. No integer program is needed.

Lang.5 (2021)

[8] Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar, and Zhihao Jia. “Quartz: superoptimization of quantum circuits”. p. 2

Where the paper says it

Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check. 2 Verification of decomposition validity (pillar ii) VOQC [7] and Quartz [8] are the nearest verification rivals: VOQC is Coq-verified rewriting and Quartz is verified cost-search superoptimization, but both prove context-free, unconditional equivalences and minimize count.

p. 2
Where the paper says it

Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check. 2 Verification of decomposition validity (pillar ii) VOQC [7] and Quartz [8] are the nearest verification rivals: VOQC is Coq-verified rewriting and Quartz is verified cost-search superoptimization, but both prove context-free, unconditional equivalences and minimize count.

In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Page 625–640 (2022)

[9] Shohei Kuroda and Shigeru Yamashita. “Optimization of quantum Boolean circuits by relative-phase Toffoli gates”. p. 2

Where the paper says it

Unlike QContext, which selects Toffoli decompositions to expose gate-count savings without checking validity, we (a) optimize a hardware error budget and (b) admit a context-dependent decomposition only after a per-instance equivalence proof. Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check.

p. 2
Where the paper says it

Unlike QContext, which selects Toffoli decompositions to expose gate-count savings without checking validity, we (a) optimize a hardware error budget and (b) admit a context-dependent decomposition only after a per-instance equivalence proof. Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check.

In Reversible Computation (RC 2022). p. 5
Where the paper says it

Two circuits C, C′ on the same qubits with the same measured outputs are observationally equivalent on R, written C ≡R C ′ , iff PrC[ y | x ] = PrC′[ y | x ] for every |x⟩ ∈ R and every output string y. This is the operationally meaningful notion: it is exactly what any experiment or downstream computation can distinguish.

p. 5
Where the paper says it

Two circuits C, C′ on the same qubits with the same measured outputs are observationally equivalent on R, written C ≡R C ′ , iff PrC[ y | x ] = PrC′[ y | x ] for every |x⟩ ∈ R and every output string y. This is the operationally meaningful notion: it is exactly what any experiment or downstream computation can distinguish.

Volume 13354 of Lecture Notes in Computer Science, pages 20–27. p. 3
Where the paper says it

The 1-ancilla relative-phase variant is depth-optimal among exact-upto-phase options [19]. Type 2Q Notes 0 exact 6 standard CCX 1 rel.

p. 3
Where the paper says it

The 1-ancilla relative-phase variant is depth-optimal among exact-upto-phase options [19]. Type 2Q Notes 0 exact 6 standard CCX 1 rel.

Springer (2022)

[10] Lukas Burgholzer and Robert Wille. “Advanced equivalence checking for quantum circuits”. p. 2

Where the paper says it

Unlike QContext, which selects Toffoli decompositions to expose gate-count savings without checking validity, we (a) optimize a hardware error budget and (b) admit a context-dependent decomposition only after a per-instance equivalence proof. Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check.

p. 2
Where the paper says it

Unlike QContext, which selects Toffoli decompositions to expose gate-count savings without checking validity, we (a) optimize a hardware error budget and (b) admit a context-dependent decomposition only after a per-instance equivalence proof. Maslov [4] introduced the relative-phase Toffoli identities and Kuroda & Yamashita [9] systematized their application to Boolean circuits, but as hand-proven templates applied by pattern match, optimizing count, not budget, and without a per-instance validity check.

IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems 40, 1810–1824 (2021)

[15] Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. “Silq: a highlevel quantum language with safe uncomputation and intuitive semantics”. p. 2

Where the paper says it

4 Uncomputation synthesis and safeuncompute languages Unqomp [13], Reqomp [14], Silq [15], and modular uncomputation [16] synthesize where to uncompute (or type-check that uncomputation is safe), correct by construction. They do not select which decomposition to use under a noise budget: their knob is resources or language-level safety, not hardware two-qubit infidelity.

p. 2
Where the paper says it

4 Uncomputation synthesis and safeuncompute languages Unqomp [13], Reqomp [14], Silq [15], and modular uncomputation [16] synthesize where to uncompute (or type-check that uncomputation is safe), correct by construction. They do not select which decomposition to use under a noise budget: their knob is resources or language-level safety, not hardware two-qubit infidelity.

In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Page 286–300 (2020)

[17] Craig Gidney. “Halving the cost of quantum addition”. p. 2

Where the paper says it

2 Relative-phase and approximate Toffolis A relative-phase Toffoli [4] implements a unitary U˜ = D UCCX where D is diagonal in the computational basis and acts non-trivially only on a known subset of basis states. It is exact whenever D is cancelled downstream—in particular when the target is later uncomputed (a structure exploited by Gidney’s addition circuits [17]).

p. 2
Where the paper says it

2 Relative-phase and approximate Toffolis A relative-phase Toffoli [4] implements a unitary U˜ = D UCCX where D is diagonal in the computational basis and acts non-trivially only on a known subset of basis states. It is exact whenever D is cancelled downstream—in particular when the target is later uncomputed (a structure exploited by Gidney’s addition circuits [17]).

Quantum 2, 74 (2018)

[20] A. Paetznick, M. P. da Silva, C. RyanAnderson, J. M. Bello-Rivas, J. P. Campora III, A. p. 1

Where the paper says it

We reframe aggressive Toffoli optimization as a soundness problem and contribute the missing layer—a pass that makes error-budget-driven selection of context-dependent decompositions provably safe per instance. The pass rests on three pillars: (i) context analysis that marks, for each Toffoli, which cheaper decompositions are admissible given the surrounding circuit (exact always; relative-phase iff the residual phase is uncomputed downstream; approximate iff within tolerance on the reachable subspace); (ii) a perinstance verification gate that discharges an exact (or bounded-error) equivalence obligation conditioned on the context before any substitution is committed; and (iii) an error-budget objective that selects decompositions to minimize summed two-qubit-gate infidelity under a hardware error model, rather than gate count.

Chernoguzov, J. M. Dreiling, C Foltz, F Frachon, J P Gaebler, T M Gatterman, L Grans-Samuelsson, D Gresh, D Hayes, N Hewitt, C Holliman, C V Horst, J Johansen, D Lucchetti, Y Matsuoka, M Mills, S A Moses, B Neyenhuis, A Paz, J Pino, P Siegfried, A Sundaram, D Tom, S J Wernli, M Zanner R P Stutz and K M Svore. “Demonstration of logical qubits and repeated error correction with better-than-physical error rates” (2024)

[21] IBM Quantum. “IBM Quantum platform: Backend calibration data (ibm marrakesh, heron r2)”. p. 8

Where the paper says it

Where applicable, Unqomp/Reqomp [13, 14]. Two-qubit-gate infidelity (the headline error budget), two-qubitgate count, depth, and ancilla width, under an IBM/IonQ-like two-qubit error model.

p. 8
Where the paper says it

Where applicable, Unqomp/Reqomp [13, 14]. Two-qubit-gate infidelity (the headline error budget), two-qubitgate count, depth, and ancilla width, under an IBM/IonQ-like two-qubit error model.

https://quantum. p. 0
Where the paper says it

Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks Karol Bartkiewicz1 and Patrycja Tulewicz1,2 1 Institute of Spintronics and Quantum Information, Faculty of Physics and Astronomy, Adam Mickiewicz University, 61-614 Poznań, Poland 2Poznań Supercomputing and Networking Center, IBCH PAS, Poznań, Poland Two-qubit-gate error dominates the failure budget of near-term quantum circuits, so the decomposition chosen for each Toffoli (CCX) gate should minimize hardware two-qubit infidelity, not gate count. The cheapest decompositions— relative-phase and approximate Toffolis— are only correct in context: their residual phase or bounded error must be cancelled or absorbed downstream.

p. 0
Where the paper says it

Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks Karol Bartkiewicz1 and Patrycja Tulewicz1,2 1 Institute of Spintronics and Quantum Information, Faculty of Physics and Astronomy, Adam Mickiewicz University, 61-614 Poznań, Poland 2Poznań Supercomputing and Networking Center, IBCH PAS, Poznań, Poland Two-qubit-gate error dominates the failure budget of near-term quantum circuits, so the decomposition chosen for each Toffoli (CCX) gate should minimize hardware two-qubit infidelity, not gate count. The cheapest decompositions— relative-phase and approximate Toffolis— are only correct in context: their residual phase or bounded error must be cancelled or absorbed downstream.

ibm.co m (2025)

[24] IonQ. “IonQ Aria: Practical performance”. p. 7

Where the paper says it

Should a chosen di fail the gate, the selector falls back to a cheaper certified alternative (in the worst case an exact decomposition, always admissible), so every committed step is admissible and the induction is never broken. Hence the budget objective affects performance but never soundness.

p. 7
Where the paper says it

Should a chosen di fail the gate, the selector falls back to a cheaper certified alternative (in the worst case an exact decomposition, always admissible), so every committed step is admissible and the induction is never broken. Hence the budget objective affects performance but never soundness.

https://www.ionq.com/resources/ion q-aria-practical-performance (2025)

Conclusion and Future Work

The framework first rewrites the Toffoli network and then reduces its total count of native two-qubit gates (by up to 39.5% on compute/uncompute heavy workloads), lowering the dominant error-budget term and thereby improving the feasibility of error-budget-limited physical quantumcomputing runs, with every reduction certified sound Future work includes tighter sound over-approximations of R to push the verification scalability boundary and enlarge the admissible set, certified synthesis of bounded-approximate decompositions to a target ϵ-budget (Corollary 1), extension from CCX to multi-controlled-X (MCX) networks [18], and coupling the budget selector with noise-aware routing [11] The bounded-approximate regime is inert under current set-based reachability, necessitating an amplitude-aware reachability frontend that propagates amplitude bounds for a genuine budget vs. p. 1

Where the paper says it

It licenses the relative-phase admissions and an exact-onreachable control-drop that removes a Toffoli whose control is provably constant on the reachable domain. The same criterion extends, with a proven ϵ-budget bound (Corollary 1), to genuinely approximate Toffolis; we show this approximate regime is sound but, under set-based reachability, activates only with an amplitude-aware front-end, which we leave to future work.

epsilon trade The decision-diagram backend (QCEC [10]) or ZX normalization [12] can fail to certify an equivalence that holds, but never certify a false one, ensuring Theorem 1 holds regardless of which backend is used for discharge The only cost of scaling is missed optimization opportunities (more fallbacks to exact), never a correctness regression The hardware coupling topology is orthogonal: selection consumes only the per-gate two-qubit infidelity, never the device connectivity graph, so the certified decisions are unchanged under any routing and compose with a noise-aware mapper [11] The reduction is thus a function of circuit structure, not a single universal figure; it tracks how many Toffolis sit in cancellable pairs (compute/uncompute pairs) versus those that stay live The mean twoqubit-gate reduction is ≈49% for Grover ANDladder oracles (every CCX paired), ≈28% for carrylookahead adders, ≈6% for ripple adders, and 0% for array multipliers and modular-increment circuits The gain is conditional on the declared domain: under the unrestricted 0/1 n input space a reversible prefix can make every control pair reachable and no drop fires, exactly as soundness demands The selection is correctness-greedy, meaning the same certified substitutions apply at every hardware operating point; only the magnitude of the infidelity reduction tracks the device The two-qubitgate count after selection is device-independent; only the estimated circuitinfidelity magnitude moves, with reductions of 36–43% across all five platforms The two-qubit gate count after selection is identical across all five (the substitutions do not depend on the noise rates), and the estimated circuitinfidelity reduction ranges from 36.4% to 43.4%

[1] John Preskill. “Quantum Computing in the NISQ era and beyond”. Quantum 2, 79 (2018)

[4] Dmitri Maslov. “Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization”. Phys. Rev. A 93, 022311 (2016)

[5] Liam Madden and Andrea Simonetto. “Best approximate quantum compiling problems”. ACM Transactions on Quantum Computing3 (2022)

[7] Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. “A verified optimizer for quantum circuits”. Proc. ACM Program. Lang.5 (2021)

[8] Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken Umut A. Acar and Zhihao Jia. “Quartz: superoptimization of quantum circuits”. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Page 625–640 (2022)

[9] Shohei Kuroda and Shigeru Yamashita. “Optimization of quantum Boolean circuits by relative-phase Toffoli gates”. In Reversible Computation (RC 2022). Volume 13354 of Lecture Notes in Computer Science, pages 20–27. Springer (2022)

[10] Lukas Burgholzer and Robert Wille. “Advanced equivalence checking for quantum circuits”. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems 40, 1810–1824 (2021)

[15] Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. “Silq: a highlevel quantum language with safe uncomputation and intuitive semantics”. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Page 286–300 (2020)

[17] Craig Gidney. “Halving the cost of quantum addition”. Quantum 2, 74 (2018)

[20] A. Paetznick, M. P. da Silva, C RyanAnderson, J M Bello-Rivas, J P Campora III A Chernoguzov J M Dreiling C Foltz F Frachon J P Gaebler T M Gatterman L Grans-Samuelsson D Gresh D Hayes N Hewitt C Holliman C V Horst J Johansen D Lucchetti Y Matsuoka M Mills S A Moses B Neyenhuis A Paz J Pino P Siegfried A Sundaram D Tom S J Wernli M Zanner R P Stutz and K M Svore. “Demonstration of logical qubits and repeated error correction with better-than-physical error rates” (2024)

[21] IBM Quantum. “IBM Quantum platform: Backend calibration data (ibm marrakesh, heron r2)”. https://quantum.ibm.co m (2025)

[24] IonQ. “IonQ Aria: Practical performance”. https://www.ionq.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Context-verified error budget selection for quantum compilers allows AI systems to select Toffoli decompositions that minimize hardware two-qubit infidelity rather than just gate count. This leads to a reduction of up to 39.5% in two-qubit gates and 36.7% lower infidelity over exact-only methods on compute/uncompute heavy suites.

  2. The system can safely employ cheaper decompositions like relative-phase Toffolis only when an exact, instance-specific equivalence check certifies their validity in the circuit context, preventing silent errors where pattern-matched relative-phase substitution is silently incorrect.

  3. AI systems can be improved to perform state resetting protocols more efficiently by utilizing the certified compute/uncompute pairs. This allows for a reduction of 48.8% of native two-qubit gates on synchronizing-word circuits when every substitution is verified, bringing budget-limited synchronization experiments within reach.

  4. The compiler pass can be extended to handle approximate Toffolis by selecting them only when the error stays within tolerance epsilon on the reachable subspace R(g), leading to a sound and bounded-approximate regime where the infidelity saved exceeds the approximation budget spent.

  5. AI systems can incorporate workload-dependent gains by analyzing circuit topology, such as identifying compute/uncompute pairs versus live Toffolis, to prioritize which decompositions yield the largest two-qubit gate reductions based on structure rather than just qubit count.

Abstract

The cheapest Toffoli (CCX) decompositions (relative-phase and control-reduced Toffolis) save two-qubit gates, which dominate the error budget of near-term hardware, but they are correct only in context, since a relative phase is observable only when superposed branches interfere. We propose quantum chip performance tuning (QCPT), a compiler that selects the cheapest decomposition for each Toffoli (stage 1) and admits it only if a per-instance check shows that it equals the exact gate, up to one phase, on every state that can enter it; a whole-circuit certificate gates the output. The output acts as the exact circuit on every valid input, superposed ones included, up to a reported global phase, which per-state checks do not guarantee. Substituting relative-phase Toffolis wherever they fit changes the unitary of six of twelve benchmark circuits used as subroutines, whereas stage 1 changes none and removes 31.0% of the two-qubit gates. A certified resynthesis of classical circuits of up to ten qubits raises the saving to 43.1% on the primary suite and to 57.5% on 20 small RevLib circuits (in-sample). A bound on the compilation error plus the per-gate device error separates what the compiler adds from what a depolarizing two-qubit model of the device adds. In mirror tests on ibm aachen, QCPT (best of four candidates, one of them the Qiskit circuit) returns more often than Qiskit on all nine circuits; in simulation with the calibration that drives its selection, on 29 of 33 circuits and worse on none by more than 0.01. An iterative language-model search with our certificate obtains no fewer gates on any of nine circuits and needs about 45 times longer (one run each). QCPT gives no gain without Toffoli structure. Certified context-dependent selection can thus let near-term devices run larger Toffoli circuits at a given success probability, with a gain that varies by family.

Sources

Related papers