Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate

Abstract

In this paper, we settle the long-standing open problem of the minimum cost of two-qubit gates for simulating a Toffoli gate. More precisely, we show that five two-qubit gates are necessary. Before our work, it is known that five gates are sufficient and only numerical evidences have been gathered, indicating that the five-gate implementation is necessary. The idea introduced here can also be used to solve the problem of optimal simulation of three-qubit control phase introduced by Deutsch in 1989.

5 Pages, comments welcome

References in corpus (7)

• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Realization of Three-Qubit Quantum Error Correction with Superconducting Circuits
• Quantum Computation as Geometry
• Implementation of a Toffoli Gate with Superconducting Circuits
• Realization of the quantum Toffoli gate with trapped ions
• Implementing the Quantum von Neumann Architecture with Superconducting Circuits
• Efficient Toffoli Gates Using Qudits

Cited by in corpus (32)

• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Deutsch, Toffoli, and CNOT Gates via Rydberg Blockade of Neutral Atoms
• Realization of efficient quantum gates with a superconducting qubit-qutrit circuit
• Low-cost Fredkin gate with auxiliary space
• Hyper-parallel Toffoli gate on three-photon system with two degrees of freedom assisted by single-sided optical microcavities
• Extensive characterization of a family of efficient three-qubit gates at the coherence limit
• Efficient construction of three- and four-qubit quantum gates by global entangling gates
• Learning quantum states and unitaries of bounded gate complexity
• Universal quantum multi-qubit entangling gates with auxiliary spaces
• Quantum information processing with closely-spaced diamond color centers in strain and magnetic fields
• Subdivided Phase Oracle for NISQ Search Algorithms
• Realization of a deterministic quantum Toffoli gate with a single photon
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
• Experimental Demonstration of a Quantum Controlled-SWAP Gate with Multiple Degrees of Freedom of a Single Photon
• Direct Implementation of High-Fidelity Three-Qubit Gates for Superconducting Processor with Tunable Couplers
• Quantum Computation of Eigenvalues within Target Intervals
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• Efficient Fusion of Photonic W-states with Nonunitary Partial-swap Gates
• Polarization and Orbital Angular Momentum Encoded Quantum Toffoli Gate Enabled by Diffractive Neural Networks
• Entangling power of two-qubit unitary operations
• A minimum control ancilla driven quantum computation scheme with repeat-until-success style gate generation
• Encrypted Qubits can be Cloned
• Algorithmic Primitives for Quantum-Assisted Quantum Control
• Scalability and high-efficiency of an $(n+1)$-qubit Toffoli gate sphere via blockaded Rydberg atoms
• Optimized Topological Quantum Compilation of Three-Qubit Controlled Gates in the Fibonacci Anyon Model: A Controlled-Injection Approach
• Asymptotically optimal synthesis of reversible circuits
• Generation of perfectly entangled two and three qubits states by classical random interaction
• Microwave-activated high-fidelity three-qubit gate scheme for fixed-frequency superconducting qubits
• Transversal AND in Quantum Codes
• Quantum circuit synthesis with SQiSW
• Engineering long-range and multi-body interactions via global kinetic constraints