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

arXiv:2606.31791v2 Announce Type: replace 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.