https://dl.acm.org/doi/10.1145/3517340 ACM Digital Library home ACM home * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search ACM Transactions on Quantum Computing * Journal Home * Just Accepted * Latest Issue * * Archive * Authors + Author Guidelines + Calls for Papers + Submission Site + ACM Author Policies * Editors + Editorial Board + Associate Editor Guidelines + Associate Editors Welcome Video * Reviewers + Reviewer Guidelines * About + Charter + Abstracting/Indexing + TQC Author List + TQC Affiliations + ACM Award Winners * Contact Us * More HomeACM JournalsACM Transactions on Quantum ComputingJust Accepted Quantum Algorithm Implementations for Beginners review-article Free Access Share on Quantum Algorithm Implementations for Beginners Just Accepted * Authors: * Abhijith J. Search about this author , * Adetokunbo Adedoyin Search about this author , * John Ambrosiano Search about this author , * Petr Anisimov Search about this author , * William Casper Search about this author , * Gopinath Chennupati Search about this author , * Carleton Coffrin Search about this author , * Hristo Djidjev Search about this author , * David Gunter Search about this author , * Satish Karra Search about this author , * Nathan Lemons Search about this author , * Shizeng Lin Search about this author , * Alexander Malyzhenkov Search about this author , * David Mascarenas Search about this author , * Susan Mniszewski Search about this author , * Balu Nadiga Search about this author , * Daniel O'Malley Search about this author , * Diane Oyen Search about this author , * Scott Pakin Search about this author , * Lakshman Prasad Search about this author , * Randy Roberts Search about this author , * Phillip Romero Search about this author , * Nandakishore Santhi Search about this author , * Nikolai Sinitsyn Search about this author , * Pieter J. Swart Search about this author , * James G. Wendelberger Search about this author , * Boram Yoon Search about this author , * Richard Zamora Search about this author , * Wei Zhu Search about this author , * Stephan Eidenbenz Search about this author , * Andreas Bartschi Search about this author , * Patrick J. Coles Search about this author , * Marc Vuffray Search about this author , * Andrey Y. Lokhov Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA Search about this author Authors Info & Claims ACM Transactions on Quantum ComputingAccepted on February 2022 https: //doi.org/10.1145/3517340 Online:28 March 2022Publication History * 0citation * 291 * Downloads Metrics Total Citations0 Total Downloads291 Last 12 Months291 Last 6 weeks235 * * Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account * Save to Binder Save to Binder [loader] Create a New Binder Name [ ] + Cancel + Create * Export Citation * Publisher Site * * eReader * PDF ACM Transactions on Quantum Computing Just Accepted PreviousArticleNextArticle ACM Digital Library 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. References 1. [n.d.]. ibmq-device-information. https://github.com/Qiskit/ ibmq-device-information/tree/master/backends/tenerife/V1. Accessed: 14-12-2019.Google ScholarGoogle Scholar 2. Scott Aaronson. 2015. Read the fine print. Nature Physics 11, 4 (2015), 291-293.Google ScholarGoogle ScholarCross RefCross Ref 3. Scott Aaronson and Lijie Chen. 2017. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia(LIPIcs, Vol. 79), Ryan O'Donnell (Ed.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 22:1-22:67. https:// doi.org/10.4230/LIPIcs.CCC.2017.22Google ScholarGoogle Scholar 4. Hector Abraham, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz...., and yotamvakninibm. 2019. Qiskit: An Open-source Framework for Quantum Computing. https://doi.org/10.5281/zenodo.2562110Google ScholarGoogle Scholar 5. Andris Ambainis. 2007. Quantum walk algorithm for element distinctness. SIAM J. Comput. 37, 1 (2007), 210-239.Google ScholarGoogle ScholarDigital LibraryDigital Library 6. A. Ambainis, H. Buhrman, P. Hoyer, M. Karpinski, and P. Kurur. 2002. Quantum matrix verification. (2002).Google ScholarGoogle Scholar 7. Andris Ambainis and R. Spalec. 2006. Quantum Algorithms for Matching and Network Flows. in Lecture Notes in Computer Science: STACS 2006 3884 (2006).Google ScholarGoogle Scholar 8. Itai Arad and Zeph Landau. 2010. Quantum computation and the evaluation of tensor networks. SIAM J. Comput. 39, 7 (2010), 3089-3121.Google ScholarGoogle ScholarDigital LibraryDigital Library 9. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505-510.Google ScholarGoogle Scholar 10. Dave Bacon, Isaac L Chuang, and Aram W Harrow. 2007. The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits. (2007), 1235-1244.Google ScholarGoogle Scholar 11. Dave Bacon and Wim Van Dam. 2010. Recent progress in quantum algorithms. Commun. ACM 53, 2 (2010), 84-93.Google ScholarGoogle ScholarDigital LibraryDigital Library 12. Stefanie Barz, Ivan Kassal, Martin Ringbauer, Yannick Ole Lipp, Borivoje Dakic, Alan Aspuru-Guzik, and Philip Walther. 2014. A two-qubit photonic quantum processor and its application to solving systems of linear equations. Scientific reports 4(2014). Google ScholarGoogle Scholar 13. Robert Beals. 1997. Quantum computation of Fourier transforms over symmetric groups. In Proceedings of STOC(1997), 48-53.Google ScholarGoogle Scholar 14. Giuliano Benenti and Giuliano Strini. 2008. Quantum simulation of the single-particle Schrodinger equation. American Journal of Physics 76, 7 (2008), 657-662.Google ScholarGoogle ScholarCross RefCross Ref 15. Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM journal on Computing 26, 5 (1997), 1510-1523. https:// doi.org/10.1137/S0097539796300933Google ScholarGoogle Scholar Digital LibraryDigital Library 16. E. Bernstein and U. Vazirani. 1993. Quantum complexity theory. In Proc. of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC '93). 11-20. DOI: 10.1145/167088.167097.Google ScholarGoogle ScholarDigital LibraryDigital Library 17. 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.Google ScholarGoogle ScholarCross RefCross Ref 18. Robin Blume-Kohout. 2010a. Hedged maximum likelihood quantum state estimation. Physical review letters 105, 20 (2010), 200504. Google ScholarGoogle Scholar 19. Robin Blume-Kohout. 2010b. Optimal, reliable estimation of quantum states. New Journal of Physics 12, 4 (2010), 043034. Google ScholarGoogle ScholarCross RefCross Ref 20. Otakar Boruvka. 1926. O jistem problemu minimalnim. Prace Mor. Prirodove d. spol. v Brnr (Acta Societ. Scient. Natur. Moravicae) 3 (1926), 37-58.Google ScholarGoogle Scholar 21. Michel Boyer, Gilles Brassard, Peter Hoyer, and Alain Tapp. 1998. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics 46, 4-5 (1998), 493-505.Google ScholarGoogle ScholarCross RefCross Ref 22. 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 (2021), 070505. Issue 7. https://doi.org/10.1103/PhysRevLett.126.070505Google ScholarGoogle Scholar 23. G. Brassard et al. 2002. Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information 9 (2002). Google ScholarGoogle Scholar 24. 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 preprint arXiv:1909.05820(2019).Google ScholarGoogle Scholar 25. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 2020. Obstacles to Variational Quantum Optimization from Symmetry Protection. Physical Review Letters 125 (2020), 260505. Issue 26. https://doi.org/10.1103/PhysRevLett.125.260505Google Scholar Google Scholar 26. H. Buhrman and R. Spalek. 2006. Quantum verification of matrix products. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (2006), 880-889.Google Scholar Google Scholar 27. 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. https://doi.org/10.1103/PhysRevLett.110.230501 arxiv:1302.4310 [quant-ph]Google ScholarGoogle Scholar 28. Kevin K. H. Cheung and Michele Mosca. 2001. Decomposing Finite Abelian Groups. Quantum Info. Comput. 1, 3 (Oct. 2001), 26-32. http://dl.acm.org/citation.cfm?id=2011339.2011341Google Scholar Google Scholar 29. Nai-Hui Chia, Andras Gilyen, 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 31st International Symposium on Algorithms and Computation (ISAAC 2020)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 181), Yixin Cao, Siu-Wing Cheng, and Minming Li (Eds.). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, Dagstuhl, Germany, 47:1-47:17. https://doi.org/10.4230/LIPIcs.ISAAC.2020.47Google ScholarGoogle Scholar 30. Andrew M Childs and Wim Van Dam. 2010. Quantum algorithms for algebraic problems. Reviews of Modern Physics 82, 1 (2010), 1. Google ScholarGoogle ScholarCross RefCross Ref 31. Lukasz Cincio, Yigit Subasi, Andrew T Sornborger, and Patrick J Coles. 2018. Learning the quantum algorithm for state overlap. New Journal of Physics 20, 11 (2018), 113022.Google ScholarGoogle ScholarCross RefCross Ref 32. Jill Cirasella. 2006. Classical and quantum algorithms for finding cycles. MSc Thesis (2006), 1-58.Google ScholarGoogle Scholar 33. C. Codsil and H. Zhan. 2011. Discrete-Time Quantum Walks and Graph Structures. (2011), 1-37. https://arxiv.org/abs/1701.4474 Google ScholarGoogle Scholar 34. Rigetti Computing. 2017. Quantum Approximate Optimization Algorithm. Published online at https://github.com/ rigetticomputing/grove. Accessed: 12/01/2017.Google ScholarGoogle Scholar 35. Jeremy Cook, Stephan Eidenbenz, and Andreas Bartschi. 2020. The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover. In IEEE International Conference on Quantum Computing & Engineering QCE'20. 83-92. https://doi.org/10.1109/QCE49297.2020.00021 arxiv:1910.13483Google ScholarGoogle Scholar 36. Stephen A. Cook. 1971. The Complexity of Theorem-proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, USA) (STOC '71). ACM, New York, NY, USA, 151-158. https://doi.org/10.1145/800157.805047 Google ScholarGoogle ScholarDigital LibraryDigital Library 37. D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. Journal of symbolic computation9 (1990), 251-280.Google ScholarGoogle Scholar 38. 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.Google ScholarGoogle Scholar 39. Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. 2008. Algorithms. McGraw-Hill, Inc., New York, NY, USA.Google ScholarGoogle Scholar 40. M. Dehn. 1911. Uber unendliche diskontinuierliche Gruppen. Math. Ann. 71, 1 (01 Mar 1911), 116-144. https://doi.org/10.1007/ BF01456932Google ScholarGoogle Scholar 41. D. Deutsch and R. Jozsa. 1992. Rapid solutions of problems by quantum computation. In Proc. of the Royal Society of London A. 439-553.Google ScholarGoogle Scholar 42. Simon J Devitt, William J Munro, and Kae Nemoto. 2013. Quantum error correction for beginners. Reports on Progress in Physics 76, 7 (2013), 076001.Google ScholarGoogle ScholarCross RefCross Ref 43. B. L. Douglas and J. B. Wang. 2009. Efficient quantum circuit implementation of quantum walks. Physical Review A 79, 5 (2009), 052335.Google ScholarGoogle ScholarCross RefCross Ref 44. 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. https:/ /doi.org/10.1287/ijoc.2017.0798Google ScholarGoogle Scholar Digital LibraryDigital Library 45. Christoph Durr, Mark Heiligman, Peter Hoyer, and Mehdi Mhalla. 2006. Quantum query complexity of some graph problems. SIAM J. Comput. 35, 6 (2006), 1310-1328.Google ScholarGoogle Scholar Digital LibraryDigital Library 46. Christoph Durr and Peter Hoyer. 1996. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014(1996).Google ScholarGoogle Scholar 47. Jack Edmonds and Richard M. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19 (2)(1972), 248-264.Google ScholarGoogle Scholar 48. Nayak F. Magniez A, J. Roland, and M. Santha. 2011. Search via Quantum Walk. SIAM J. Comput. 40, 1 (2011), 142-164. https:// arxiv.org/abs/quant-ph/0608026Google ScholarGoogle Scholar 49. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014a. A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv e-prints (2014). arXiv:1412.6062.Google ScholarGoogle Scholar 50. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014b. A Quantum Approximate Optimization Algorithm.Google ScholarGoogle Scholar 51. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum Computation by Adiabatic Evolution. arXiv e-prints (2000). arXiv:quant-ph/0001106.Google ScholarGoogle Scholar 52. L. R. Ford and D. R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399-404.Google ScholarGoogle Scholar 53. R. Freivalds. 1979. Fast probabilistic algorithms. In Proc. of 8th Symp. on Math. Foundations of Computer Science (1979), 57-69. Google ScholarGoogle Scholar 54. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.Google ScholarGoogle Scholar 55. Silvano Garnerone, Annalisa Marzuoli, and Mario Rasetti. 2007. Efficient quantum processing of 3-manifold topological invariants. arXiv preprint quant-ph/0703037(2007).Google Scholar Google Scholar 56. Iulia M Georgescu, Sahel Ashhab, and Franco Nori. 2014. Quantum simulation. Reviews of Modern Physics 86, 1 (2014), 153.Google ScholarGoogle ScholarCross RefCross Ref 57. Joseph Geraci. 2008. A new connection between quantum circuits, graphs and the Ising partition function. Quantum Information Processing 7, 5 (2008), 227-242.Google ScholarGoogle Scholar Digital LibraryDigital Library 58. 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.Google ScholarGoogle ScholarCross RefCross Ref 59. Andras Gilyen, Srinivasan Arunachalam, and Nathan Wiebe. [n.d.]. Optimizing quantum optimization algorithms via faster quantum gradient computation. In ACM-SIAM Symposium on Discrete Algorithms, SODA'2019. 1425-1444. https://doi.org/10.1137/ 1.9781611975482.87Google ScholarGoogle Scholar 60. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Quantum Random Access Memory. 100 (04, 2008), 160501.Google ScholarGoogle Scholar 61. Michel X. Goemans and David P. Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42, 6 (1995), 1115-1145. https://doi.org/10.1145/227683.227684Google Scholar Google ScholarDigital LibraryDigital Library 62. 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.Google ScholarGoogle Scholar 63. Lov K Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 212-219.Google Scholar Google ScholarDigital LibraryDigital Library 64. Eran Halperin, Dror Livnat, and Uri Zwick. 2004. MAX CUT in cubic graphs. Journal of Algorithms 53, 2 (2004), 169-185. https:// doi.org/10.1016/j.jalgor.2004.06.001Google ScholarGoogle Scholar Digital LibraryDigital Library 65. Matthew P. Harrigan et al. 2021. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics 17, 3 (2021), 332-336. https://doi.org/ 10.1038/s41567-020-01105-yGoogle ScholarGoogle Scholar 66. Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters 103, 15 (2009), 150502.Google ScholarGoogle Scholar 67. Zdenek Hradil. 1997. Quantum-state estimation. Physical Review A 55, 3 (1997), R1561.Google ScholarGoogle ScholarCross RefCross Ref 68. Johan Hastad. 2001. Some Optimal Inapproximability Results. J. ACM 48, 4 (2001), 798-859. https://doi.org/10.1145/502090.502098 Google ScholarGoogle ScholarDigital LibraryDigital Library 69. IBM Corporation. 2016. IBM Quantum Experience. Published online at https://quantumexperience.ng.bluemix.net. Accessed: 12/01/ 2017.Google ScholarGoogle Scholar 70. Daniel F. V. James, Paul G. Kwiat, William J. Munro, and Andrew G. White. 2001. Measurement of qubits. Phys. Rev. A 64 (2001), 052312. Issue 5.Google ScholarGoogle ScholarCross Ref Cross Ref 71. Sonika Johri, Damian S Steiger, and Matthias Troyer. 2017. Entanglement spectroscopy on a quantum computer. Physical Review B 96, 19 (2017), 195136.Google ScholarGoogle Scholar 72. Stephan Jordan. 2011. Quantum Algorithm Zoo. Published online at https://math.nist.gov/quantum/zoo/. Accessed: 3/18/2018.Google ScholarGoogle Scholar 73. Stephen P. Jordan. 2009. Fast quantum algorithms for approximating some irreducible representations of groups. (2009), 1-21. arxiv:0811.0562 https://arxiv.org/abs/0811.0562Google ScholarGoogle Scholar 74. Petteri Kaski. 2002. Eigenvectors and spectra of Cayley graphs. http://www.tcs.hut.fi/Studies/T-79.300/2002S/esitelmat/ kaski_paper_020506.pdfGoogle ScholarGoogle Scholar 75. J. Kempe. 2003. Quantum random walks - an introductory overview. Contemporary Physics 44, 4 (2003), 307-327. http:// www.tandfonline.com/doi/abs/10.1080/00107151031000110776Google ScholarGoogle ScholarCross RefCross Ref 76. V. Kendon. 2011. Where to quantum walk. (2011), 1-13. https:// arxiv.org/abs/1107.3795Google ScholarGoogle Scholar 77. 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. https:// doi.org/10.1137/S0097539705447372Google ScholarGoogle Scholar Digital LibraryDigital Library 78. Daphne Koller and Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT Press.Google ScholarGoogle ScholarDigital LibraryDigital Library 79. M W Krentel. 1986. The Complexity of Optimization Problems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (Berkeley, California, USA) (STOC '86). ACM, New York, NY, USA, 69-76. https://doi.org/10.1145/12130.12138Google Scholar Google ScholarDigital LibraryDigital Library 80. Thaddeus D Ladd, Fedor Jelezko, Raymond Laflamme, Yasunobu Nakamura, Christopher Monroe, and Jeremy Lloyd O'Brien. 2010. Quantum computers. Nature 464, 7285 (2010), 45.Google Scholar Google Scholar 81. R. LaRose, A. Tikku, E. O'Neel-Judy, L. Cincio, and P. J. Coles. 2019. Variational quantum state diagonalization. npj Quantum Information 5, 1 (2019), 57. https://doi.org/10.1038/ s41534-019-0167-6Google ScholarGoogle Scholar 82. R. J. Lipton and K. W. Regan. 2014. Quantum Algorithms via Linear Algebra. (2014).Google ScholarGoogle Scholar 83. Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. 2015. Quantum Algorithms for Topological and Geometric Analysis of Data. Nature Communications(2015). https://doi.org/10.1038/ncomms10138Google ScholarGoogle Scholar 84. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411(2013).Google ScholarGoogle Scholar 85. 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 arxiv:arXiv:1307.0401v2Google ScholarGoogle ScholarCross RefCross Ref 86. Neil B Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, and Viv Kendon. 2010. Universal quantum computation using the discrete-time quantum walk. Physical Review A 81, 4 (2010), 042330.Google ScholarGoogle ScholarCross RefCross Ref 87. Frederic Magniez, Miklos Santha, and Mario Szegedy. 2007. Quantum algorithms for the triangle problem. SIAM J. Comput. (2007), 413-424.Google ScholarGoogle Scholar 88. 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.Google Scholar Google Scholar 89. Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alan Aspuru-Guzik. 2016. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics 18, 2 (2016), 023023.Google ScholarGoogle ScholarCross RefCross Ref 90. Ashley Montanaro. 2016. Quantum algorithms: an overview. npj Quantum Information 2 (2016), 15023.Google ScholarGoogle Scholar 91. Michele Mosca. 2012. Quantum algorithms. In Computational Complexity. Springer, 2303-2333.Google ScholarGoogle Scholar 92. Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, United Kingdom. 10th Anniversary Edition.Google ScholarGoogle ScholarDigital LibraryDigital Library 93. Bryan O'Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley. 2019. Generalized swap networks for near-term quantum computing. arXiv e-prints (2019). arXiv:1905.05118.Google ScholarGoogle Scholar 94. Brian Olson, Irina Hashmi, Kevin Molloy, and Amarda Shehu. 2012. Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules. Advances in Artificial Intelligence 2012 (2012), 674832. https://doi.org/ 10.1155/2012/674832Google ScholarGoogle ScholarDigital Library Digital Library 95. 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. https://doi.org/10.1080/14786440109462720Google Scholar Google Scholar 96. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alan Aspuru-Guzik, and Jeremy L. O'Brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature Communications 5(July 2014), ncomms5213. https://doi.org/10.1038/ncomms5213Google Scholar Google Scholar 97. Martin Plesch and Caslav Brukner. 2011a. Quantum-state preparation with universal gate decompositions. Physical Review A 83, 3 (2011), 032302.Google ScholarGoogle ScholarCross RefCross Ref 98. Martin Plesch and Caslav Brukner. 2011b. Quantum-state preparation with universal gate decompositions. Phys. Rev. A 83 (2011), 032302. Issue 3. https://doi.org/10.1103/ PhysRevA.83.032302Google ScholarGoogle Scholar 99. Carl Pomerance. 1996. A tale of two sieves. Notices Amer. Math. Soc 43 (1996), 1473-1485.Google ScholarGoogle Scholar 100. John Preskill. [n.d.]. Quantum computing and the entanglement frontier. Rapporteur talk at the 25th Solvay Conference on Physics, 19-22 October 2011 ([n. d.]).Google ScholarGoogle Scholar 101. Bo Qi, Zhibo Hou, Li Li, Daoyi Dong, Guoyong Xiang, and Guangcan Guo. 2013. Quantum state tomography via linear regression estimation. Scientific reports 3(2013).Google ScholarGoogle Scholar 102. Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. 2014. Quantum support vector machine for big data classification. Physical review letters 113, 13 (2014), 130503.Google Scholar Google Scholar 103. E. Riefful and W. Polak. 2011. Quantum Computing: A Gentle Introduction. (2011).Google ScholarGoogle Scholar 104. R. L. Rivest, A. Shamir, and L. Adleman. 1978. A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120-126. https://doi.org/10.1145/ 359340.359342Google ScholarGoogle ScholarDigital LibraryDigital Library 105. Mehdi Saeedi and Igor L Markov. 2013. Synthesis and optimization of reversible circuits - a survey. ACM Computing Surveys (CSUR) 45, 2 (2013), 21.Google ScholarGoogle ScholarDigital Library Digital Library 106. Miklos Santha. 2008. Quantum walk based search algorithms. In International Conference on Theory and Applications of Models of Computation. Springer, 31-46.Google ScholarGoogle Scholar 107. N. Santhi. 2017. Quantum Netlist Compiler (QNC) software repository. http://gitlab.lanl.gov/QuantumProgramming2017/QNC Applied for LANL LACC authorization for unlimited open-source release, December 2017.Google ScholarGoogle Scholar 108. Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. 2015. An introduction to quantum machine learning. Contemporary Physics 56, 2 (2015), 172-185.Google ScholarGoogle ScholarCross RefCross Ref 109. Jiangwei Shang, Zhengyun Zhang, and Hui Khoon Ng. 2017. Superfast maximum-likelihood reconstruction for quantum tomography. Physical Review A 95, 6 (2017), 062336.Google Scholar Google Scholar 110. Vivek V. Shende and Igor L. Markov. 2009. On the CNOT-cost of TOFFOLI gates. Quant. Inf. Comp. 9, 5-6 (2009), 461-486. arxiv:0803.2316 http://arxiv.org/abs/0803.2316Google Scholar Google Scholar 111. 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.Google ScholarGoogle ScholarCross RefCross Ref 112. Neil Shenvi, Julia Kempe, and K Birgitta Whaley. 2003. Quantum random-walk search algorithm. Physical Review A 67, 5 (2003), 052307.Google ScholarGoogle ScholarCross RefCross Ref 113. Peter W Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on. IEEE, 124-134. https://doi.org/10.1109/SFCS.1994.365700Google ScholarGoogle Scholar 114. Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (1997), 1484-1509. https://doi.org/10.1137/ S0097539795293172 arXiv:https://doi.org/10.1137/S0097539795293172 Google ScholarGoogle ScholarDigital LibraryDigital Library 115. Nikolai A Sinitsyn. 2018. Computing with a single qubit faster than the computation quantum speed limit. Physics Letters A 382, 7 (2018), 477-481.Google ScholarGoogle Scholar 116. Robert S. Smith, Michael J. Curtis, and William J. Zeng. 2016. A Practical Quantum Instruction Set Architecture. arXiv:arXiv:1608.03355Google ScholarGoogle Scholar 117. 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.Google ScholarGoogle Scholar 118. Rolando D Somma. 2016. Quantum simulations of one dimensional quantum systems. Quantum Information & Computation 16, 13-14 (2016), 1125-1168.Google ScholarGoogle Scholar 119. Robert Spalek et al. 2006. Quantum algorithms, lower bounds, and time-space tradeoffs. ILLC,Amsterdam.Google ScholarGoogle Scholar 120. V. Strassen. 1969. Gaussian elimination is not optimal. Numer. Math.13(1969), 354-356.Google ScholarGoogle ScholarDigital LibraryDigital Library 121. Yigit Subasi, 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. Google ScholarGoogle Scholar 122. J. A. K. Suykens and J. Vandewalle. 1999. Least Squares Support Vector Machine Classifiers. Neural Process. Lett. 9, 3 (June 1999), 293-300. https://doi.org/10.1023/A:1018628609742Google ScholarGoogle ScholarDigital LibraryDigital Library 123. Mario Szegedy. 2004. Quantum speed-up of Markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science. IEEE, 32-41.Google ScholarGoogle ScholarDigital LibraryDigital Library 124. Maika Takita, Antonio D Corcoles, 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.Google ScholarGoogle Scholar 125. IBM QX Team. 2017. IBM Q experience backend information. http:// github.com/QISKit/ibmqx-backend-information. Last accessed: 12 December, 2017.Google ScholarGoogle Scholar 126. 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.Google ScholarGoogle Scholar 127. 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(Dec. 2001), 883-887. https://doi.org/ 10.1038/414883a arXiv:quant-ph/0112176Google ScholarGoogle Scholar 128. Guifre Vidal. 2003. Efficient classical simulation of slightly entangled quantum computations. Physical review letters 91, 14 (2003), 147902.Google ScholarGoogle Scholar 129. Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. 2018. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Physical Review A 97(2018), 022304. Issue 2. https://doi.org/10.1103/PhysRevA.97.022304Google Scholar Google ScholarCross RefCross Ref 130. Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. 2020. XY mixers: Analytical and numerical results for the quantum alternating operator ansatz. Physical Review A 101, 1 (2020), 012320. https://doi.org/10.1103/PhysRevA.101.012320Google ScholarGoogle Scholar 131. Chu Ryang Wie. 2017. A quantum circuit to construct all maximal cliques using Grover's search algorithm. (2017), 1-13. https:// arxiv.org/abs/1711.06146Google ScholarGoogle Scholar 132. 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.Google ScholarGoogle Scholar Cross RefCross Ref 133. James R Wootton. 2020. Benchmarking near-term devices with quantum error correction. Quantum Sci. Technol. 5, 4 (2020), 044004.Google ScholarGoogle Scholar 134. James R Wootton and Daniel Loss. 2018. Repetition code of 15 qubits. Physical Review A 97, 5 (2018), 052313.Google Scholar Google ScholarCross RefCross Ref 135. Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. 2017. Optimizing Variational Quantum Algorithms Using Pontryagin's Minimum Principle. Physical Review X 7, 2 (2017), 021027. https://doi.org/10.1103/physrevx.7.021027 Google ScholarGoogle Scholar 136. N. S. Yonofsky and M. A. Mannucci. 2008. Quantum Computing for Computer Scientists. (2008).Google ScholarGoogle Scholar 137. 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.Google ScholarGoogle Scholar 138. 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. https: //doi.org/10.1103/PhysRevX.10.021067Google ScholarGoogle Scholar Comments Please enable JavaScript to view thecomments powered by Disqus. Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article * Information * Contributors * Published in ACM Transactions on Quantum Computing cover image ACM Transactions on Quantum Computing Just Accepted ISSN:2643-6809 EISSN:2643-6817 Table of Contents Copyright (c) 2022 Copyright held by the owner/author(s). Sponsors In-Cooperation Publisher Association for Computing Machinery New York, NY, United States Publication History + Online: 28 March 2022 + Accepted: 8 February 2022 + Revised: 13 August 2021 + Received: 12 March 2020 Qualifiers + review-article Conference Funding Sources * [loader] Other Metrics View Article Metrics * Bibliometrics * Citations0 * Article Metrics + 0 Total Citations View Citations + 291 Total Downloads + Downloads (Last 12 months)291 + Downloads (Last 6 weeks)235 Other Metrics View Author Metrics * Cited By This publication has not been cited yet PDF Format View or Download as a PDF file. PDF eReader View online with eReader. eReader Digital Edition View this article in digital edition. View Digital Edition * Figures * Other * * Share this Publication link https://dl.acm.org/doi/10.1145/3517340 Copy Link Share on Social Media Share on * * * * 0References * * * Close Figure Viewer Browse AllReturnChange zoom level[ ] Caption Export Citations Select Citation format[BibTeX ] + Download citation + Copy citation * Preview is not available. By clicking download,a new tab will open to start the export process. The process may takea few minutes but once it finishes a file will be downloaded on your browser soplease do not close the new tab. Download Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Digital Library Accessibility Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact * Facebook * Twitter * Linkedin The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2022 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM home About Cookies On This Site We use cookies to ensure that we give you the best experience on our website. Learn more Got it!