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• 11 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

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•19 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

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•14 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

Optimal simulation of three-qubit gates

Nengkun Yu, Mingsheng Ying

In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary $u$ on the target qubit only if both the states of the control are $\ket{1}$. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of $u$ is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.

arXiv:1301.3727•Jan 16, 2013•7 citations

Efficient Decomposition of Quantum Gates

Juha J. Vartiainen, Mikko Möttönen, Martti M. Salomaa

Optimal implementation of quantum gates is crucial for designing a quantum computer. We consider the matrix representation of an arbitrary multiqubit gate. By ordering the basis vectors using the Gray code, we construct the quantum circuit which is optimal in the sense of fully controlled single-qubit gates and yet is equivalent with the multiqubit gate. In the second step of the optimization, superfluous control bits are eliminated, which eventually results in a smaller total number of the elementary gates. In our scheme the number of controlled NOT gates is O(4(n)) which coincides with the theoretical lower bound.

arXiv:quant-ph/0312218•Physical Review Letters•Apr 29, 2004•256 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.
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.
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.
In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary uuu on the target qubit only if both the states of the control are ∣1⟩\ket{1}∣1⟩. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of uuu is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.
Optimal implementation of quantum gates is crucial for designing a quantum computer. We consider the matrix representation of an arbitrary multiqubit gate. By ordering the basis vectors using the Gray code, we construct the quantum circuit which is optimal in the sense of fully controlled single-qubit gates and yet is equivalent with the multiqubit gate. In the second step of the optimization, superfluous control bits are eliminated, which eventually results in a smaller total number of the elementary gates. In our scheme the number of controlled NOT gates is O(4(n)) which coincides with the theoretical lower bound.