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.

Abstract

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.
https:/​/​doi.org/​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.
arXiv:0908.2782

[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.
https:/​/​doi.org/​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.
arXiv:1005.3011

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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] Jacob Bringewatt and Lucas T. Brady, "Simultaneous stoquasticity", Physical Review A 105 6, 062601 (2022).

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

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

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

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

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

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

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

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

[11] 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.

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

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

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

[15] Abolfazl Ramezanpour, "Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement", arXiv:2202.10908.

The above citations are from Crossref's cited-by service (last updated successfully 2022-07-05 16:57:33) and SAO/NASA ADS (last updated successfully 2022-07-05 16:57:34). The list may be incomplete as not all publishers provide suitable and complete citation data.