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

ACM Transactions on Quantum Computing

Toffoli Requires Six Quantum Neighbor Gates

Keli Huang, Jens Palsberg

Published Jan 2, 2026• 0 citations
Publisher

Abstract

Toffoli gates are key building blocks in quantum programs, and on most current quantum computers, they must be implemented with smaller gates. Such an implementation requires five 2-qubit gates if we assume that each gate can operate on any two qubits. However, many current quantum computers have only 2-qubit gates that operate on neighboring qubits; we call them neighbor gates. How many neighbor gates are required to implement a Toffoli gate? In this article, we show that six neighbor gates are necessary and sufficient, and we generalize to a characterization of all 3-qubit diagonal gates.

DOI
10.1145/3787463

Related papers

Five two-qubit gates are necessary for implementing the Toffoli gate

Nengkun Yu, Runyao Duan, Mingsheng Ying

In this Rapid Communication, we consider the open problem of the minimum cost of two-qubit gates for simulating the Toffoli gate and show that five two-qubit gates are necessary. Before our work, it was known that five two-qubit gates are sufficient to implement the Toffoli gate, and numerical evidence indicates that five two-qubit gates are also necessary. The idea introduced here can also be used to solve the problem of optimal simulation of Deutsch three-qubit gates.

arXiv:1301.3372•Physical Review A•Jul 30, 2013•86 citations

Efficient implementation of multi-control Toffoli gates in linear nearest neighbor arrays

Saman Daraeizadeh

Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.

•May 1, 2014•1 citation

Optimal implementation of quantum gates with two controls

Jens Palsberg, Nengkun Yu

We give a detailed proof of a well-known theorem in quantum computing. The theorem characterizes the number of two-qubit gates that is necessary for implementing three-qubit quantum gates with two controls. For example, the theorem implies that five 2-qubit gates are necessary for implementing the Toffoli gate. No detailed proof was available earlier.

Linear Algebra and its Applications•Apr 4, 2024•4 citations

On the CNOT -cost of TOFFOLI gates

Vivek Shende, Igor L. Markov

The three-input \TOFFOLI\ gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, \TOFFOLI\ gates are decomposed into six \CNOT\ gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its \CNOT-optimality. We study three-qubit circuits which contain less than six \CNOT\ gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonical nature of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the $n$-qubit analogue of the \TOFFOLI\ requires at least $2n$ \CNOT\ gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their \CNOT -cost, which holds even if ancilla qubits are available.

arXiv:0803.2316•Quantum Information and Computation•May 1, 2009•264 citations

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is a universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very non-classical feature of the operation, its exact quantum phase factor.

arXiv:cond-mat/9409111•Sep 26, 1994•16 citations

Results on two-bit gate design for quantum computers

David Peter Divincenzo, John A. Smolin

We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is the universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very nonclassical feature of the operation, its exact quantum phase factor.>

Workshop on Physics and Computation (PhysComp)•Dec 17, 2002•18 citations
Toffoli gates are key building blocks in quantum programs, and on most current quantum computers, they must be implemented with smaller gates. Such an implementation requires five 2-qubit gates if we assume that each gate can operate on any two qubits. However, many current quantum computers have only 2-qubit gates that operate on neighboring qubits; we call them neighbor gates. How many neighbor gates are required to implement a Toffoli gate? In this article, we show that six neighbor gates are necessary and sufficient, and we generalize to a characterization of all 3-qubit diagonal gates.
Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.
The three-input \TOFFOLI\ gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, \TOFFOLI\ gates are decomposed into six \CNOT\ gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its \CNOT-optimality. We study three-qubit circuits which contain less than six \CNOT\ gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonical nature of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the nnn-qubit analogue of the \TOFFOLI\ requires at least 2n2n2n \CNOT\ gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their \CNOT -cost, which holds even if ancilla qubits are available.
We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is a universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very non-classical feature of the operation, its exact quantum phase factor.
We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is the universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very nonclassical feature of the operation, its exact quantum phase factor.>