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] Ali Hamed Moosavian, Seyed Sajad Kahani, and Salman Beigi, "Limits of Short-Time Evolution of Local Hamiltonians", Quantum 6, 744 (2022).

[2] Aarón Villanueva, Peyman Najafi, and Hilbert J Kappen, "Why adiabatic quantum annealing is unlikely to yield speed-up", Journal of Physics A: Mathematical and Theoretical 56 46, 465304 (2023).

[3] Hefeng Wang, Sixia Yu, and Hua Xiang, "Efficient quantum algorithm for solving structured problems via multistep quantum computation", Physical Review Research 5 1, L012004 (2023).

[4] A. Ramezanpour, "Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement", Physical Review A 106 1, 012418 (2022).

[5] T. C. Mooney, Jacob Bringewatt, Neill C. Warrington, and Lucas T. Brady, "Lefschetz thimble quantum Monte Carlo for spin systems", Physical Review B 106 21, 214416 (2022).

[6] Yuichiro Mori, Shiro Kawabata, and Yuichiro Matsuzaki, "How to experimentally evaluate the adiabatic condition for quantum annealing", Scientific Reports 14 1, 8177 (2024).

[7] Noa Feldman and Moshe Goldstein, "Noisy quantum computation modeled by quantum walk: universality without ancillas", Quantum Science and Technology 7 4, 045032 (2022).

[8] Eric R. Anschuetz, Lena Funcke, Patrick T. Komiske, Serhii Kryhin, and Jesse Thaler, "Degeneracy engineering for classical and quantum annealing: A case study of sparse linear regression in collider physics", Physical Review D 106 5, 056008 (2022).

[9] Sevag Gharibian, "Guest Column: The 7 faces of quantum NP", ACM SIGACT News 54 4, 54 (2023).

[10] Jacob Bringewatt and Lucas T. Brady, "Simultaneous stoquasticity", Physical Review A 105 6, 062601 (2022).

[11] Shuvro Chowdhury, Kerem Y. Camsari, and Supriyo Datta, "Accelerated quantum Monte Carlo with probabilistic computers", Communications Physics 6 1, 85 (2023).

[12] Artem Rakcheev and Andreas M. Läuchli, "Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model", Physical Review A 107 6, 062602 (2023).

[13] Meng Ye, Ye Tian, Jian Lin, Yuchen Luo, Jiaqi You, Jiazhong Hu, Wenjun Zhang, Wenlan Chen, and Xiaopeng Li, "Universal Quantum Optimization with Cold Atoms in an Optical Cavity", Physical Review Letters 131 10, 103601 (2023).

[14] Narendra N. Hegade, Xi Chen, and Enrique Solano, "Digitized counterdiabatic quantum optimization", Physical Review Research 4 4, L042030 (2022).

[15] 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 algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[16] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

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

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

[19] Scott Aaronson, "How Much Structure Is Needed for Huge Quantum Speedups?", arXiv:2209.06930, (2022).

[20] S. Whitlock and T. D. Kieu, "Quantum Factoring Algorithm using Grover Search", arXiv:2312.10054, (2023).

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

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

[23] 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).

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

[25] 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, (2020).

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

[27] 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).

[28] Hefeng Wang, Sixia Yu, and Hua Xiang, "Efficient quantum algorithm for solving structured problems via multi-step quantum computation", arXiv:1912.06959, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 15:18:09) and SAO/NASA ADS (last updated successfully 2024-05-21 15:18:10). The list may be incomplete as not all publishers provide suitable and complete citation data.