{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:05:56Z","timestamp":1764687956967},"reference-count":21,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T00:00:00Z","timestamp":1638748800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We show a superpolynomial oracle separation between the power of adiabatic quantum computation with no sign problem and the power of classical computation.<\/jats:p>","DOI":"10.22331\/q-2021-12-06-597","type":"journal-article","created":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T13:15:10Z","timestamp":1638796510000},"page":"597","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":21,"title":["The Power of Adiabatic Quantum Computation with No Sign Problem"],"prefix":"10.22331","volume":"5","author":[{"given":"Matthew B.","family":"Hastings","sequence":"first","affiliation":[{"name":"Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA"},{"name":"Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA"}]}],"member":"9598","published-online":{"date-parts":[[2021,12,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u2013475, 2001. doi:10.1126\/science.1057726.","DOI":"10.1126\/science.1057726"},{"key":"1","unstructured":"Boris Altshuler, Hari Krovi, and Jeremie Roland. Adiabatic quantum optimization fails for random instances of np-complete problems. arXiv preprint arXiv:0908.2782, 2009."},{"key":"2","doi-asserted-by":"publisher","unstructured":"Boris Altshuler, Hari Krovi, and J\u00e9r\u00e9mie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107(28):12446\u201312450, 2010. doi:10.1073\/pnas.1002116107.","DOI":"10.1073\/pnas.1002116107"},{"key":"3","unstructured":"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."},{"key":"4","doi-asserted-by":"publisher","unstructured":"M. B. Hastings. A short path quantum algorithm for exact optimization. Quantum, 2:78, jul 2018. doi:10.22331\/q-2018-07-26-78.","DOI":"10.22331\/q-2018-07-26-78"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2019-05-20-145"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physrevlett.109.030502"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.94.022309"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Troels F R\u00f8nnow, 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\u2013424, 2014. doi:10.1126\/science.1252319.","DOI":"10.1126\/science.1252319"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/focs.2004.8"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u201343, 2002. doi:10.1023\/a:1019609420309.","DOI":"10.1023\/a:1019609420309"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Rolando D. Somma, Daniel Nagaj, and M\u00e1ria Kieferov\u00e1. Quantum speedup by quantum annealing. Physical Review Letters, 109(5), jul 2012. doi:10.1103\/physrevlett.109.050501.","DOI":"10.1103\/physrevlett.109.050501"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs. Universal computation by quantum walk. Physical Review Letters, 102(18), may 2009. doi:10.1103\/physrevlett.102.180501.","DOI":"10.1103\/physrevlett.102.180501"},{"key":"13","doi-asserted-by":"crossref","unstructured":"M. B. Hastings and M. H. Freedman. Obstructions to classically simulating the adiabatic algorithm. QIC, 13:1038, 2013.","DOI":"10.26421\/QIC13.11-12-8"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Patrik Henelius, S. M. Girvin, and Anders W. Sandvik. Role of winding numbers in quantum monte carlo simulations. Physical Review B, 57(21):13382\u201313385, jun 1998. doi:10.1103\/physrevb.57.13382.","DOI":"10.1103\/physrevb.57.13382"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/780542.780546"},{"key":"16","unstructured":"Andrew Macgregor Childs. Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004."},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u2013371, dec 2006. doi:10.1007\/s00220-006-0150-x.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/sfcs.1994.365701"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Jeffrey H. Schenker and Michael Aizenman. Letters in Mathematical Physics, 53(3):253\u2013262, 2000. doi:10.1023\/a:1011032212489.","DOI":"10.1023\/a:1011032212489"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.94.042318"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-12-06-597\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,12,6]],"date-time":"2021-12-06T13:15:15Z","timestamp":1638796515000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-12-06-597\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,6]]},"references-count":21,"URL":"https:\/\/doi.org\/10.22331\/q-2021-12-06-597","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,6]]},"article-number":"597"}}