Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks
Karol Bartkiewicz, Patrycja Tulewicz · 2026
Read Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks by Karol Bartkiewicz, Patrycja Tulewicz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31791.txt.
Introduction
Bartkiewicz and Tulewicz present a compiler pass that chooses how to decompose each Toffoli gate in a quantum circuit. Two-qubit gate errors dominate failure on near-term hardware. The cheapest Toffoli versions, relative-phase and approximate ones, are correct only in context: a leftover phase must cancel later, or a small error must stay tolerable.
Their pass admits a cheap decomposition only when an exact check certifies it for that specific circuit. The check matters: the verifier flags 66 library rewrites from a deployed optimizer as non-equivalent, and greedy substitution silently corrupts 6 of 12 benchmark circuits in their tests. Certified choices still cut two-qubit gates by up to 39.5 percent on one suite, lowering estimated infidelity.
Catalog record
| CREATOR | Karol Bartkiewicz, Patrycja Tulewicz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31791
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks Karol Bartkiewicz, Patrycja Tulewicz Abstract 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. We present, to our knowledge, the first compiler pass that selects a per-Toffoli decomposition to minimize a two-qubit-infidelity error budget . It admits each context-dependent decomposition only when an exact, instance-specific equivalence check certifies its validity in that circuit context , coupling an error-budget objective (absent from count-based selectors such as QContext) with per-instance verification (absent from template-based replacement such as Maslov’s) and closing the gap between context-aware-but-unverified and verified-but-context-free optimizers. The central result is a safety one: pattern-matched relative-phase substitution is silently incorrect . Our verifier flags 66 66 library rewrites of a deployed open optimizer as non-equivalent without a context check, and count-greedy substitution silently corrupts 6 6 of 12 12 benchmark circuits; the verification gate certifies 0 0 errors while still applying every valid decomposition. The two-qubit-gate reduction is real but workload-dependent : up to 39.5 % 39.5\% fewer two-qubit gates and 36.7 % 36.7\% lower infidelity over exact-only on a compute/uncompute-heavy suite ( ≈ 39 % / 35 % {\approx}39\%/35\% versus Qiskit opt-3 and tket), and 15.6 % 15.6\% aggregate on a larger 12 12 – 24 24 -qubit suite, with decision-diagram checking certifying every substitution past the exhaustive-verification limit. At current superconducting and trapped-ion error rates the certified substitutions lower estimated circuit infidelity by 36 36 – 43 % 43\% , and on a quantum state-resetting (synchronizing-word) circuit the pass removes 48.8 % 48.8\% of the native two-qubit gates, every substitution verified. 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. The demand is not confined to textbook arithmetic: emerging primitives such as quantum synchronizing-word / state-resetting protocols [ 2 , 3 ] compile to Toffoli-heavy controlled logic whose two-qubit-gate budget is the binding constraint on whether the experiment fits within the device error budget. Crucially, the cheapest known decompositions are not exact CCX implementations: relative-phase Toffolis [ 4 ] realize the Toffoli permutation up to a diagonal phase on a subset of basis states, and approximate Toffolis [ 5 ] realize it only to within a tolerance. Both are strictly cheaper in two-qubit gates than any exact decomposition, and both are correct only in context —the residual phase must be uncomputed downstream, or the approximation error must stay within tolerance on the states the gate actually sees. The gap. This contextual validity is exactly where existing tooling splits into two non-overlapping camps. Context-aware selectors (notably QContext [ 6 ] ) automatically choose context-dependent Toffoli decompositions, but they optimize gate count , carry no hardware fidelity model, and—decisively—do not verify that the chosen cheap decomposition is valid in its context. Verified optimizers (VOQC [ 7 ] , Quartz [ 8 ] ) prove their rewrites correct, but only as context-free , unconditional equivalences, and they optimize count, not fidelity. Relative-phase replacement in the style of Maslov and of Kuroda & Yamashita [ 4 , 9 ] is template-based: an identity is hand-proven once, then applied wherever it pattern-matches, with no per-instance check that the surrounding circuit actually cancels the phase. The result is a real hazard: a cheap context-dependent decomposition, deployed by structural pattern matching, can be silently incorrect . Our contribution: a soundness layer. 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 per-instance 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 2^{n} inputs—both weaker than whole-unitary approximate compiling [ 5 ] (more decompositions become admissible) and the least-covered sub-claim in the literature. It licenses the relative-phase admissions and an exact-on-reachable control-drop that removes a Toffoli whose control is provably constant on the reachable domain. The same criterion extends, with a proven \epsilon -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. This paper automates and verifies the per-gate selection that, in the decomposition taxonomy of § 3.1 , requires context-dependent admission: we turn the manual taxonomy into an automated, verified, error-budget-driven pass over whole Toffoli networks. Contributions. This work makes four contributions. 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 \epsilon -budget bound for the approximate regime (Corollary 1 ). Third, the reachable-subspace admissibility criterion (§ 4.1 ), the technical centerpiece, which certifies decompositions against the states reachable in context rather than all 2^{n} inputs—demonstrated by an exact-on-reachable 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 Related Work We organize prior art by the three pillars; our wedge is the triple (context-aware selection) \,\times\, (error-budget objective) \,\times\, (per-instance verification), which no prior work combines (Table 1 ). Table 1 : Where this work sits on the three axes. No prior approach combines all three. † template/pattern-based, with no per-instance check; ‡ context-free (unconditional) equivalence only; § whole-unitary fidelity distance, not a per-gate two-qubit-infidelity budget. Approach Context-aware Error-budget obj. Per-instance verified Optimizes QContext [ 6 ] \checkmark \times \times gate count Maslov; Kuroda–Yamashita [ 4 , 9 ] \checkmark^{\dagger} \times \times gate count VOQC [ 7 ] ; Quartz [ 8 ] \times \times