article

Optimal realizations of simplified Toffoli gates

Authors:

Guang Song,

Andreas KlappeneckerAuthors Info & Claims

Quantum Information & Computation, Volume 4, Issue 5

Pages 361 - 372

Published: 01 September 2004 Publication History

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 three controlled-not gates, and subject to that, a sharp lower bound of 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.

References

[1]

Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52:3457-3467, 1995.

Crossref

Google Scholar

[2]

David P. DiVincenzo and John A. Smolin. Results on two-bit gate design for quantum computers. In Proceedings of Workshop on Physics and Computation (PhysComp '94), pages 14-23, 1994.

Google Scholar

[3]

D.P. DiVincenzo. Quantum gates and circuits. Proc. R. Soc. Lond. A, 454:261-276, 1998.

Crossref

Google Scholar

[4]

N. Margolus. Universal cellular automata based on the collisions of soft spheres. In A. Adamatzky, editor, Collision Based Computation, page 107. Springer-Verlag, 2002.

Crossref

Google Scholar

[5]

N. Margolus. Simple qualltum gates. Uupublished malmscript, about 1994.

Google Scholar

[6]

G. Song and A. Klappcnccker. Optimal realizations of controlled unitary gates. Journal of Quantum Information and Computation, 3(2):139-156, 2003.

Digital Library

Google Scholar

Cited By

View all

Yeh Lvan de Wetering J(2022)Constructing All Qutrit Controlled Clifford+T gates in Clifford+TReversible Computation10.1007/978-3-031-09005-9_3(28-50)Online publication date: 5-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-09005-9_3
Zhang KRao PYu KLim HKorepin V(2021)Implementation of efficient quantum search algorithms on NISQ computersQuantum Information Processing10.1007/s11128-021-03165-220:7Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s11128-021-03165-2
Viamontes GMarkov IHayes JGielen G(2007)Checking equivalence of quantum circuits and statesProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326089(69-74)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326089

Recommendations

Optimal realizations of controlled unitary gates

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 ...
Pairwise decomposition of toffoli gates in a quantum circuit
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are ...
An arbitrary twoqubit computation In 23 elementary gates or less
DAC '03: Proceedings of the 40th annual Design Automation Conference

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Quantum Information & Computation Volume 4, Issue 5

September 2004

84 pages

ISSN:1533-7146

Issue’s Table of Contents

Publisher

Rinton Press, Incorporated

Paramus, NJ

Publication History

Published: 01 September 2004

Revised: 30 August 2004

Received: 31 December 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yeh Lvan de Wetering J(2022)Constructing All Qutrit Controlled Clifford+T gates in Clifford+TReversible Computation10.1007/978-3-031-09005-9_3(28-50)Online publication date: 5-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-09005-9_3
Zhang KRao PYu KLim HKorepin V(2021)Implementation of efficient quantum search algorithms on NISQ computersQuantum Information Processing10.1007/s11128-021-03165-220:7Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s11128-021-03165-2
Viamontes GMarkov IHayes JGielen G(2007)Checking equivalence of quantum circuits and statesProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326089(69-74)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326089

Abstract

References

Cited By

Recommendations

Optimal realizations of controlled unitary gates

Pairwise decomposition of toffoli gates in a quantum circuit

An arbitrary twoqubit computation In 23 elementary gates or less

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations