The Power of Adiabatic Quantum Computation with No Sign Problem

Matthew B. Hastings

Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA
Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We show a superpolynomial oracle separation between the power of adiabatic quantum computation with no sign problem and the power of classical computation.

► BibTeX data

► References

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292(5516):472–475, 2001. doi:10.1126/​science.1057726.

[2] Boris Altshuler, Hari Krovi, and Jeremie Roland. Adiabatic quantum optimization fails for random instances of np-complete problems. arXiv preprint arXiv:0908.2782, 2009.

[3] Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107(28):12446–12450, 2010. doi:10.1073/​pnas.1002116107.

[4] Sergey Knysh and Vadim Smelyanskiy. On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm. arXiv preprint arXiv:1005.3011, 2010.

[5] M. B. Hastings. A short path quantum algorithm for exact optimization. Quantum, 2:78, jul 2018. doi:10.22331/​q-2018-07-26-78.

[6] M. B. Hastings. The short path algorithm applied to a toy model. Quantum, 3:145, may 2019. doi:10.22331/​q-2019-05-20-145.

[7] CR Laumann, R Moessner, A Scardicchio, and Shivaji Lal Sondhi. Quantum adiabatic algorithm and scaling of gaps at first-order quantum phase transitions. Physical review letters, 109(3):030502, 2012. doi:10.1103/​physrevlett.109.030502.

[8] Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Training a quantum optimizer. Physical Review A, 94(2), aug 2016. doi:10.1103/​physreva.94.022309.

[9] Troels F Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V Isakov, David Wecker, John M Martinis, Daniel A Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345(6195):420–424, 2014. doi:10.1126/​science.1252319.

[10] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev. Adiabatic quantum computation is equivalent to standard quantum computation. In 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE. doi:10.1109/​focs.2004.8.

[11] Andrew M. Childs, Edward Farhi, and Sam Gutmann. An example of the difference between quantum and classical random walks. Quantum Information Processing, 1(1/​2):35–43, 2002. doi:10.1023/​a:1019609420309.

[12] Rolando D. Somma, Daniel Nagaj, and Mária Kieferová. Quantum speedup by quantum annealing. Physical Review Letters, 109(5), jul 2012. doi:10.1103/​physrevlett.109.050501.

[13] Andrew M. Childs. Universal computation by quantum walk. Physical Review Letters, 102(18), may 2009. doi:10.1103/​physrevlett.102.180501.

[14] M. B. Hastings and M. H. Freedman. Obstructions to classically simulating the adiabatic algorithm. QIC, 13:1038, 2013.

[15] Patrik Henelius, S. M. Girvin, and Anders W. Sandvik. Role of winding numbers in quantum monte carlo simulations. Physical Review B, 57(21):13382–13385, jun 1998. doi:10.1103/​physrevb.57.13382.

[16] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth ACM symposium on Theory of computing - 03. ACM Press, 2003. doi:10.1145/​780542.780546.

[17] Andrew Macgregor Childs. Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004.

[18] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270(2):359–371, dec 2006. doi:10.1007/​s00220-006-0150-x.

[19] D.R. Simon. On the power of quantum computation. In Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press. doi:10.1109/​sfcs.1994.365701.

[20] Jeffrey H. Schenker and Michael Aizenman. Letters in Mathematical Physics, 53(3):253–262, 2000. doi:10.1023/​a:1011032212489.

[21] Michael Jarret, Stephen P. Jordan, and Brad Lackey. Adiabatic optimization versus diffusion monte carlo methods. Physical Review A, 94(4), oct 2016. doi:10.1103/​physreva.94.042318.

Cited by

[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum (NISQ) algorithms", arXiv:2101.08448.

[2] E. J. Crosson and D. A. Lidar, "Prospects for quantum enhancement with diabatic quantum annealing", Nature Reviews Physics 3 7, 466 (2021).

[3] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, "Prospects and challenges of quantum finance", arXiv:2011.06492.

[4] Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon, and Nicholas Chancellor, "An energetic perspective on rapid quenches in quantum annealing", arXiv:2007.11599.

[5] A. Ciani and B. M. Terhal, "Stoquasticity in circuit QED", Physical Review A 103 4, 042401 (2021).

[6] Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, and Barbara M. Terhal, "Sign-curing local Hamiltonians: termwise versus global stoquasticity and the use of Clifford transformations", arXiv:2007.11964.

[7] András Gilyén and Umesh Vazirani, "(Sub)Exponential advantage of adiabatic quantum computation with no sign problem", arXiv:2011.09495.

[8] Tameem Albash and Matthew Kowalsky, "Diagonal catalysts in quantum adiabatic optimization", Physical Review A 103 2, 022608 (2021).

[9] Jacob Bringewatt and Michael Jarret, "Effective Gaps Are Not Effective: Quasipolynomial Classical Simulation of Obstructed Stoquastic Hamiltonians", Physical Review Letters 125 17, 170504 (2020).

[10] Sergey Knysh, Eugeniu Plamadeala, and Davide Venturelli, "Quantum annealing speedup of embedded problems via suppression of Griffiths singularities", Physical Review B 102 22, 220407 (2020).

[11] T. C. Mooney, Jacob Bringewatt, and Lucas T. Brady, "Lefschetz Thimble Quantum Monte Carlo for Spin Systems", arXiv:2110.10699.

[12] Stephen P. Jordan, Siyuan Hu, Ignacio Rozada, Debra F. McGivney, Rasim Boyacioğlu, Darryl C. Jacob, Sherry Huang, Michael Beverland, Helmut G. Katzgraber, Matthias Troyer, Mark A. Griswold, and Dan Ma, "Automated design of pulse sequences for magnetic resonance fingerprinting using physics-inspired optimization", Proceedings of the National Academy of Science 118 40, 2020516118 (2021).

[13] Kabuki Takada, Shigetoshi Sota, Seiji Yunoki, Bibek Pokharel, Hidetoshi Nishimori, and Daniel A. Lidar, "Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts", Physical Review Research 3 4, 043013 (2021).

The above citations are from SAO/NASA ADS (last updated successfully 2022-01-23 08:38:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-01-23 08:38:31).