Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.31791

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

Karol Bartkiewicz, Patrycja Tulewicz

quant-phSubmitted Jun 30, 2026• Announced Jul 1, 2026• 2 citations• Revised Oct 30, 2026 (v2)
v1 · Jun 30, 2026v2 · Oct 30, 2026
arXivHTMLPDF

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 papers

When More Becomes Less: Topology-Reversed Three-Qubit Gate Performance on IBM Quantum Processors

Simona K. Grigorova, Stancho S. Stanchev, Nikolay V. Vitanov

The exact Toffoli gate admits a six-CX decomposition, denoted by $CCX_6$, that is optimal under unrestricted two-qubit connectivity. On a linear three-qubit topology, however, $CCX_6$ contains 4 nearest-neighbor CX gates and 2 non-nearest-neighbor CX gates. By contrast, an alternative exact decomposition, denoted by $CCX_8$, uses only 8 nearest-neighbor CX gates. Because CCX is locally equivalent to CCZ, we perform the experiments using the corresponding $\cczs$ and $\cczl$ circuits. We compare these circuits on sampled linear triples of the 156-qubit IBM Quantum Heron processors \texttt{ibm\_fez} and \texttt{ibm\_kingston}. Under the compilation protocol, the nominal $\cczs$ circuit becomes a twelve-CZ implementation, whereas the linear-nearest-neighbor circuit retains eight native CZ gates. Experimentally measured ensemble-feature-selection estimates favor the eight-CZ realization on nearly all retained triples. We test the same ordering by preparing a three-qubit hypergraph state, which probes the coherent conditional phase rather than only computational-basis populations. The measured hypergraph-state infidelity is lower for the $\cczl$ circuit for most triples on both processors. Phase-altered interleaved randomized benchmarking provides a complementary comparison of Clifford surrogates preserving the two compiled entangling structures. Within the scope of the tested circuits and phase-sensitive input state, the results demonstrate that hardware connectivity can reverse the operational ranking of exact decompositions: a circuit with more abstract two-qubit gates can yield the better physical implementation.

quant-pharXiv:2608.21004•Aug 24, 2026•0 citations

Adaptive Clifford+T Decomposition of Large Toffoli Gates with One Clean Ancilla

Abhoy Kole, Majd Assaad, Till Schnittka +1 more

Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.

quant-pharXiv:2605.18169•May 19, 2026•1 citation

Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging

Pedro M. Q. Cruz, Bruno Murta

The controlled-swap and controlled-controlled-not gates are at the heart of the original proposal of reversible classical computation by Fredkin and Toffoli. Their widespread use in quantum computation, both in the implementation of classical logic subroutines of quantum algorithms and in quantum schemes with no direct classical counterparts, has made it imperative early on to pursue their efficient decomposition in terms of the lower-level gate sets native to different physical platforms. Here, we add to this body of literature by providing several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity, the latter with two different routings for control and target qubits. Besides achieving the lowest cnot counts in the literature for all these configurations, we also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers via equivalent circuit averaging. We first quantify the performance of the method in silico with a coherent-noise model before validating it experimentally on a superconducting quantum processor. In addition, we consider the case where the three qubits on which the Toffoli or Fredkin gates act nontrivially are not adjacent, proposing a novel scheme to reorder them that saves one cnot for every swap. This scheme also finds use in the shallow implementation of long-range cnots. Our results highlight the importance of considering different entangling gate structures and connectivity constraints when designing efficient quantum circuits.

arXiv:2305.18128•APL Quantum•Feb 23, 2024•32 citations

Quantum-Adaptive KS($\varphi$): A Parameterized Three-Qubit Gate Family Embedding Toffoli with Measurement-Free Phase Kickback and Intrinsic Error Non-Amplification

Kripa Sankaranarayanan, Marek Perkowski

We introduce Quantum-Adaptive KS($\varphi$) ($K$ = kickback, $S$ = sandwich), a parameterized three-qubit gate family that structurally embeds the Toffoli (CCX) gate within two additional components: (1)a palindromic Hadamard sandwich on the first control qubit $q_0$ that conjugates $Z$-type errors to $X$-type in the CCX frame, providing simultaneous sensitivity to both error types without ancilla overhead; and (2)a controlled-phase (CP) gate whose quantum phase kickback propagates post-CCX target-state information into the control-qubit phase without measurement. The term Quantum- Adaptive refers to amplitude steering conditioned by the compile-time parameter $\varphi$ via a Quantum Neural Cellular Automaton (QNCA) majority-inspired bias rule; the gate does not self-modify at runtime. Two QA-KS($π$) gates chained on a shared control qubit $q_0$ produce outputs completely orthogonal to two sequential CCX gates on $q_0$=1 inputs (output fidelity F=0.000), while agreeing exactly on $q_0$=0 inputs (F=1.000). This subspace-dependent divergence is the direct computational signature of coherent phase retention across gate boundaries -- impossible for CCX-only circuits. On the $q_1$ = 0 subspace the gate acts deterministically (up to a relative phase), providing intrinsic error non-amplification. On the $q_1$ = 1 subspace it produces four-component entangled superpositions, making it a strictly distinct quantum-native primitive from CCX. We present the complete $8 \times 8$ unitary matrix, confirmed exact to $||U^{\dagger}U-I||_{\infty} < 10^{-15}$, and define two canonical variants: QA-KS$_{π/2}$ ($\varphi = π/2$, $S$ gate) and QA-KS$_π$ ($\varphi = π$, $Z$ gate). Qiskit depolarizing-noise simulation demonstrates near-unit fidelity at $p \leq 10^{-2}$ with an honest depth cost at higher error rates. The gate preserves the three-qubit footprint of CCX with no qubit overhead.

quant-pharXiv:2605.24182•May 26, 2026•0 citations

Structure-Aware Placement and Routing of Multi-Controlled Toffoli on Bivariate Bicycle Code Architectures

Anik Basu Bhaumik, Suman Dutta, Siyi Wang +1 more

The multi-controlled Toffoli (MCT) gate is a fundamental primitive in quantum circuit design, with applications in quantum arithmetic, cryptanalysis, and algorithmic implementations. Being a high-level logical operation, the efficient decomposition of MCT gates into lower-level netlists has remained a major optimization challenge for decades. While emerging quantum error-correcting codes such as bivariate bicycle (BB) codes drastically reduce fault-tolerance overhead, realizing non-Clifford circuits on modular BB-code architectures introduces complex compilation bottlenecks governed by inter-module routing, factory density, and layout. Consequently, the mapping of MCT gates onto BB-code architectures remains relatively unexplored. In this paper, we overcome these challenges by mapping optimal-Toffoli-depth MCT decompositions (Dutta et al., PRA, 2025) onto BB-code-based fault-tolerant architectures via direct $\lvert \mathrm{CCZ} \rangle$ state injection from an external magic state factory. We introduce a targeted placement strategy that exploits the binary-tree structure of MCT decompositions to co-locate interacting subtrees. This approach reduces inter-module instruction counts by up to $\mathbf{16.02}\%$ compared to a naive sequential first-fit placement. We also evaluate the impact of factory placement across different topologies, demonstrating that grid-based layouts yield up to a $\mathbf{23.7}\%$ reduction in inter-module instructions relative to linear architectures (Yoder et al., arXiv, 2025). Finally, we validate the practical viability of our compiled circuits by analyzing aggregate execution errors and logical failure probabilities using the bicycle-ISA error estimator bicycle_numerics provided by the Qiskit community, https://github.com/qiskit-community/bicycle-architecture-compiler.

quant-pharXiv:2609.00852•Sep 2, 2026•0 citations

End-to-End Fidelity Analysis of Quantum Circuit Optimization: From Gate-Level Transformations to Pulse-Level Control

Rylan Malarchick

We present an analysis of quantum circuit fidelity across the full compilation stack, from high-level gate optimization through pulse-level control. We connect a C++ circuit optimizer to a per-gate Lindblad master-equation fidelity model whose decoherence channels are cross-validated against qiskit-dynamics and whose absolute predictions are benchmarked against execution on real hardware. Across a campaign of 4,452 experiment runs over 371 benchmark circuits, gate cancellation provides the dominant improvement ($d = 1.66$, 72% of circuits improved), while circuit size and pulse duration are the strongest negative predictors of process fidelity (input gates $r = -0.78$; pulse duration $r = -0.73$, $R^2 = 0.53$). A formal ablation study shows that pass ordering has no significant effect on two-qubit gate reduction (Kruskal--Wallis $p = 0.302$). Comparing against Qiskit transpilation levels, we show that two-qubit gate count, not total gate count, is the hardware-relevant metric: our optimizer attains superior two-qubit reduction on structured circuits (87.8% on QFT, 100% on QAOA) whereas Qiskit's larger total-gate reduction is dominated by single-qubit ($u_3$) consolidation. Finally, executing eight circuits on the IQM Resonance Garnet processor (8/8 jobs completed, job identifiers released) reveals that the model is a consistent upper bound: it preserves the relative difficulty ordering of circuits but overestimates absolute fidelity by a mean of 0.49, quantifying the error budget (crosstalk, leakage, readout) outside a $T_1$/$T_2$/depolarizing model. We release the framework, data, and scripts as open source.

quant-pharXiv:2601.20871•Jan 20, 2026•0 citations
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.
The exact Toffoli gate admits a six-CX decomposition, denoted by CCX6CCX_6CCX6​, that is optimal under unrestricted two-qubit connectivity. On a linear three-qubit topology, however, CCX6CCX_6CCX6​ contains 4 nearest-neighbor CX gates and 2 non-nearest-neighbor CX gates. By contrast, an alternative exact decomposition, denoted by CCX8CCX_8CCX8​, uses only 8 nearest-neighbor CX gates. Because CCX is locally equivalent to CCZ, we perform the experiments using the corresponding $\cczs$ and $\cczl$ circuits. We compare these circuits on sampled linear triples of the 156-qubit IBM Quantum Heron processors \texttt{ibm\_fez} and \texttt{ibm\_kingston}. Under the compilation protocol, the nominal $\cczs$ circuit becomes a twelve-CZ implementation, whereas the linear-nearest-neighbor circuit retains eight native CZ gates. Experimentally measured ensemble-feature-selection estimates favor the eight-CZ realization on nearly all retained triples. We test the same ordering by preparing a three-qubit hypergraph state, which probes the coherent conditional phase rather than only computational-basis populations. The measured hypergraph-state infidelity is lower for the $\cczl$ circuit for most triples on both processors. Phase-altered interleaved randomized benchmarking provides a complementary comparison of Clifford surrogates preserving the two compiled entangling structures. Within the scope of the tested circuits and phase-sensitive input state, the results demonstrate that hardware connectivity can reverse the operational ranking of exact decompositions: a circuit with more abstract two-qubit gates can yield the better physical implementation.
Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead. In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.
The controlled-swap and controlled-controlled-not gates are at the heart of the original proposal of reversible classical computation by Fredkin and Toffoli. Their widespread use in quantum computation, both in the implementation of classical logic subroutines of quantum algorithms and in quantum schemes with no direct classical counterparts, has made it imperative early on to pursue their efficient decomposition in terms of the lower-level gate sets native to different physical platforms. Here, we add to this body of literature by providing several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity, the latter with two different routings for control and target qubits. Besides achieving the lowest cnot counts in the literature for all these configurations, we also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers via equivalent circuit averaging. We first quantify the performance of the method in silico with a coherent-noise model before validating it experimentally on a superconducting quantum processor. In addition, we consider the case where the three qubits on which the Toffoli or Fredkin gates act nontrivially are not adjacent, proposing a novel scheme to reorder them that saves one cnot for every swap. This scheme also finds use in the shallow implementation of long-range cnots. Our results highlight the importance of considering different entangling gate structures and connectivity constraints when designing efficient quantum circuits.
Quantum-Adaptive KS(φ\varphiφ): A Parameterized Three-Qubit Gate Family Embedding Toffoli with Measurement-Free Phase Kickback and Intrinsic Error Non-Amplification
We introduce Quantum-Adaptive KS(φ\varphiφ) (KKK = kickback, SSS = sandwich), a parameterized three-qubit gate family that structurally embeds the Toffoli (CCX) gate within two additional components: (1)a palindromic Hadamard sandwich on the first control qubit q0q_0q0​ that conjugates ZZZ-type errors to XXX-type in the CCX frame, providing simultaneous sensitivity to both error types without ancilla overhead; and (2)a controlled-phase (CP) gate whose quantum phase kickback propagates post-CCX target-state information into the control-qubit phase without measurement. The term Quantum- Adaptive refers to amplitude steering conditioned by the compile-time parameter φ\varphiφ via a Quantum Neural Cellular Automaton (QNCA) majority-inspired bias rule; the gate does not self-modify at runtime. Two QA-KS(πππ) gates chained on a shared control qubit q0q_0q0​ produce outputs completely orthogonal to two sequential CCX gates on q0q_0q0​=1 inputs (output fidelity F=0.000), while agreeing exactly on q0q_0q0​=0 inputs (F=1.000). This subspace-dependent divergence is the direct computational signature of coherent phase retention across gate boundaries -- impossible for CCX-only circuits. On the q1q_1q1​ = 0 subspace the gate acts deterministically (up to a relative phase), providing intrinsic error non-amplification. On the q1q_1q1​ = 1 subspace it produces four-component entangled superpositions, making it a strictly distinct quantum-native primitive from CCX. We present the complete 8×88 \times 88×8 unitary matrix, confirmed exact to ∣∣U†U−I∣∣∞<10−15||U^{\dagger}U-I||_{\infty} < 10^{-15}∣∣U†U−I∣∣∞​<10−15, and define two canonical variants: QA-KSπ/2_{π/2}π/2​ (φ=π/2\varphi = π/2φ=π/2, SSS gate) and QA-KSπ_ππ​ (φ=π\varphi = πφ=π, ZZZ gate). Qiskit depolarizing-noise simulation demonstrates near-unit fidelity at p≤10−2p \leq 10^{-2}p≤10−2 with an honest depth cost at higher error rates. The gate preserves the three-qubit footprint of CCX with no qubit overhead.
The multi-controlled Toffoli (MCT) gate is a fundamental primitive in quantum circuit design, with applications in quantum arithmetic, cryptanalysis, and algorithmic implementations. Being a high-level logical operation, the efficient decomposition of MCT gates into lower-level netlists has remained a major optimization challenge for decades. While emerging quantum error-correcting codes such as bivariate bicycle (BB) codes drastically reduce fault-tolerance overhead, realizing non-Clifford circuits on modular BB-code architectures introduces complex compilation bottlenecks governed by inter-module routing, factory density, and layout. Consequently, the mapping of MCT gates onto BB-code architectures remains relatively unexplored. In this paper, we overcome these challenges by mapping optimal-Toffoli-depth MCT decompositions (Dutta et al., PRA, 2025) onto BB-code-based fault-tolerant architectures via direct ∣CCZ⟩\lvert \mathrm{CCZ} \rangle∣CCZ⟩ state injection from an external magic state factory. We introduce a targeted placement strategy that exploits the binary-tree structure of MCT decompositions to co-locate interacting subtrees. This approach reduces inter-module instruction counts by up to 16.02%\mathbf{16.02}\%16.02% compared to a naive sequential first-fit placement. We also evaluate the impact of factory placement across different topologies, demonstrating that grid-based layouts yield up to a 23.7%\mathbf{23.7}\%23.7% reduction in inter-module instructions relative to linear architectures (Yoder et al., arXiv, 2025). Finally, we validate the practical viability of our compiled circuits by analyzing aggregate execution errors and logical failure probabilities using the bicycle-ISA error estimator bicycle_numerics provided by the Qiskit community, https://github.com/qiskit-community/bicycle-architecture-compiler.
We present an analysis of quantum circuit fidelity across the full compilation stack, from high-level gate optimization through pulse-level control. We connect a C++ circuit optimizer to a per-gate Lindblad master-equation fidelity model whose decoherence channels are cross-validated against qiskit-dynamics and whose absolute predictions are benchmarked against execution on real hardware. Across a campaign of 4,452 experiment runs over 371 benchmark circuits, gate cancellation provides the dominant improvement (d=1.66d = 1.66d=1.66, 72% of circuits improved), while circuit size and pulse duration are the strongest negative predictors of process fidelity (input gates r=−0.78r = -0.78r=−0.78; pulse duration r=−0.73r = -0.73r=−0.73, R2=0.53R^2 = 0.53R2=0.53). A formal ablation study shows that pass ordering has no significant effect on two-qubit gate reduction (Kruskal--Wallis p=0.302p = 0.302p=0.302). Comparing against Qiskit transpilation levels, we show that two-qubit gate count, not total gate count, is the hardware-relevant metric: our optimizer attains superior two-qubit reduction on structured circuits (87.8% on QFT, 100% on QAOA) whereas Qiskit's larger total-gate reduction is dominated by single-qubit (u3u_3u3​) consolidation. Finally, executing eight circuits on the IQM Resonance Garnet processor (8/8 jobs completed, job identifiers released) reveals that the model is a consistent upper bound: it preserves the relative difficulty ordering of circuits but overestimates absolute fidelity by a mean of 0.49, quantifying the error budget (crosstalk, leakage, readout) outside a T1T_1T1​/T2T_2T2​/depolarizing model. We release the framework, data, and scripts as open source.