CoChat
Sign Up
PreprintCited by 256Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

The DOI matches its DataCite record.

Quantum Algorithm Implementations for Beginners

Open access
J., Abhijith, Adedoyin, Adetokunbo, Ambrosiano, John, Anisimov, Petr, Casper, William, Chennupati, Gopinath, Coffrin, Carleton, Djidjev, Hristo, Gunter, David, Karra, Satish, Lemons, Nathan, Lin, Shizeng, Malyzhenkov, Alexander, Mascarenas, David, Mniszewski, Susan, Nadiga, Balu, O'Malley, Daniel, Oyen, Diane, Pakin, Scott, Prasad, Lakshman, Roberts, Randy, Romero, Phillip, Santhi, Nandakishore, Sinitsyn, Nikolai, Swart, Pieter J., Wendelberger, James G., Yoon, Boram, Zamora, Richard, Zhu, Wei, Eidenbenz, Stephan, Bärtschi, Andreas, Coles, Patrick J., Vuffray, Marc, Lokhov, Andrey Y.·2018·arXiv
DOI 10.48550/arxiv.1804.03719arXiv 1804.03719
Open this paper in CoChat — free accountOpen PDF

Abstract

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims to explain the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM's quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

Overview

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1804.03719

Cites

Statistics

Verification

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.

A few free checks a day · papers already verified open instantly · results are public

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?

  • An established and effective quantum algorithm is available for integer factorization and discrete logarithms, providing remarkable computational speed over the most significant classical algorithm.

    “It can be recalled that an established and effective quantum algorithm is available for problems dealing with integer factorization and discrete logarithms [47], providing remarkable computational speed over the most significant classical algorithm.”

    From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [47]

    Section 5.1 states that Shor’s factoring algorithm runs in polynomial time, while the most efficient known classical factoring algorithm has a much slower running time. The paper also identifies discrete logarithms as an application of quantum hidden-subgroup methods, but our copy does not compare their speed with the best classical discrete-logarithm algorithm. Thus the claimed speed advantage is supported for factoring, not established here for both problems. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • The safety of many internet transactions depends on the theory that factoring integers with a huge number of digits (say, at least a thousand) is almost impossible.

    “As an illustration [47], it may be noted that the safety of many internet transactions depends on the following theory: factoring integers possessing a huge number of digits (say, ≥ thousand) is almost impossible.”

    From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [47]

    Section 5.1 says that difficulty factoring large integers underpins the security of RSA, a widely used public-key cryptosystem. It describes integers of 1,000 or more **bits**, not digits, as impractical to factor with known algorithms and classical hardware; the citing sentence changes that quantitative threshold. (LLM, conf=0.89)

    Experimental — accuracy not yet measured

  • Grover's algorithm is applied to find maximal cliques, finding cycles, and finding triangles in a graph.

    “The algorithm is applied to find maximal cliques, finding cycles, and finding triangles in a graph [47]”

    From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [47]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 127

  1. Scott Aaronson. 2015. Read the fine print. Nature Physics 11, 4 (2015), 291-293.
  2. Scott Aaronson and Lijie Chen. 2017. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference, (CCC'17), July 6-9, 2017, Riga, Latvia (LIPIcs), Ryan O'Donnell (Ed.), Vol. 79. Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 22:1-22:67. DOI: https://doi.org/10. 4230/LIPIcs.CCC.2017.22 · DOI
  3. Andris Ambainis. 2007. Quantum walk algorithm for element distinctness. SIAM Journal on Computing 37, 1 (2007), 210-239.
  4. Andris Ambainis and R. Spalec. 2006. Quantum algorithms for matching and network flows. In Proceedings of the Lecture Notes in Computer Science: STACS 2006 3884 (2006).
  5. Itai Arad and Zeph Landau. 2010. Quantum computation and the evaluation of tensor networks. SIAM Journal on Computing 39, 7 (2010), 3089-3121.
  6. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandr á, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505-510.
  7. Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. 2006. Efficient quantum circuits for Schur and Clebsch-Gordan transforms. Physical Review Letters 97, 17 (2006), 170502.
  8. Dave Bacon and Wim Van Dam. 2010. Recent progress in quantum algorithms. Communications of the ACM 53, 2 (2010), 84-93.
  9. Stefanie Barz, Ivan Kassal, Martin Ringbauer, Yannick Ole Lipp, Borivoje Dakić, Alán Aspuru-Guzik, and Philip Walther. 2014. A two-qubit photonic quantum processor and its application to solving systems of linear equations. Scientific Reports 4, 1 (2014), 1-5.
  10. Robert Beals. 1997. Quantum computation of fourier transforms over symmetric groups . In Proceedings of the STOC (1997), 48-53.
  11. Giuliano Benenti and Giuliano Strini. 2008. Quantum simulation of the single-particle schrödinger equation. Ameri- can Journal of Physics 76, 7 (2008), 657-662.
  12. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and weaknesses of quan- tum computing. SIAM Journal on Computing 26, 5 (1997), 1510-1523. DOI:https://doi.org/10.1137/S0097539796300933 · DOI · Paper page
  13. E. Bernstein and U. Vazirani. 1993. Quantum complexity theory. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing . 11-20. DOI:https://doi.org/10.1145/167088.167097 · DOI · Paper page
  14. Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. 2007. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics 270, 2 (2007), 359-371.
  15. Robin Blume-Kohout. 2010. Hedged maximum likelihood quantum state estimation. Physical Review Letters 105, 20 (2010), 200504.
  16. Robin Blume-Kohout. 2010. Optimal, reliable estimation of quantum states. New Journal of Physics 12, 4 (2010), 043034.
  17. Otakar Borůvka. 1926. O jistém problému minimálním. Práce Mor. Přírodově d. spol. v Brnř (Acta Societ. Scient. Natur. Moravicae) 3 (1926), 37-58.
  18. Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. 1998. Tight bounds on quantum searching. Fortschritte Der Physik: Progress of Physics 46, 4-5 (1998), 493-505.
  19. Lucas T. Brady, Christopher L. Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov. 2021. Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems. Physical Review Letters 126, 7 (2021), 070505. DOI:https://doi.org/10.1103/PhysRevLett.126.070505 · DOI
  20. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. 2002. Quantum amplitude amplification and estimation. Contemporary Mathematics 305 (2002), 53-74.
  21. Carlos Bravo-Prieto, Ryan LaRose, Marco Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J Coles. 2019. Variational quantum linear solver: A hybrid algorithm for linear systems. arXiv:1909.05820. Retrieved from https://arxiv.org/ abs/1909.05820. · arXiv
  22. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 2020. Obstacles to variational quantum op- timization from symmetry protection. Physical Review Letters 125, 26 (2020), 260505. DOI:https://doi.org/10.1103/ PhysRevLett.125.260505 · DOI · Paper page
  23. H. Buhrman and R. Spalek. 2006. Quantum verification of matrix products. In Proceedings of the 17th Annual ACM- SIAM Symposium on Discrete Algorithm (2006), 880-889.
  24. X. -D. Cai, C. Weedbrook, Z. -E. Su, M. -C. Chen, M. Gu, M. -J. Zhu, L. Li, N. -L. Liu, C. -Y. Lu, and J. -W. Pan. 2013. Experimental quantum computing to solve systems of linear equations. Physical Review Letters 110, 23, Article 230501 (June 2013), 230501 pages. DOI:https://doi.org/10.1103/PhysRevLett.110.230501 · DOI · Paper page
  25. Kevin K. H. Cheung and Michele Mosca. 2001. Decomposing finite abelian groups. Quantum Information & Compu- tation 1, 3 (Oct. 2001), 26-32. Retrieved from http://dl.acm.org/citation.cfm?id=2011339.2011341.
  26. Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. 2020. Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension. In Pro- ceedings of the 31st International Symposium on Algorithms and Computation (Leibniz International Proceedings in Informatics (LIPIcs)), Yixin Cao, Siu-Wing Cheng, and Minming Li (Eds.), Vol. 181. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 47:1-47:17. DOI:https://doi.org/10.4230/LIPIcs.ISAAC.2020.47 · DOI
  27. Andrew M. Childs and Wim Van Dam. 2010. Quantum algorithms for algebraic problems. Reviews of Modern Physics 82, 1 (2010), 1.
  28. Lukasz Cincio, Yiğit Subaşı, Andrew T. Sornborger, and Patrick J. Coles. 2018. Learning the quantum algorithm for state overlap. New Journal of Physics 20, 11 (2018), 113022.
  29. Jill Cirasella. 2006. Classical and quantum algorithms for finding cycles. MSc Thesis (2006), 1-58.
  30. Chris Godsil and Hanmeng Zhan. 2019. Discrete-time quantum walks and graph structures. Journal of Combinatorial Theory, Series A 167 (2019), 181-212.
  31. Jeremy Cook, Stephan Eidenbenz, and Andreas Bärtschi. 2020. The quantum alternating operator ansatz on maxi- mum k-vertex cover. In Proceedings of the IEEE International Conference on Quantum Computing & Engineering. 83-92. DOI:https://doi.org/10.1109/QCE49297.2020.00021 · DOI
  32. Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Sym- posium on Theory of Computing . ACM, New York, NY, 151-158. DOI:https://doi.org/10.1145/800157.805047 · DOI · Paper page
  33. D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. Journal of Symbolic Com- putation 9, 3 (1990), 251-280.
  34. Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. 2010. Efficient quantum state tomography. Nature Communications 1 (2010), 149.
  35. Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. 2008. Algorithms. McGraw-Hill, Inc., New York, NY.
  36. M. Dehn. 1911. Über unendliche diskontinuierliche gruppen. Mathematische Annalen 71, 1 (01 Mar 1911), 116-144. DOI: https://doi.org/10.1007/BF01456932 · DOI
  37. D. Deutsch and R. Jozsa. 1992. Rapid solutions of problems by quantum computation. In Proceedings of the of the Royal Society of London A. 439-553.
  38. Simon J. Devitt, William J. Munro, and Kae Nemoto. 2013. Quantum error correction for beginners. Reports on Progress in Physics 76, 7 (2013), 076001.
  39. B. L. Douglas and J. B. Wang. 2009. Efficient quantum circuit implementation of quantum walks. Physical Review A 79, 5 (2009), 052335.
  40. Iain Dunning, Swati Gupta, and John Silberholz. 2018. What works best when? A systematic evaluation of heuristics for max-cut and QUBO. INFORMS Journal on Computing 30, 3 (2018), 608-624. DOI:https://doi.org/10.1287/ijoc.2017. 0798 · DOI · Paper page
  41. Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. 2006. Quantum query complexity of some graph problems. SIAM Journal on Computing 35, 6 (2006), 1310-1328.
  42. Christoph Durr and Peter Hoyer. 1996. A quantum algorithm for finding the minimum. arXiv preprint quant- ph/9607014 (1996).
  43. Jack Edmonds and Richard M. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19 (2) (1972), 248-264.
  44. F. Magniez, A. Nayak, J. Roland, and M. Santha. 2011. Search via quantum walk. SIAM Journal on Computing 40, 1 (2011), 142-164. https://arxiv.org/abs/quant-ph/0608026. · arXiv
  45. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv:1412.6062. Retrieved from https://arxiv.org/abs/1412.6062. · arXiv
  46. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028. · arXiv
  47. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum computation by adiabatic evo- lution. arXiv: quant-ph/0001106. Retrieved from https://arxiv.org/abs/0001106. · arXiv
  48. L. R. Ford and D. R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399-404.
  49. R. Freivalds. 1979. Fast probabilistic algorithms. In Proc. of 8th Symposium on Mathematical Foundations of Computer Science (1979), 57-69.
  50. Silvano Garnerone, Annalisa Marzuoli, and Mario Rasetti. 2009. Efficient quantum processing of three-manifold topological invariants. Advances in Theoretical and Mathematical Physics 13, 6 (2009), 1601-1652.
  51. Iulia M. Georgescu, Sahel Ashhab, and Franco Nori. 2014. Quantum simulation. Reviews of Modern Physics 86, 1 (2014), 153.
  52. Joseph Geraci. 2008. A new connection between quantum circuits, graphs and the ising partition function. Quantum Information Processing 7, 5 (2008), 227-242.
  53. Joseph Geraci and Daniel A. Lidar. 2008. On the exact evaluation of certain instances of the potts partition function by quantum computers. Communications in Mathematical Physics 279, 3 (2008), 735-768.
  54. András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. [n.d.]. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1425- 1444. DOI:https://doi.org/10.1137/1.9781611975482.87 · DOI
  55. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Quantum random access memory. Physical Review Letters 100, 16 (2008), 160501.
  56. Michel X. Goemans and David P. Williamson. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42, 6 (1995), 1115-1145. DOI:https: //doi.org/10.1145/227683.227684 · DOI · Paper page
  57. David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. 2010. Quantum state tomography via compressed sensing. Physical Review Letters 105, 15 (2010), 150401.
  58. Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 212-219.
  59. Eran Halperin, Dror Livnat, and Uri Zwick. 2004. MAX CUT in cubic graphs. Journal of Algorithms 53, 2 (2004), 169-185. DOI:https://doi.org/10.1016/j.jalgor.2004.06.001 · DOI · Paper page
  60. Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O'Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush. 2021. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics 17, 3 (2021), 332-336. DOI:https://doi.org/10.1038/s41567-020-01105-y · DOI · Paper page
  61. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical Review Letters 103, 15 (2009), 150502.
  62. Zdenek Hradil. 1997. Quantum-state estimation. Physical Review A 55, 3 (1997), R1561.
  63. Johan Håstad. 2001. Some optimal inapproximability results. Journal of the ACM 48, 4 (2001), 798-859. DOI:https: //doi.org/10.1145/502090.502098 · DOI · Paper page
  64. Daniel F. V. James, Paul G. Kwiat, William J. Munro, and Andrew G. White. 2001. Measurement of qubits. Physical Review A 64, 5 (2001), 052312.
  65. Sonika Johri, Damian S. Steiger, and Matthias Troyer. 2017. Entanglement spectroscopy on a quantum computer. Physical Review B 96, 19 (2017), 195136.
  66. Stephen P. Jordan. 2009. Fast quantum algorithms for approximating some irreducible representations of groups . (2009), 1-21. arXiv:0811.0562. Retrieved from https://arxiv.org/abs/0811.0562. · arXiv
  67. J. Kempe. 2003. Quantum random walks -an introductory overview. Contemporary Physics 44, 4 (2003), 307-327. Retrieved from http://www.tandfonline.com/doi/abs/10.1080/00107151031000110776. · DOI · Paper page
  68. V. Kendon. 2011. Where to quantum walk. (2011), 1-13. https://arxiv.org/abs/1107.3795. · arXiv
  69. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. 2007. Optimal inapproximability results for MAX-CUT and Other 2-Variable CSPs? SIAM J. Comput. 37, 1 (2007), 319-357. DOI:https://doi.org/10.1137/ S0097539705447372 · DOI
  70. Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press.
  71. M. W. Krentel. 1986. The complexity of optimization problems. In Proceedings of the Eighteenth Annual ACM Sympo- sium on Theory of Computing . ACM, New York, NY, 69-76. DOI:https://doi.org/10.1145/12130.12138 · DOI
  72. Thaddeus D. Ladd, Fedor Jelezko, Raymond Laflamme, Yasunobu Nakamura, Christopher Monroe, and Jeremy Lloyd O'Brien. 2010. Quantum computers. Nature 464, 7285 (2010), 45.
  73. R. LaRose, A. Tikku, É. O'Neel-Judy, L. Cincio, and P. J. Coles. 2019. Variational quantum state diagonalization. npj Quantum Information 5, 1 (2019), 57. DOI:https://doi.org/10.1038/s41534-019-0167-6 · DOI · Paper page
  74. Richard J. Lipton and Kenneth W. Regan. 2014. Quantum Algorithms via Linear Algebra: A Primer. MIT Press.
  75. Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. 2015. Quantum algorithms for topological and geometric analysis of data. Nature Communications 7, 1 (2015), 1-7. DOI:https://doi.org/10.1038/ncomms10138 · DOI · Paper page
  76. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411. Retrieved from https://arxiv.org/abs/1307.0411. · arXiv
  77. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2014. Quantum principal component analysis. Nature Physics 10, 9 (2014), 631-633. https://doi.org/10.1038/nphys3029 · DOI · Paper page
  78. Neil B. Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, and Viv Kendon. 2010. Universal quantum compu- tation using the discrete-time quantum walk. Physical Review A 81, 4 (2010), 042330.
  79. Frederic Magniez, Miklos Santha, and Mario Szegedy. 2007. Quantum algorithms for the triangle problem. SIAM Journal on Computing 37, 2 (2007), 413-424.
  80. Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L O'brien. 2012. Experimental realization of Shor's quantum factoring algorithm using qubit recycling. Nature Photonics 6, 11 (2012), 773-776.
  81. Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. 2016. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics 18, 2 (2016), 023023.
  82. Ashley Montanaro. 2016. Quantum algorithms: An overview. npj Quantum Information 2, 1 (2016), 15023.
  83. Michele Mosca. 2012. Quantum algorithms. In Proceedings of the Computational Complexity. Springer, 2303-2333.
  84. Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information. Cambridge Univer- sity Press, Cambridge, United Kingdom. 10th Anniversary Edition.
  85. Bryan O'Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley. 2019. Generalized swap networks for near-term quantum computing. arXiv:1905.05118. Retrieved from https://arxiv.org/abs/1905.05118. · arXiv
  86. Brian Olson, Irina Hashmi, Kevin Molloy, and Amarda Shehu. 2012. Basin hopping as a general and versatile opti- mization framework for the characterization of biological macromolecules. Advances in Artificial Intelligence 2012 (2012), 674832. DOI:https://doi.org/10.1155/2012/674832 · DOI
  87. Karl Pearson. 1901. On lines and planes of closest fit to systems of points in space. Philosophical Magazine Series 6 2, 11 (1901), 559-572. DOI:https://doi.org/10.1080/14786440109462720 · DOI
  88. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature Communica- tions 5 (July 2014), 5213. DOI:https://doi.org/10.1038/ncomms5213 · DOI · Paper page
  89. Martin Plesch and Časlav Brukner. 2011. Quantum-state preparation with universal gate decompositions. Physical Review A 83, 3 (2011), 032302.
  90. Martin Plesch and Časlav Brukner. 2011. Quantum-state preparation with universal gate decompositions. Physical Review A 83, 3 (2011), 032302. DOI:https://doi.org/10.1103/PhysRevA.83.032302 · DOI
  91. Carl Pomerance. 1996. A tale of two sieves. Notices of the American Mathematical Society 43, 12 (1996), 1473-1485.
  92. John Preskill. 2020. Quantum computing and the entanglement frontier. Rapporteur Talk at the 25th Solvay Conference on Physics, 19-22 October 2011 (2020).
  93. Bo Qi, Zhibo Hou, Li Li, Daoyi Dong, Guoyong Xiang, and Guangcan Guo. 2013. Quantum state tomography via linear regression estimation. Scientific Reports 3, 1 (2013), 1-6.
  94. Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. 2014. Quantum support vector machine for big data classifica- tion. Physical Review Letters 113, 13 (2014), 130503.
  95. Eleanor G. Rieffel and Wolfgang H. Polak. 2011. Quantum computing: A gentle introduction. MIT Press.
  96. R. L. Rivest, A. Shamir, and L. Adleman. 1978. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 2 (Feb. 1978), 120-126. DOI:https://doi.org/10.1145/359340.359342 · DOI · Paper page
  97. Mehdi Saeedi and Igor L. Markov. 2013. Synthesis and optimization of reversible circuits -a survey. ACM Computing Surveys (CSUR) 45, 2 (2013), 21.
  98. Miklos Santha. 2008. Quantum walk based search algorithms. In International Conference on Theory and Applications of Models of Computation. Springer, 31-46.
  99. Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. 2015. An introduction to quantum machine learning. Con- temporary Physics 56, 2 (2015), 172-185.
  100. Jiangwei Shang, Zhengyun Zhang, and Hui Khoon Ng. 2017. Superfast maximum-likelihood reconstruction for quan- tum tomography. Physical Review A 95, 6 (2017), 062336.
  101. Vivek V. Shende and Igor L. Markov. 2009. On the CNOT-cost of TOFFOLI gates. Quantum Information & Computa- tion 9, 5-6 (2009), 461-486.
  102. Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock. 2004. Minimal universal two-qubit controlled-NOT-based circuits. Physical Review A 69, 6 (2004), 062321.
  103. Neil Shenvi, Julia Kempe, and K. Birgitta Whaley. 2003. Quantum random-walk search algorithm. Physical Review A 67, 5 (2003), 052307.
  104. Peter W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science . IEEE, 124-134. DOI:https://doi.org/10.1109/SFCS. 1994.365700 · DOI · Paper page
  105. Peter W. Shor. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum com- puter. SIAM Journal on Computing 26, 5 (1997), 1484-1509. DOI:https://doi.org/10.1137/S0097539795293172 · DOI · Paper page
  106. Nikolai A. Sinitsyn. 2018. Computing with a single qubit faster than the computation quantum speed limit. Physics Letters A 382, 7 (2018), 477-481.
  107. Robert S. Smith, Michael J. Curtis, and William J. Zeng. 2016. A Practical Quantum Instruction Set Architecture. arXiv:1608.03355. Retrieved from https://arxiv.org/abs/1608.03355. · arXiv
  108. John A. Smolin, Jay M. Gambetta, and Graeme Smith. 2012. Efficient method for computing the maximum-likelihood quantum state from measurements with additive gaussian noise. Physical Review Letters 108, 7 (2012), 070502.
  109. Rolando D. Somma. 2016. Quantum simulations of one dimensional quantum systems. Quantum Information & Com- putation 16, 13-14 (2016), 1125-1168.
  110. V. Strassen. 1969. Gaussian elimination is not optimal. Numerische Mathematik 13 (1969), 354-356.
  111. Yiğit Subaşı, Rolando D. Somma, and Davide Orsucci. 2019. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Physical Review Letters 122, 6 (2019), 060504.
  112. J. A. K. Suykens and J. Vandewalle. 1999. Least squares support vector machine classifiers. Neural Processing Letters 9, 3 (June 1999), 293-300. DOI:https://doi.org/10.1023/A:1018628609742 · DOI
  113. Mario Szegedy. 2004. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 32-41.
  114. Maika Takita, Antonio D. Córcoles, Easwar Magesan, Baleegh Abdo, Markus Brink, Andrew Cross, Jerry M. Chow, and Jay M. Gambetta. 2016. Demonstration of weight-four parity measurements in the surface code architecture. Physical Review Letters 117, 21 (2016), 210505.
  115. Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo. 2018. Neural-network quantum state tomography. Nature Physics 14, 5 (2018), 447.
  116. L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang. 2001. Experimental realization of shor's quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 6866 (Dec. 2001), 883-887. DOI:https://doi.org/10.1038/414883a · DOI · Paper page
  117. Guifré Vidal. 2003. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters 91, 14 (2003), 147902.
  118. Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. 2018. Quantum approximate optimization algo- rithm for MaxCut: A fermionic view. Physical Review A 97, 2 (2018), 022304. DOI:https://doi.org/10.1103/PhysRevA. 97.022304 · DOI · Paper page
  119. Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. 2020. X Y mixers: Analytical and numerical results for the quantum alternating operator ansatz. Physical Review A 101, 1 (2020), 012320. DOI:https://doi.org/10. 1103/PhysRevA.101.012320 · DOI · Paper page
  120. Chu Ryang Wie. 2017. A Quantum Circuit to Construct All Maximal Cliques Using Grover Search Algorithm. arXiv preprint arXiv:1711.06146. · arXiv
  121. James R. Wootton. 2017. Demonstrating non-abelian braiding of surface code defects in a five qubit experiment. Quantum Science and Technology 2, 1 (2017), 015006.
  122. James R. Wootton. 2020. Benchmarking near-term devices with quantum error correction. Quantum Science and Technology 5, 4 (2020), 044004.
  123. James R. Wootton and Daniel Loss. 2018. Repetition code of 15 qubits. Physical Review A 97, 5 (2018), 052313.
  124. Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. 2017. Optimizing varia- tional quantum algorithms using pontryagin's minimum principle. Physical Review X 7, 2 (2017), 021027. DOI:https: //doi.org/10.1103/physrevx.7.021027 · DOI · Paper page
  125. Noson S. Yanofsky and Mirco A. Mannucci. 2008. Quantum computing for computer scientists. Cambridge University Press.
  126. Yarui Zheng, Chao Song, Ming-Cheng Chen, Benxiang Xia, Wuxin Liu, Qiujiang Guo, Libo Zhang, Da Xu, Hui Deng, Keqiang Huang, et al. 2017. Solving systems of linear equations with a superconducting quantum processor. Physical Review Letters 118, 21 (2017), 210504.
  127. Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. 2020. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X 10, 2 (2020), 021067.

Cited by

Sorted by citations

Metadata

Authors
J., A., Adedoyin, A., Ambrosiano, J., Anisimov, P., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H., Gunter, D., Karra, S., Lemons, N., Lin, S., Malyzhenkov, A., Mascarenas, D., Mniszewski, S., Nadiga, B., O'Malley, D., Oyen, D., Pakin, S., Prasad, L., Roberts, R., Romero, P., Santhi, N., Sinitsyn, N., Swart, P. J., Wendelberger, J. G., Yoon, B., Zamora, R., Zhu, W., Eidenbenz, S., Bärtschi, A., Coles, P. J., Vuffray, M., & Lokhov, A. Y.
Affiliations
Los Alamos National Laboratory (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
3
Issue
4
Pages
1-92
ISSN
2643-6809 (ISSN-L)
DOI
10.48550/arxiv.1804.03719
arXiv
1804.03719
OpenAlex
W4220663753
Cited by
256
References
0
Citations by year
2026: 11 · 2025: 29 · 2024: 40 · 2023: 33 · 2022: 36 · 2021: 44 · 2020: 36 · 2019: 21 · 2018: 6
FWCI
11.31
Type
journal article
Language
en
Open access
Licence
Locations
  • ACM Transactions on Quantum Computing (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Department of Energy (#89233218CNA000001)
  • National Nuclear Security Administration (89233218C-NA000001)
  • Los Alamos National Laboratory (89233218CNA 000001)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
quantum algorithms, quantum programming, quantum computing hardware, IBM quantum hardware, quantum simulation, algorithm implementation, qubits

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