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

Quantum Information and Computation

Optimal realizations of simplified Toffoli gates

Guang Song, Andreas Klappenecker

Published Sep 1, 2004• 10 citations
Publisher

Abstract

A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate implementation by Margolus is optimal, in the sense that it attains a lower bound of {\em three} controlled-not gates, and subject to that, a sharp lower bound of {\em four} single-qubit gates. We also discuss optimal implementations of other simplified Toffoli gates, and explain why the phase factor $-1$ invariably occurs in such implementations.

DOI
10.26421/qic4.5-2

Related papers

Optimal realizations of simplified Toffoli gates

SongGuang, KlappeneckerAndreas

A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate i...

Quantum Information and Computation•Sep 1, 2004•0 citations

The simplified Toffoli gate implementation by Margolus is optimal

Guang Song, Andreas Klappenecker

Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.

arXiv:quant-ph/0312225•Dec 31, 2003•11 citations

Toffoli gate implementation method based on Margolus gate on four or more qubits

Andrii Tereshchenko, V. K. Zadiraka

This paper considers the method of building the Toffoli Gate based on the Margolus Gate on four or more qubits. In the first part of the considered method, the modification of the Margolus gate on four or more qubits is suggested. In the second part of the method, the modification of the Margolus gate is transformed into the modification of the Toffoli gate implementation using step-by-step phase rotation compensations. The phase rotation compensation for an N-qubit quantum circuit can be performed with N successive steps, where at each step the gates with phase rotation pi/2^(s-1) are added, where s is the step number, starting from one. The compensation phase requires 2 two-qubit gates and 2N-1 one-qubit gates.

Theoretical and Applied Cybersecurity•Dec 16, 2024•0 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 oper-ations 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 thefirst demonstration of its CNOT-optimality. We study three-qubit circuits which containless than six CNOT gates and implement a block-diagonal operator, then show that theyimplicitly describe the cosine-sine decomposition of a related operator. Leveraging thecanonical nature of such decompositions to limit one-qubit gates appearing in respectivecircuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOTgates. Additionally, our results offer a complete classification of three-qubit diagonaloperators by their CNOT-cost, which holds even if ancilla qubits are available.

Quantum Information and Computation•May 1, 2009•127 citations

Implementation of a three-qubit Toffoli gate in a single step

Ai Min Chen, Sam Young Cho, Mun Dae Kim

Single-step implementations of multiqubit gates are generally believed to provide a simpler design, a faster operation, and a lower decoherence. For three coupled qubits interacting with a photon field, a realizable scheme for a single-step Toffoli gate is investigated. We find that the three-qubit system can be described by four effective modified Jaynes-Cummings models in the states of two control qubits. Within the rotating-wave approximation, the modified Jaynes-Cummings models are shown to be reduced to the conventional Jaynes-Cummings models with renormalized couplings between qubits and photon fields. A single-step Toffoli gate is shown to be realizable with tuning of the four characteristic oscillation periods that satisfy a commensurate condition. Possible values of the system parameters are estimated for a single-step Toffoli gate. Further, we discuss our single-step Toffoli-gate operation errors due to imperfections in the system parameters; numerical calculations show that a Toffoli gate with high fidelity can be obtained by adjusting pairs of the photon-qubit and qubit-qubit coupling strengths. In addition, a decoherence effect on the Toffoli-gate operation due to a thermal reservoir is discussed.

arXiv:1203.0374•Physical Review A•Mar 20, 2012•13 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 canonicity 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•Mar 15, 2008•7 citations
A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate implementation by Margolus is optimal, in the sense that it attains a lower bound of {\em three} controlled-not gates, and subject to that, a sharp lower bound of {\em four} single-qubit gates. We also discuss optimal implementations of other simplified Toffoli gates, and explain why the phase factor −1-1−1 invariably occurs in such implementations.
Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.
This paper considers the method of building the Toffoli Gate based on the Margolus Gate on four or more qubits. In the first part of the considered method, the modification of the Margolus gate on four or more qubits is suggested. In the second part of the method, the modification of the Margolus gate is transformed into the modification of the Toffoli gate implementation using step-by-step phase rotation compensations. The phase rotation compensation for an N-qubit quantum circuit can be performed with N successive steps, where at each step the gates with phase rotation pi/2^(s-1) are added, where s is the step number, starting from one. The compensation phase requires 2 two-qubit gates and 2N-1 one-qubit gates.
The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic oper-ations 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 thefirst demonstration of its CNOT-optimality. We study three-qubit circuits which containless than six CNOT gates and implement a block-diagonal operator, then show that theyimplicitly describe the cosine-sine decomposition of a related operator. Leveraging thecanonical nature of such decompositions to limit one-qubit gates appearing in respectivecircuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOTgates. Additionally, our results offer a complete classification of three-qubit diagonaloperators by their CNOT-cost, which holds even if ancilla qubits are available.
Single-step implementations of multiqubit gates are generally believed to provide a simpler design, a faster operation, and a lower decoherence. For three coupled qubits interacting with a photon field, a realizable scheme for a single-step Toffoli gate is investigated. We find that the three-qubit system can be described by four effective modified Jaynes-Cummings models in the states of two control qubits. Within the rotating-wave approximation, the modified Jaynes-Cummings models are shown to be reduced to the conventional Jaynes-Cummings models with renormalized couplings between qubits and photon fields. A single-step Toffoli gate is shown to be realizable with tuning of the four characteristic oscillation periods that satisfy a commensurate condition. Possible values of the system parameters are estimated for a single-step Toffoli gate. Further, we discuss our single-step Toffoli-gate operation errors due to imperfections in the system parameters; numerical calculations show that a Toffoli gate with high fidelity can be obtained by adjusting pairs of the photon-qubit and qubit-qubit coupling strengths. In addition, a decoherence effect on the Toffoli-gate operation due to a thermal reservoir is discussed.
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 canonicity 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.