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:quant-ph/0312225

The simplified Toffoli gate implementation by Margolus is optimal

Guang Song, Andreas Klappenecker

Published Dec 31, 2003• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0312225

Related papers

Optimal realizations of simplified Toffoli gates

Guang Song, Andreas Klappenecker

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.

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

Optimal realizations of controlled unitary gates

Guang Song, Andreas Klappenecker

The controlled-not gate and the single qubit gates are considered elementary gates in quantum computing. It is natural to ask how many such elementary gates are needed to implement more elaborate gates or circuits. Recall that a controlled-U gate can be realized with two controlled-not gates and four single qubit gates. We prove that this implementation is optimal if and only if the matrix U satisfies the conditions trU\neq 0, tr(UX)\neq 0, and detU\neq 1. We also derive optimal implementations in the remaining non-generic cases. realizations of controlled unitary gates (pp139-155) G. Song and A. Klappenecker The controlled-not gate and the single qubit gates are considered elementary gates in quantum computing. It is natural to ask how many such elementary gates are needed to implement more elaborate gates or circuits. Recall that a controlled-U gate can be realized with two controlled-not gates and four single qubit gates. We prove that this implementation is optimal if and only if the matrix U satisfies the conditions trU\neq 0, tr(UX)\neq 0, and detU\neq 1. We also derive optimal implementations in the remaining non-generic cases.

arXiv:quant-ph/0207157•Quantum Information and Computation•Mar 1, 2003•28 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 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.

Quantum Information and Computation•May 1, 2009•99 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

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
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.
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.
The controlled-not gate and the single qubit gates are considered elementary gates in quantum computing. It is natural to ask how many such elementary gates are needed to implement more elaborate gates or circuits. Recall that a controlled-U gate can be realized with two controlled-not gates and four single qubit gates. We prove that this implementation is optimal if and only if the matrix U satisfies the conditions trU\neq 0, tr(UX)\neq 0, and detU\neq 1. We also derive optimal implementations in the remaining non-generic cases. realizations of controlled unitary gates (pp139-155) G. Song and A. Klappenecker The controlled-not gate and the single qubit gates are considered elementary gates in quantum computing. It is natural to ask how many such elementary gates are needed to implement more elaborate gates or circuits. Recall that a controlled-U gate can be realized with two controlled-not gates and four single qubit gates. We prove that this implementation is optimal if and only if the matrix U satisfies the conditions trU\neq 0, tr(UX)\neq 0, and detU\neq 1. We also derive optimal implementations in the remaining non-generic cases.
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 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.
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.
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.