{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T19:59:06Z","timestamp":1780603146498,"version":"3.54.1"},"reference-count":60,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T00:00:00Z","timestamp":1752192000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"SERB-DST, Government of India","award":["SRG\/2022\/000354"],"award-info":[{"award-number":["SRG\/2022\/000354"]}]},{"name":"MeitY, Government of India","award":["4(3)\/2024-ITEA"],"award-info":[{"award-number":["4(3)\/2024-ITEA"]}]},{"name":"Digital Horizon Europe","award":["01070558"],"award-info":[{"award-number":["01070558"]}]},{"name":"FCT, Portugal","award":["CEECINST\/00062\/2018"],"award-info":[{"award-number":["CEECINST\/00062\/2018"]}]},{"name":"Belgian FNRS","award":["R.8015.21"],"award-info":[{"award-number":["R.8015.21"]}]},{"name":"Belgian FNRS","award":["O.0013.22"],"award-info":[{"award-number":["O.0013.22"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-bits in time <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mtext>poly<\/mml:mtext><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:msup><mml:mn>2<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>n<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math>. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x03A9;<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mn>2<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>n<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.<\/jats:p>","DOI":"10.22331\/q-2025-07-11-1790","type":"journal-article","created":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T15:56:06Z","timestamp":1752249366000},"page":"1790","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Unstructured Adiabatic Quantum Optimization: Optimality with Limitations"],"prefix":"10.22331","volume":"9","author":[{"given":"Arthur","family":"Braida","sequence":"first","affiliation":[{"name":"QuIC, Ecole Polytechnique de Bruxelles, Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shantanav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"CQST and CSTAR, International Institute of Information Technology Hyderabad, Telangana, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alapan","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"CQST and CSTAR, International Institute of Information Technology Hyderabad, Telangana, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Cunningham","sequence":"additional","affiliation":[{"name":"QuIC, Ecole Polytechnique de Bruxelles, Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rutvij","family":"Menavlikar","sequence":"additional","affiliation":[{"name":"CQST and CSTAR, International Institute of Information Technology Hyderabad, Telangana, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonardo","family":"Novo","sequence":"additional","affiliation":[{"name":"International Iberian Nanotechnology Laboratory, Braga, Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[{"name":"QuIC, Ecole Polytechnique de Bruxelles, Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2025,7,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv:quant-ph\/0001106, 2000. URL: https:\/\/arxiv.org\/abs\/quant-ph\/0001106, doi:10.48550\/arXiv.quant-ph\/0001106.","DOI":"10.48550\/arXiv.quant-ph\/0001106"},{"key":"1","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. URL: https:\/\/www.science.org\/doi\/abs\/10.1126\/science.1057726, doi:10.1126\/science.1057726.","DOI":"10.1126\/science.1057726"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Matthew B. Hastings. Obstructions to classically simulating the quantum adiabatic algorithm. Quantum Info. Comput., 13(11\u201312):1038\u20131076, November 2013. URL: https:\/\/dl.acm.org\/doi\/10.5555\/2535639.2535647.","DOI":"10.26421\/QIC13.11-12-8"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90:015002, Jan 2018. URL: https:\/\/doi.org10.1103\/RevModPhys.90.015002, doi:10.1103\/RevModPhys.90.015002.","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070\u20131097, 2006. doi:10.1137\/S0097539704445226.","DOI":"10.1137\/S0097539704445226"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins. Nature, 473(7346):194\u2013198, 2011. doi:10.1038\/nature10012.","DOI":"10.1038\/nature10012"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Journal on Computing, 37(1):166\u2013194, 2007. doi:10.1137\/S0097539705447323.","DOI":"10.1137\/S0097539705447323"},{"key":"7","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 Annual ACM Symposium on Theory of Computing, STOC &apos;03, page 20\u201329, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145\/780542.780546.","DOI":"10.1145\/780542.780546"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Hari Krovi, Maris Ozols, and J\u00e9r\u00e9mie Roland. Adiabatic condition and the quantum hitting time of markov chains. Phys. Rev. A, 82:022333, Aug 2010. URL: https:\/\/doi.org\/10.1103\/PhysRevA.82.022333, doi:10.1103\/PhysRevA.82.022333.","DOI":"10.1103\/PhysRevA.82.022333"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Rolando D. Somma, Daniel Nagaj, and M\u00e1ria Kieferov\u00e1. Quantum speedup by quantum annealing. Phys. Rev. Lett., 109:050501, Jul 2012. URL: https:\/\/doi.org\/10.1103\/PhysRevLett.109.050501, doi:10.1103\/PhysRevLett.109.050501.","DOI":"10.1103\/PhysRevLett.109.050501"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar. Adiabatic quantum algorithm for search engine ranking. Phys. Rev. Lett., 108:230506, Jun 2012. URL: https:\/\/doi.org\/10.1103\/PhysRevLett.108.230506, doi:10.1103\/PhysRevLett.108.230506.","DOI":"10.1103\/PhysRevLett.108.230506"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Matthew B. Hastings. The Power of Adiabatic Quantum Computation with No Sign Problem. Quantum, 5:597, December 2021. doi:10.22331\/q-2021-12-06-597.","DOI":"10.22331\/q-2021-12-06-597"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Matthew B. Hastings, and Umesh Vazirani. (Sub)exponential advantage of adiabatic quantum computation with no sign problem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1357\u20131369, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145\/3406325.3451060.","DOI":"10.1145\/3406325.3451060"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Yi\u011fit Suba\u015f\u0131, Rolando D. Somma, and Davide Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett., 122:060504, Feb 2019. URL: https:\/\/doi.org\/10.1103\/PhysRevLett.122.060504, doi:10.1103\/PhysRevLett.122.060504.","DOI":"10.1103\/PhysRevLett.122.060504"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, November 2020. doi:10.22331\/q-2020-11-11-361.","DOI":"10.22331\/q-2020-11-11-361"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Dong An and Lin Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. ACM Transactions on Quantum Computing, 3(2), March 2022. doi:10.1145\/3498331.","DOI":"10.1145\/3498331"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brand\u00e3o. Mind the gap: Achieving a super-grover quantum speedup by jumping to the end. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1131\u20131144, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145\/3564246.3585203.","DOI":"10.1145\/3564246.3585203"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent Hamiltonian simulation with $L^1$-norm scaling. Quantum, 4:254, April 2020. doi:10.22331\/q-2020-04-20-254.","DOI":"10.22331\/q-2020-04-20-254"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Sergio Boixo, Emanuel Knill, and Rolando Somma. Eigenpath traversal by phase randomization. Quantum Info. Comput., 9(9):833\u2013855, September 2009. URL: https:\/\/dl.acm.org\/doi\/10.5555\/2011804.2011811.","DOI":"10.26421\/QIC9.9-10-7"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48(10):102111, 10 2007. doi:10.1063\/1.2798382.","DOI":"10.1063\/1.2798382"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Alexander Elgart and George A. Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53(10):102202, 09 2012. doi:10.1063\/1.4748968.","DOI":"10.1063\/1.4748968"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ben W. Reichardt. The quantum adiabatic optimization algorithm and local minima. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC &apos;04, page 502\u2013510, New York, NY, USA, 2004. Association for Computing Machinery. doi:10.1145\/1007352.1007428.","DOI":"10.1145\/1007352.1007428"},{"key":"22","doi-asserted-by":"publisher","unstructured":"F Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241, oct 1982. URL: https:\/\/dx.doi.org\/10.1088\/0305-4470\/15\/10\/028, doi:10.1088\/0305-4470\/15\/10\/028.","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Andrew Lucas. Ising formulations of many NP problems. Frontiers in physics, 2:5, 2014. doi:doi.org\/10.3389\/fphy.2014.00005.","DOI":"10.3389\/fphy.2014.00005"},{"key":"24","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. URL: https:\/\/www.pnas.org\/doi\/abs\/10.1073\/pnas.1002116107, doi:10.1073\/pnas.1002116107.","DOI":"10.1073\/pnas.1002116107"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Jeremie Roland and Nicolas J. Cerf. Quantum search by local adiabatic evolution. Physical Review A, 65(4), mar 2002. doi:10.1103\/physreva.65.042308.","DOI":"10.1103\/physreva.65.042308"},{"key":"26","doi-asserted-by":"crossref","unstructured":"Andris Ambainis. Quantum search algorithms. Acm Sigact News, 35(2):22\u201335, 2004.","DOI":"10.1145\/992287.992296"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel Nagaj. How to make the quantum adiabatic algorithm fail. International Journal of Quantum Information, 6(03):503\u2013516, 2008. doi:10.1142\/S021974990800358X.","DOI":"10.1142\/S021974990800358X"},{"key":"28","doi-asserted-by":"publisher","unstructured":"W. van Dam, M. Mosca, and U. Vazirani. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 279\u2013287, 2001. doi:10.1109\/SFCS.2001.959902.","DOI":"10.1109\/SFCS.2001.959902"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Richard M. Karp. Reducibility among Combinatorial Problems, pages 85\u2013103. Springer US, Boston, MA, 1972. doi:10.1007\/978-1-4684-2001-2_9.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979. doi:10.1137\/0208032.","DOI":"10.1137\/0208032"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC &apos;11, page 333\u2013342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145\/1993636.1993682.","DOI":"10.1145\/1993636.1993682"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1:8, April 2017. doi:10.22331\/q-2017-04-25-8.","DOI":"10.22331\/q-2017-04-25-8"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159\u2013163, 2019. doi:10.1038\/s41567-018-0318-2.","DOI":"10.1038\/s41567-018-0318-2"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Ramis Movassagh. The hardness of random quantum circuits. Nature Physics, 19(11):1719\u20131724, 2023. doi:10.1038\/s41567-023-02131-2.","DOI":"10.1038\/s41567-023-02131-2"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Phys. Rev. Lett., 83:5162\u20135165, Dec 1999. URL: https:\/\/doi.org\/10.1103\/PhysRevLett.83.5162, doi:10.1103\/PhysRevLett.83.5162.","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60(2):022202, 02 2019. doi:10.1063\/1.5027484.","DOI":"10.1063\/1.5027484"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty. Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers. Quantum, 8:1496, October 2024. doi:10.22331\/q-2024-10-10-1496.","DOI":"10.22331\/q-2024-10-10-1496"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4:372, December 2020. doi:10.22331\/q-2020-12-14-372.","DOI":"10.22331\/q-2020-12-14-372"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1\u201333:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. URL: https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ICALP.2019.33, doi:10.4230\/LIPIcs.ICALP.2019.33.","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Jack Sherman and Winifred J. Morrison. Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix. The Annals of Mathematical Statistics, 21(1):124 \u2013 127, 1950. doi:10.1214\/aoms\/1177729893.","DOI":"10.1214\/aoms\/1177729893"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. doi:doi.org\/10.1017\/CBO9780511804090.","DOI":"10.1017\/CBO9780511804090"},{"key":"42","doi-asserted-by":"publisher","unstructured":"L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189\u2013201, 1979. URL: https:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397579900446, doi:10.1016\/0304-3975(79)90044-6.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Joseph Cunningham and J\u00e9r\u00e9mie Roland. Eigenpath Traversal by Poisson-Distributed Phase Randomisation. In Fr\u00e9d\u00e9ric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), volume 310 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1\u20137:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. URL: https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.TQC.2024.7, doi:10.4230\/LIPIcs.TQC.2024.7.","DOI":"10.4230\/LIPIcs.TQC.2024.7"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Marko \u017dnidari\u010dand Martin Horvat. Exponential complexity of an adiabatic algorithm for an NP-complete problem. Phys. Rev. A, 73:022329, Feb 2006. URL: https:\/\/doi.org\/10.1103\/PhysRevA.73.022329, doi:10.1103\/PhysRevA.73.022329.","DOI":"10.1103\/PhysRevA.73.022329"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Itay Hen. Continuous-time quantum algorithms for unstructured problems. Journal of Physics A: Mathematical and Theoretical, 47(4):045305, jan 2014. URL: https:\/\/dx.doi.org\/10.1088\/1751-8113\/47\/4\/045305, doi:10.1088\/1751-8113\/47\/4\/045305.","DOI":"10.1088\/1751-8113\/47\/4\/045305"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Max Born and Vladimir Fock. Beweis des adiabatensatzes. Zeitschrift f\u00fcr Physik, 51(3):165\u2013180, 1928. doi:10.1007\/BF01343193.","DOI":"10.1007\/BF01343193"},{"key":"47","unstructured":"Arthur Braida. Analog Quantum Computing for NP-Hard Combinatorial Graph Problems. Theses, Universit\u00e9 d&apos;Orl\u00e9ans, June 2024. URL: https:\/\/theses.hal.science\/tel-04706199."},{"key":"48","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Jeffrey Goldstone. Spatial search by quantum walk. Phys. Rev. A, 70:022314, Aug 2004. URL: https:\/\/doi.org\/10.1103\/PhysRevA.70.022314, doi:10.1103\/PhysRevA.70.022314.","DOI":"10.1103\/PhysRevA.70.022314"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, and Yasser Omar. Spatial search by quantum walk is optimal for almost all graphs. Phys. Rev. Lett., 116:100501, Mar 2016. URL: https:\/\/doi.org\/10.1103\/PhysRevLett.116.100501, doi:10.1103\/PhysRevLett.116.100501.","DOI":"10.1103\/PhysRevLett.116.100501"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Leonardo Novo, and J\u00e9r\u00e9mie Roland. Optimality of spatial search via continuous-time quantum walks. Phys. Rev. A, 102:032214, Sep 2020. URL: https:\/\/doi.org\/10.1103\/PhysRevA.102.032214, doi:10.1103\/PhysRevA.102.032214.","DOI":"10.1103\/PhysRevA.102.032214"},{"key":"51","unstructured":"Joseph Cunningham and J\u00e9r\u00e9mie Roland. Quantum adiabatic theorem. In preparation, 2025."},{"key":"52","doi-asserted-by":"publisher","unstructured":"Gene H. Golub. Some modified matrix eigenvalue problems. SIAM Review, 15(2):318\u2013334, 1973. arXiv:https:\/\/doi.org\/10.1137\/1015032, doi:10.1137\/1015032.","DOI":"10.1137\/1015032"},{"key":"53","doi-asserted-by":"publisher","unstructured":"M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237\u2013267, 1976. doi:10.1016\/0304-3975(76)90059-1.","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"54","doi-asserted-by":"crossref","unstructured":"Vicky Choi. Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3sat problems. Quantum Info. Comput., 11(7\u20138):638\u2013648, July 2011. URL: https:\/\/dl.acm.org\/doi\/abs\/10.5555\/2230916.2230923.","DOI":"10.26421\/QIC11.7-8-7"},{"key":"55","doi-asserted-by":"publisher","unstructured":"George M Phillips. Interpolation and approximation by polynomials, volume 14. Springer Science & Business Media, 2003. doi:10.1007\/b97417.","DOI":"10.1007\/b97417"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC &apos;92, page 468\u2013474, New York, NY, USA, 1992. Association for Computing Machinery. doi:10.1145\/129712.129758.","DOI":"10.1145\/129712.129758"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Leonid Gurvits. On the complexity of mixed discriminants and related problems. In Proceedings of the 30th International Conference on Mathematical Foundations of Computer Science, MFCS&apos;05, page 447\u2013458, Berlin, Heidelberg, 2005. Springer-Verlag. doi:10.1007\/11549345_39.","DOI":"10.1007\/11549345_39"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon. Finding spin glass ground states using quantum walks. New Journal of Physics, 21(12):123022, dec 2019. URL: https:\/\/dx.doi.org\/10.1088\/1367-2630\/ab5ca2, doi:10.1088\/1367-2630\/ab5ca2.","DOI":"10.1088\/1367-2630\/ab5ca2"},{"key":"59","unstructured":"Eduardo Ara\u00fajo, Shantanav Chakraborty, and Leonardo Novo. Advantages and limitations of analog quantum search methods. In preparation, 2025."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-11-1790\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T15:56:10Z","timestamp":1752249370000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-11-1790\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,11]]},"references-count":60,"URL":"https:\/\/doi.org\/10.22331\/q-2025-07-11-1790","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,11]]},"article-number":"1790"}}