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:1212.5069 · Physical Review A

Low-overhead constructions for the fault-tolerant Toffoli gate

Cody Jones

Published Feb 20, 2013• 244 citations
arXivHTMLPDF

Abstract

We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)$ gates, whereas conventional circuits require seven $T$ gates. An extension of this result is that adding $n$ control inputs to a controlled gate requires $4n$ $T$ gates, whereas the best prior result was $8n$. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability $p$ in any one of eight $T$ gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from $4p$ (or $7p$, without the first contribution) to $28{p}^{2}$ for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.

DOI
10.1103/physreva.87.022328

Related papers

Composite Toffoli gate with two-round error detection

Cody Jones

We introduce a fault-tolerant construction to implement a composite quantum operation of four overlapping Toffoli gates. The same construction can produce two independent Toffoli gates. This result lowers resource overheads in designs for quantum computers by more than an order of magnitude. The procedure uses Clifford operations and 64 copies of the non-Clifford gate $T=\mathrm{exp}[i\ensuremath{\pi}(I\ensuremath{-}{\ensuremath{\sigma}}^{z})/8]$. Quantum codes detect errors in the circuit. When the dominant source of error is $T$-gate failure with probability $p$, then the composite Toffoli circuit has a postselected failure rate of $3072{p}^{4}$ to lowest order.

arXiv:1303.6971•Physical Review A•May 31, 2013•27 citations

Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Amit Saha, Francesco Arzani

Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths $n=2^h-1$, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires $6n+3$ logical $P_9$ injections and $\frac{n-3}{4}$ clean ancillary qutrits. It matches the direct $P_9$ count of a recursively extended Clifford+$P_9$ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the $6n+3$ $P_9$ count but has depth $O(\log m+n-m)$ for a balanced core $m=2^h-1\leq n$, which is linear in the worst case over $n$. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.

quant-pharXiv:2609.29884•Sep 25, 2026•1 citation

Logic Synthesis for Fault-Tolerant Quantum Computers

N. Cody Jones

Efficient constructions for quantum logic are essential since quantum computation is experimentally challenging. This thesis develops quantum logic synthesis as a paradigm for reducing the resource overhead in fault-tolerant quantum computing. The model for error correction considered here is the surface code. After developing the theory behind general logic synthesis, the resource costs of magic-state distillation for the $T = \exp(i π(I-Z)/8)$ gate are quantitatively analyzed. The resource costs for a relatively new protocol distilling multi-qubit Fourier states are calculated for the first time. Four different constructions of the fault-tolerant Toffoli gate, including two which incorporate error detection, are analyzed and compared. The techniques of logic synthesis reduce the cost of fault-tolerant quantum computation by one to two orders of magnitude, depending on which benchmark is used. Using resource analysis for $T$ gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+$T$" sequences, $V$-basis sequences, phase kickback, and programmable ancilla rotations. The application of arbitrary gates to quantum algorithms for simulating chemistry is discussed as well. Finally, the thesis examines the techniques which lead to efficient constructions of quantum logic, and these observations point to even broader applications of logic synthesis.

arXiv:1310.7290•Oct 28, 2013•20 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

Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates

Abhoy Kole, Till Schnittka, Rolf Drechsler

The Toffoli gate is a fundamental building block for quantum arithmetic and reversible logic, yet its efficient realization remains a major challenge in both near-term and fault-tolerant quantum architectures. Recent advances in dynamic quantum circuit capabilities, including mid-circuit measurement and classical feedforward, provide new opportunities for reducing the resource overhead of non-Clifford operations. In this work, we propose a set of dynamic decomposition strategies for multi-controlled Toffoli gates that exploit adaptive circuit execution and ancilla-assisted constructions. Our methods systematically reduce entangling-gate count, T-count, and T-depth compared with conventional static decompositions, while preserving fault-tolerance guarantees. Through analytical cost models and experimental evaluation, we demonstrate that relative-phase primitives and measurement-conditioned corrections enable scalable implementations with improved depth and resource efficiency.

quant-pharXiv:2605.18159•IEEE International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS)•May 19, 2026•2 citations

Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles

Arul Rhik Mazumder

In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.

quant-pharXiv:2610.38189•Oct 29, 2026•0 citations
We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four T=exp(i\ensuremathπ\ensuremathσz/8)T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)T=exp(i\ensuremathπ\ensuremathσz/8) gates, whereas conventional circuits require seven TTT gates. An extension of this result is that adding nnn control inputs to a controlled gate requires 4n4n4n TTT gates, whereas the best prior result was 8n8n8n. The second contribution is a quantum circuit for the Toffoli gate which can detect a single \ensuremathσz{\ensuremath{\sigma}}^{z}\ensuremathσz error occurring with probability ppp in any one of eight TTT gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from 4p4p4p (or 7p7p7p, without the first contribution) to 28p228{p}^{2}28p2 for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.
We introduce a fault-tolerant construction to implement a composite quantum operation of four overlapping Toffoli gates. The same construction can produce two independent Toffoli gates. This result lowers resource overheads in designs for quantum computers by more than an order of magnitude. The procedure uses Clifford operations and 64 copies of the non-Clifford gate $T=\mathrm{exp}[i\ensuremath{\pi}(I\ensuremath{-}{\ensuremath{\sigma}}^{z})/8]$. Quantum codes detect errors in the circuit. When the dominant source of error is TTT-gate failure with probability ppp, then the composite Toffoli circuit has a postselected failure rate of 3072p43072{p}^{4}3072p4 to lowest order.
Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P9+P_9+P9​ Gates
Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths n=2h−1n=2^h-1n=2h−1, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires 6n+36n+36n+3 logical P9P_9P9​ injections and n−34\frac{n-3}{4}4n−3​ clean ancillary qutrits. It matches the direct P9P_9P9​ count of a recursively extended Clifford+P9P_9P9​ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the 6n+36n+36n+3 P9P_9P9​ count but has depth O(log⁡m+n−m)O(\log m+n-m)O(logm+n−m) for a balanced core m=2h−1≤nm=2^h-1\leq nm=2h−1≤n, which is linear in the worst case over nnn. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.
Efficient constructions for quantum logic are essential since quantum computation is experimentally challenging. This thesis develops quantum logic synthesis as a paradigm for reducing the resource overhead in fault-tolerant quantum computing. The model for error correction considered here is the surface code. After developing the theory behind general logic synthesis, the resource costs of magic-state distillation for the T=exp⁡(iπ(I−Z)/8)T = \exp(i π(I-Z)/8)T=exp(iπ(I−Z)/8) gate are quantitatively analyzed. The resource costs for a relatively new protocol distilling multi-qubit Fourier states are calculated for the first time. Four different constructions of the fault-tolerant Toffoli gate, including two which incorporate error detection, are analyzed and compared. The techniques of logic synthesis reduce the cost of fault-tolerant quantum computation by one to two orders of magnitude, depending on which benchmark is used. Using resource analysis for TTT gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+TTT" sequences, VVV-basis sequences, phase kickback, and programmable ancilla rotations. The application of arbitrary gates to quantum algorithms for simulating chemistry is discussed as well. Finally, the thesis examines the techniques which lead to efficient constructions of quantum logic, and these observations point to even broader applications of logic synthesis.
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 Toffoli gate is a fundamental building block for quantum arithmetic and reversible logic, yet its efficient realization remains a major challenge in both near-term and fault-tolerant quantum architectures. Recent advances in dynamic quantum circuit capabilities, including mid-circuit measurement and classical feedforward, provide new opportunities for reducing the resource overhead of non-Clifford operations. In this work, we propose a set of dynamic decomposition strategies for multi-controlled Toffoli gates that exploit adaptive circuit execution and ancilla-assisted constructions. Our methods systematically reduce entangling-gate count, T-count, and T-depth compared with conventional static decompositions, while preserving fault-tolerance guarantees. Through analytical cost models and experimental evaluation, we demonstrate that relative-phase primitives and measurement-conditioned corrections enable scalable implementations with improved depth and resource efficiency.
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.