Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks
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.
Related
- Physics-guided deep neural networks for Laguerre–Gaussian modal decomposition via PCA-ranked Zernike descriptors
- Directional memory of early spectral selection during spinodal decomposition in finite systems
- Finite basis Kolmogorov-Arnold networks: Domain decomposition for data-driven and physics-informed problems
- Encoded reversible addition in constant Toffoli depth
- On the Assessment of Domain Decomposition Approaches in Extended Physics-Informed Neural Networks for the Shock-Dominated Burgers Equation
BibTeX
@misc{bartkiewicz2026contextverified,
title = {{Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks}},
author = {Karol Bartkiewicz and Patrycja Tulewicz},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.31791},
eprint = {2606.31791},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.31791},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks
AU - Karol Bartkiewicz
AU - Patrycja Tulewicz
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2606.31791
UR - https://arxiv.org/abs/2606.31791
AB - 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.
ER -