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• 19 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•11 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•27 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.

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

Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization

Dmitri A Maslov

Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over the regular Toffoli gate is its smaller circuit size. However, its use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative-phase deviations would prevent the relative-phase Toffoli gates from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative-phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the controlled-not count, $T$count, as well as the number of ancillae used. We suggest that a further study of the relative-phase Toffoli implementations and their use may yield other optimizations.

arXiv:1508.03273•Physical Review A•Feb 10, 2016•218 citations

Efficient Toffoli gates using qudits

Timothy C. Ralph, Kevin J. Resch, Alexei Gilchrist

The simplest decomposition of a Toffoli gate acting on 3 qubits requires five 2-qubit gates. If we restrict ourselves to controlled-sign (or controlled-NOT) gates this number climbs to 6. We show that the number of controlled-sign gates required to implement a Toffoli gate can be reduced to just 3 if one of the three quantum systems has a third state that is accessible during the computation---i.e., is actually a qutrit. Such a requirement is not unreasonable or even atypical since we often artificially enforce a qubit structure on multilevel quantums systems (e.g., atoms, photonic polarization plus spatial modes). We explore the implementation of these techniques in optical quantum processing and show that linear optical circuits could operate with much higher probabilities of success.

arXiv:0806.0654•Physical Review A•Feb 16, 2007•301 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.
Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over the regular Toffoli gate is its smaller circuit size. However, its use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative-phase deviations would prevent the relative-phase Toffoli gates from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative-phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the controlled-not count, TTTcount, as well as the number of ancillae used. We suggest that a further study of the relative-phase Toffoli implementations and their use may yield other optimizations.
The simplest decomposition of a Toffoli gate acting on 3 qubits requires five 2-qubit gates. If we restrict ourselves to controlled-sign (or controlled-NOT) gates this number climbs to 6. We show that the number of controlled-sign gates required to implement a Toffoli gate can be reduced to just 3 if one of the three quantum systems has a third state that is accessible during the computation---i.e., is actually a qutrit. Such a requirement is not unreasonable or even atypical since we often artificially enforce a qubit structure on multilevel quantums systems (e.g., atoms, photonic polarization plus spatial modes). We explore the implementation of these techniques in optical quantum processing and show that linear optical circuits could operate with much higher probabilities of success.