Five two-qubit gates are necessary for implementing the Toffoli gate
Open accessAbstract
In this Rapid Communication, we consider the open problem of the minimum cost of two-qubit gates for simulating the Toffoli gate and show that five two-qubit gates are necessary. Before our work, it was known that five two-qubit gates are sufficient to implement the Toffoli gate, and numerical evidence indicates that five two-qubit gates are also necessary. The idea introduced here can also be used to solve the problem of optimal simulation of Deutsch three-qubit gates.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Five two-qubit gates are necessary for 2-controlled phase shift gates.
“Since 5 two-qubit gates are necessary for 2-controlled phase shift gates [62], this decomposition is essentially optimal.”
From High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices (2023) · cites this paper as [62]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 20,449 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691 · see citing works
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270 · see citing works
Demonstration of two-qubit algorithms with a superconducting quantum processor
DiCarlo, L., Chow, J. M., Gambetta, J., Bishop, L. S., Johnson, B., Schuster, D., Majer, J., Blais, A., Frunzio, L., Girvin, S. M., et al. (2009) · Nature · doi:10.1038/nature08121 · Cited by 1,158 · see citing works
Simplifying quantum logic using higher-dimensional Hilbert spaces
Lanyon, B. P., Barbieri, M., de Almeida, M. P., Jennewein, T. D., Ralph, T. C., Resch, K. J., Pryde, G. J., O’Brien, J. L., Gilchrist, A., & White, A. G. (2008) · Nature Physics · doi:10.1038/nphys1150 · Cited by 739 · see citing works
Almost Any Quantum Logic Gate is Universal
Lloyd, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.346 · Cited by 690 · see citing works
Experimental Quantum Error Correction
Cory, D. G., Price, M. D., Maas, W., Knill, E., Laflamme, R., Zurek, W. H., Havel, T. F., & Somaroo, S. S. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.2152 · Cited by 581 · see citing works
Realization of three-qubit quantum error correction with superconducting circuits
Reed, M. D., DiCarlo, L., Nigg, S. E., Sun, L., Frunzio, L., Girvin, S. M., & Schoelkopf, R. J. (2012) · Nature · doi:10.1038/nature10786 · Cited by 577 · see citing works
Quantum Computation as Geometry
Nielsen, M. A., Dowling, M. R., Gu, M., & Doherty, A. C. (2006) · Science · doi:10.1126/science.1121541 · Cited by 539 · see citing works
Realization of quantum error correction
Chiaverini, J., Leibfried, D., Schaetz, T., Barrett, M. D., Blakestad, R. B., Britton, J., Itano, W. M., Jost, J. D., Knill, E., Langer, C., et al. (2004) · Nature · doi:10.1038/nature03074 · Cited by 517 · see citing works
Realizable Universal Quantum Logic Gates
Sleator, T., & Weinfurter, H. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4087 · Cited by 515 · see citing works
Optimal creation of entanglement using a two-qubit gate
Kraus, B., & Cirac, J. I. (2001) · Physical Review A · doi:10.1103/physreva.63.062309 · Cited by 432 · see citing works
Implementation of a Toffoli gate with superconducting circuits
Fedorov, A., Steffen, L., Baur, M., Silva, M. P. D., & Wallraff, A. J. (2011) · Nature · doi:10.1038/nature10713 · Cited by 383 · see citing works
Realization of the Quantum Toffoli Gate with Trapped Ions
Monz, T., Kim, K., Hänsel, W., Riebe, M., Villar, A. S., Schindler, P., Chwalla, M., Hennrich, M., & Blatt, R. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.040501 · Cited by 337 · see citing works
Implementing the Quantum von Neumann Architecture with Superconducting Circuits
Mariantoni, M., Wang, H., Yamamoto, T., Neeley, M., Bialczak, R. C., Chen, Y., Lenander, M., Lucero, E. A., O’Connell, A. D., Sank, D., et al. (2011) · Science · doi:10.1126/science.1208517 · Cited by 315 · see citing works
Efficient Toffoli gates using qudits
Ralph, T. C., Resch, K. J., & Gilchrist, A. (2007) · Physical Review A · doi:10.1103/physreva.75.022313 · Cited by 293 · see citing works
Practical Scheme for Quantum Computation with Any Two-Qubit Entangling Gate
Bremner, M. J., Dawson, C. M., Dodd, J. L., Gilchrist, A., Harrow, A. W., Mortimer, D., Nielsen, M. A., & Osborne, T. J. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.247902 · Cited by 292 · see citing works
Simulation of Topological Field Theories¶by Quantum Computers
Freedman, M. H., Kitaev, A., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200635 · Cited by 274 · see citing works
Benchmarking Quantum Computers: The Five-Qubit Error Correcting Code
Knill, E. H., Laflamme, R., Martínez, R., & Negrevergne, C. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5811 · Cited by 215 · see citing works
Divincenzo, D. P. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0159 · Cited by 175 · see citing works
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Hallgren, S. (2007) · Journal of the ACM · doi:10.1145/1206035.1206039 · Cited by 143 · see citing works
Automata, Languages and Programming
(1974) · Lecture notes in computer science · doi:10.1007/3-540-06841-4 · Cited by 138 · see citing works
Improved quantum cost for n -bit Toffoli gates
Maslov, D. A., & Dueck, G. W. (2003) · Electronics Letters · doi:10.1049/el:20031202 · Cited by 137 · see citing works
Physical optimization of quantum error correction circuits
Burkard, G., Loss, D., Divincenzo, D. P., & Smolin, J. A. (1999) · Physical review. B, Condensed matter · doi:10.1103/physrevb.60.11404 · Cited by 106 · see citing works
Demonstration of quantum error correction using linear optics
Pittman, T. B., Jacobs, B. C., & Franson, J. D. (2005) · Physical Review A · doi:10.1103/physreva.71.052332 · Cited by 82 · see citing works
Minimum Construction of Two-Qubit Quantum Operations
Zhang, J., Vala, J., Sastry, S., & Whaley, K. B. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.020502 · Cited by 69 · see citing works
Exact Two-Qubit Universal Quantum Circuit
Zhang, J., Vala, J., Sastry, S., & Whaley, K. B. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.027903 · Cited by 68 · see citing works
Daskin, A., & Kais, S. (2011) · The Journal of Chemical Physics · doi:10.1063/1.3575402 · Cited by 60 · see citing works
Simple Realization of the Fredkin Gate using a Series Of Two-Body Operators
Chau, H. F., & Wilczek, F. A. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.748 · Cited by 57 · see citing works
Aoki, T., Shinohara, K., & Morinaga, A. (2001) · Physical Review A · doi:10.1103/physreva.63.063611 · Cited by 19 · see citing works
Flagged first, then by citations
Research works printed but not linked: 7
- A. M. Childs et al., in Proceedings of the 35th ACM Symposium on the Theory of Computing (STOC 2003) (ACM, New York, 2003), pp. 59-68.
- D. P. DiVincenzo and J. A. Smolin, in Proceedings of the Workshop on Physics and Computation: Physcomp '94 (Dallas, Texas, 1994).
- Y. Shi, Quantum Inf. Comput. 3, 1 (2003).
- G. Song and A. Klappenecker, Quantum Inf. Comput. 4, 5 (2004).
- V. V. Shende and I. L. Markov, Quantum Inf. Comput. 9, 5 (2009).
- C. Moraga, Facta universitatis -series: Electronics and Energet- ics 2011, vol. 24, br. 3, str. 423-435.
- N. Yu and M. Ying, arXiv:1301.3727. · arXiv
Cited by
Sorted by citations
High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00064 · Cited by 15 · see citing works
Quantum computation of eigenvalues within target intervals
Jensen, P. W. K., Kristensen, L. B., Kottmann, J. S., & Aspuru-Guzik, A. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abc096 · Cited by 13 · see citing works
- Authors
- Yu, N., Duan, R., & Ying, M.
- Affiliations
- University of Technology Sydney (AU)
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2013-07-30
- Volume
- 88
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W1994839488
- Cited by
- 77
- References
- 32
- Citations by year
- 2026: 8 · 2025: 10 · 2024: 10 · 2023: 6 · 2022: 8 · 2021: 5 · 2020: 7 · 2019: 3 · 2018: 2 · 2017: 2 · 2016: 8 · 2015: 7 · 2014: 1
- FWCI
- 5.90
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- UTS ePRESS (University of Technology Sydney) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Natural Science Foundation of China (61179030)
- Chinese Academy of Sciences
- Australian Research Council (DP120103776, FT120100449, DP110103473)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Quantum-Dot Cellular Automata
- Keywords
- Toffoli gate, two-qubit gates, gate decomposition, quantum circuit simulation, lower bounds
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
