pith. sign in

arxiv: 2606.31791 · v1 · pith:56MYRGBHnew · submitted 2026-06-30 · 🪐 quant-ph

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

Karol Bartkiewicz , Patrycja Tulewicz This is my paper

Pith reviewed 2026-07-01 05:28 UTC · model grok-4.3

classification 🪐 quant-ph
keywords Toffoli gatequantum compilationcircuit optimizationerror minimizationequivalence checkingrelative phasedecision diagramstwo-qubit infidelity
0
0 comments X

The pith

A compiler pass safely selects context-dependent Toffoli decompositions to minimize two-qubit infidelity using per-instance verification.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a method for choosing Toffoli gate decompositions in quantum circuits that accounts for the error budget dominated by two-qubit gates. It only permits approximate or relative-phase decompositions when an exact equivalence check confirms they are valid in the specific circuit context. This closes the gap between unverified context-aware optimizers and verified but context-free ones, demonstrating that many common substitutions are unsafe without checks.

Core claim

By coupling an error-budget objective with per-instance decision-diagram verification, the approach certifies that pattern-matched relative-phase substitutions are often incorrect, flags 66 invalid rewrites in a library, prevents corruption in benchmarks, and achieves up to 39.5% fewer two-qubit gates and 36.7% lower infidelity while certifying zero errors.

What carries the argument

The context-verified error-budget-aware decomposition selector for Toffoli networks, which uses decision-diagram equivalence checking to validate each substitution before inclusion in the minimized error budget.

If this is right

  • Up to 39.5 percent fewer two-qubit gates on compute/uncompute-heavy workloads
  • 36.7 percent lower infidelity compared to exact-only decompositions
  • 15.6 percent aggregate reduction on a 12-24 qubit suite
  • 48.8 percent removal of native two-qubit gates on a state-resetting circuit, all verified
  • Estimated circuit infidelity lowered by 36-43 percent at current hardware error rates

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could be applied to optimize other context-sensitive gates like controlled-SWAP or multi-controlled gates.
  • Decision-diagram verification might enable safer use of approximate methods in larger quantum algorithms.
  • Workload-dependent gains suggest tailoring the pass to specific application domains like quantum error correction circuits.

Load-bearing premise

The decision-diagram equivalence checker is sound and complete with no false negatives for valid substitutions in the benchmark circuits.

What would settle it

A concrete counterexample where the verifier accepts a decomposition as equivalent but the resulting circuit produces a measurably different output distribution from the original on the same input state.

Figures

Figures reproduced from arXiv: 2606.31791 by Karol Bartkiewicz, Patrycja Tulewicz.

Figure 2
Figure 2. Figure 2: Safety ablation: circuits silently corrupted [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 1
Figure 1. Figure 1: The verification gate decides relative-phase [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Error budget over the 12-circuit suite (lower is better; 0 ancilla overhead for every method; all sound methods exactly verified). (a) summed estimated two-qubit infidelity; (b) summed two-qubit-gate count. The count￾greedy baseline (red; QContext/Maslov-style, no public implementation, so realized as substitution at every Toffoli) attains the lowest count and infidelity but is silently wrong on 6 of 12 ci… view at source ↗
Figure 4
Figure 4. Figure 4: Structure of a resetting-protocol letter. The [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Gated pass at representative device operating [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Scale evaluation on the 20-circuit suite (12–24 qubits). (a) mean two-qubit-gate reduction by circuit family: the gain tracks how many Toffolis sit in cancellable compute/uncompute pairs—Grover oracles ≈49%, carry￾lookahead adders ≈28%, ripple adders ≈6%, and modular-increment / array-multiplier circuits 0% (all ANDs live; the sound selector correctly keeps them exact). (b) per-instance verification time v… view at source ↗
read the original 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 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 with per-instance verification 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 library rewrites of a deployed open optimizer as non-equivalent without a context check, and count-greedy substitution silently corrupts 6 of 12 benchmark circuits; the verification gate certifies 0 errors while still applying every valid decomposition. 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 (approx. 39%/35% versus Qiskit opt-3 and tket), and 15.6% aggregate on a larger 12-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-43%, and on a quantum state-resetting circuit, the pass removes 48.8% of the native two-qubit gates, every substitution verified.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a compiler pass for Toffoli (CCX) decomposition selection that minimizes two-qubit infidelity by admitting context-dependent (relative-phase or approximate) decompositions only when an instance-specific decision-diagram equivalence check certifies validity in the surrounding circuit. It reports that existing pattern-matched rewrites from a deployed optimizer are non-equivalent in 66 cases without context, that count-greedy substitution corrupts 6 of 12 benchmarks, and that the verified pass achieves up to 39.5% two-qubit gate reduction and 36-43% infidelity reduction on superconducting/trapped-ion error rates while certifying zero errors on the evaluated suites.

Significance. If the per-instance verification is sound, the work supplies the first practical coupling of error-budget optimization with context-aware verification for a common multi-qubit primitive, directly addressing a known safety gap in current quantum compilers. The concrete benchmark numbers (66 flagged rewrites, 6 corrupted circuits, 39.5% gate reduction, 36.7% infidelity drop) and the demonstration that verification can be applied past exhaustive limits provide measurable evidence of both the problem and a workable mitigation.

major comments (2)
  1. [Verification / Methods] Verification / Methods: The central safety claim (66 non-equivalent rewrites flagged, 0 errors certified on all substitutions) rests on the decision-diagram equivalence checker being sound and complete for every relative-phase and approximate-Toffoli context arising in the 12- and 24-qubit suites. No independent cross-validation (exhaustive unitary comparison on small instances, ZX-diagram equivalence, or false-negative analysis on residual-phase circuits) is reported; this assumption is load-bearing for the "certifies 0 errors" result.
  2. [Results] Results, paragraph on 12-24-qubit suite: The 15.6% aggregate two-qubit reduction and 36-43% infidelity improvement are stated without per-circuit error bars or explicit breakdown of how the infidelity budget is computed from the chosen decompositions; because the error-budget objective is the primary optimization target, the quantitative claims require the underlying fidelity model and its sensitivity to be shown.
minor comments (2)
  1. [Abstract] Abstract: "approx. 39%/35% versus Qiskit opt-3 and tket" is ambiguous; clarify whether these are two separate comparisons or a single paired figure.
  2. [Abstract] Abstract and Results: The phrase "past the exhaustive-verification limit" is used without stating what that limit is (qubit count, gate depth, or DD node count) or how soundness is preserved under the fallback heuristic.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important aspects of verification soundness and quantitative presentation that we will address in revision.

read point-by-point responses

  1. Referee: [Verification / Methods] Verification / Methods: The central safety claim (66 non-equivalent rewrites flagged, 0 errors certified on all substitutions) rests on the decision-diagram equivalence checker being sound and complete for every relative-phase and approximate-Toffoli context arising in the 12- and 24-qubit suites. No independent cross-validation (exhaustive unitary comparison on small instances, ZX-diagram equivalence, or false-negative analysis on residual-phase circuits) is reported; this assumption is load-bearing for the "certifies 0 errors" result.

    Authors: The decision-diagram equivalence procedure we employ is a standard, sound and complete method for checking unitary equivalence (including relative phases) that has been validated in prior literature on quantum circuit equivalence. We agree that reporting independent cross-validation would strengthen the central safety claim. In the revised manuscript we will add a Methods subsection that (i) details the DD checker implementation, (ii) presents exhaustive unitary-matrix comparisons for all instances with ≤4 qubits, and (iii) includes a targeted false-negative analysis on residual-phase circuits drawn from the benchmark suites. These additions directly address the load-bearing assumption. revision: yes

  2. Referee: [Results] Results, paragraph on 12-24-qubit suite: The 15.6% aggregate two-qubit reduction and 36-43% infidelity improvement are stated without per-circuit error bars or explicit breakdown of how the infidelity budget is computed from the chosen decompositions; because the error-budget objective is the primary optimization target, the quantitative claims require the underlying fidelity model and its sensitivity to be shown.

    Authors: We concur that the primary optimization target requires an explicit fidelity model and per-circuit detail. The infidelity budget is computed as the sum of per-gate two-qubit infidelities using published hardware error rates (superconducting ≈0.5 %, trapped-ion ≈0.1 %). In the revision we will (i) expand the Results section with a table listing per-circuit two-qubit gate counts and estimated infidelities for the full 12-24-qubit suite, (ii) state the exact infidelity formula and the two hardware models used, and (iii) add a sensitivity analysis showing how the reported 36-43 % improvement varies with the assumed error rates. Because the selection is deterministic, conventional statistical error bars are not applicable; we will instead report the range across the two hardware models. revision: yes

Circularity Check

0 steps flagged

No circularity; results are empirical benchmark measurements with independent verification

full rationale

The paper's central claims (66 non-equivalent rewrites flagged, 0 errors on benchmarks, workload-dependent gate reductions) are obtained by executing the described pass and decision-diagram checker on concrete circuits. No equations, parameters, or derivations are shown that reduce by construction to fitted inputs or self-definitions. The verification gate is presented as an independent soundness check decoupled from the error-budget objective. Self-citations, if present for the DD checker, are not load-bearing for the reported safety or reduction numbers, which rest on external benchmark execution rather than internal redefinition.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The work rests on standard quantum-circuit equivalence and error-rate assumptions that are not detailed in the abstract; no free parameters, invented entities, or non-standard axioms are visible from the provided text.

pith-pipeline@v0.9.1-grok · 5870 in / 1257 out tokens · 23912 ms · 2026-07-01T05:28:11.222412+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Quantum Computing in the NISQ era and beyond

    John Preskill. “Quantum Computing in the NISQ era and beyond”. Quantum2, 79 (2018)

    2018

  2. [2]

    Quantum synchroniz- ing words

    Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, Jędrzej Stempin, Jan Wójcik, and Antoni Wójcik. “Quantum synchroniz- ing words”. New Journal of Physics27, 114504 (2025)

    2025

  3. [3]

    Quantum resetting protocols based on synchronizing words

    Jędrzej Stempin, Jan Wójcik, Andrzej Grudka, Marcin Karczewski, Paweł Kurzyński, and Antoni Wójcik. “Quantum resetting protocols based on synchronizing words” (2025). arXiv:2504.01106

    work page arXiv 2025

  4. [4]

    Advantages of using relative-phase toffoli gates with an applica- tion to multiple control toffoli optimization

    Dmitri Maslov. “Advantages of using relative-phase toffoli gates with an applica- tion to multiple control toffoli optimization”. Phys. Rev. A93, 022311 (2016)

    2016

  5. [5]

    Best approximate quantum compiling problems

    Liam Madden and Andrea Simonetto. “Best approximate quantum compiling problems”. ACM Transactions on Quantum Comput- ing3(2022)

    2022

  6. [6]

    Qcontext: Context-aware decomposition for quantum gates

    Ji Liu, Max Bowman, Pranav Gokhale, Sid- dharth Dangwal, Jeffrey Larson, Frederic T. Chong, and Paul D. Hovland. “Qcontext: Context-aware decomposition for quantum gates”. In 2023 IEEE International Sym- posium on Circuits and Systems (ISCAS). Pages 1–5. (2023)

    2023

  7. [7]

    A verified optimizer for quantum circuits

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

    2021

  8. [8]

    Quartz: superop- timization of quantum circuits

    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: superop- timization of quantum circuits”. In Pro- ceedings of the 43rd ACM SIGPLAN Inter- national Conference on Programming Lan- guage Design and Implementation. Page 625–640. PLDI 2022New York, NY, USA...

    2022

  9. [9]

    Op- timization of quantum Boolean circuits by relative-phase Toffoli gates

    Shohei Kuroda and Shigeru Yamashita. “Op- timization 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)

    2022

  10. [10]

    Ad- vanced equivalence checking for quantum 15 circuits

    Lukas Burgholzer and Robert Wille. “Ad- vanced equivalence checking for quantum 15 circuits”. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Sys- tems40, 1810–1824 (2021)

    2021

  11. [11]

    t|ket〉: a retargetable com- piler for nisq devices

    Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, WillSimmons, AlecEdgington, and Ross Duncan. “t|ket〉: a retargetable com- piler for nisq devices”. Quantum Science and Technology6, 014003 (2020)

    2020

  12. [12]

    Pyzx: Large scale automated dia- grammatic reasoning

    Aleks Kissinger and John van de Weter- ing. “Pyzx: Large scale automated dia- grammatic reasoning”. Electronic Proceed- ings in Theoretical Computer Science318, 229–241 (2020)

    2020

  13. [13]

    Unqomp: syn- thesizing uncomputation in quantum cir- cuits

    Anouk Paradis, Benjamin Bichsel, Samuel Steffen, and Martin Vechev. “Unqomp: syn- thesizing uncomputation in quantum cir- cuits”. In Proceedings of the 42nd ACM SIGPLAN International Conference on Pro- gramming Language Design and Implemen- tation. Page 222–236. PLDI 2021New York, NY, USA (2021). Association for Computing Machinery

    2021

  14. [14]

    Reqomp: Space-constrained Uncomputation for Quantum Circuits

    Anouk Paradis, Benjamin Bichsel, and Mar- tin Vechev. “Reqomp: Space-constrained Uncomputation for Quantum Circuits”. Quantum8, 1258 (2024)

    2024

  15. [15]

    Silq: a high- level quantum language with safe uncompu- tation and intuitive semantics

    Benjamin Bichsel, Maximilian Baader, Ti- mon Gehr, and Martin Vechev. “Silq: a high- level quantum language with safe uncompu- tation and intuitive semantics”. In Proceed- ings of the 41st ACM SIGPLAN Conference on Programming Language Design and Im- plementation. Page286–300. PLDI2020New York, NY,USA(2020).AssociationforCom- puting Machinery

    2020

  16. [16]

    Modular syn- thesis of efficient quantum uncomputation

    Hristo Venev, Timon Gehr, Dimitar Dim- itrov, and Martin Vechev. “Modular syn- thesis of efficient quantum uncomputation”. Proc. ACM Program. Lang.8(2024)

    2024

  17. [17]

    Halving the cost of quantum addition

    Craig Gidney. “Halving the cost of quantum addition”. Quantum2, 74 (2018)

    2018

  18. [18]

    Rise of conditionally clean ancillae for efficient quantum circuit constructions

    Tanuj Khattar and Craig Gidney. “Rise of conditionally clean ancillae for efficient quantum circuit constructions”. Quantum9, 1752 (2025)

    2025

  19. [19]

    A meet- in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits

    Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. “A meet- in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems32, 818– 830 (2013)

    2013

  20. [20]

    Demonstration of logical qubits and repeated error correction with better-than-physical error rates

    A. Paetznick, M. P. da Silva, C. Ryan- Anderson, J. M. Bello-Rivas, J. P. Cam- pora 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. Mat- suoka, M. Mills, S. A. Moses, B. Neyen- huis, A. Paz, J. Pino, P. Sie...

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  21. [21]

    IBM Quantum platform: Backend calibration data (ibm_marrakesh, heron r2)

    IBM Quantum. “IBM Quantum platform: Backend calibration data (ibm_marrakesh, heron r2)”.https://quantum.ibm.co m(2025). Per-device median two-qubit (CZ) gateerror; valuesvarywithdailycalibration

    2025

  22. [22]

    Quantum error correction below the sur- face code threshold

    Google Quantum AI and Collaborators. “Quantum error correction below the sur- face code threshold”. Nature638, 920– 926 (2025)

    2025

  23. [23]

    Benchmarking a trapped-ion quan- tum computer with 30 qubits

    Jwo-Sy Chen, Erik Nielsen, Matthew Ebert, Volkan Inlek, Kenneth Wright, Vandiver Chaplin, Andrii Maksymov, Eduardo Páez, Amrit Poudel, Peter Maunz, and John Gam- ble. “Benchmarking a trapped-ion quan- tum computer with 30 qubits”. Quantum8, 1516 (2024)

    2024

  24. [24]

    IonQ Aria: Practical performance

    IonQ. “IonQ Aria: Practical performance”. https://www.ionq.com/resources/ion q-aria-practical-performance(2025). Two-qubit error 0.4%, single-qubit error 0.05%. 16

    2025