Toffoli Requires Six Quantum Neighbor Gates
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.
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Quantum Information and Cryptography
Polynomial and algebraic computation
Publication details
- Journal / source
- ACM Transactions on Quantum Computing
- Volume
- 7
- Issue
- 2
- Pages
- 1–35
- Publication date
- 2 January 2026
- Language
- EN