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
v1 · Jun 30, 2026v2 · Oct 30, 2026
arXivHTMLPDF

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.

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
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.
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.