Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks
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 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).Where the paper says it
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 The two-qubit-gate reduction is real but
workload-dependent: up to 39. 5% fewer
two-qubit gates and 36. 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. The two-qubit-gate reduction is real but
workload-dependent: up to 39. 5% fewer
two-qubit gates and 36.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
References
[1] John Preskill. “Quantum Computing in the NISQ era and beyond”. p. 0 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. 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.Where the paper says it
Where the paper says it
[4] Dmitri Maslov. “Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization”. p. 5 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. 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.Where the paper says it
Where the paper says it
[5] Liam Madden and Andrea Simonetto. “Best approximate quantum compiling problems”. p. 2 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. 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.Where the paper says it
Where the paper says it
[7] Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. “A verified optimizer for quantum circuits”. p. 8 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[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 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. 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.Where the paper says it
Where the paper says it
[9] Shohei Kuroda and Shigeru Yamashita. “Optimization of quantum Boolean circuits by relative-phase Toffoli gates”. p. 2 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[10] Lukas Burgholzer and Robert Wille. “Advanced equivalence checking for quantum circuits”. p. 2 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. 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.Where the paper says it
Where the paper says it
[15] Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. “Silq: a highlevel quantum language with safe uncomputation and intuitive semantics”. p. 2 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. 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.Where the paper says it
Where the paper says it
[17] Craig Gidney. “Halving the cost of quantum addition”. p. 2 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]). 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]).Where the paper says it
Where the paper says it
[20] A. Paetznick, M. P. da Silva, C. RyanAnderson, J. M. Bello-Rivas, J. P. Campora III, A. p. 1 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.Where the paper says it
[21] IBM Quantum. “IBM Quantum platform: Backend calibration data (ibm marrakesh, heron r2)”. p. 8 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[24] IonQ. “IonQ Aria: Practical performance”. p. 7 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
[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
-
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.
-
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.
-
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.
-
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. -
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
- Quantum Resetting Protocols Based on Synchronizing Words
- Demonstration of logical qubits and repeated error correction with better-than-physical error rates
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements