{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T02:12:33Z","timestamp":1774318353463,"version":"3.50.1"},"reference-count":19,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T00:00:00Z","timestamp":1760918400000},"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>The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03BA;<\/mml:mi><\/mml:math> and the allowable error <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03F5;<\/mml:mi><\/mml:math> \\cite{CostaAnYuvalEtAl2022}. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,200 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is about an order of magnitude more efficient than using a randomised approach from \\cite{jennings2023efficient} that claimed to be more efficient.<\/jats:p>","DOI":"10.22331\/q-2025-10-20-1887","type":"journal-article","created":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T12:32:15Z","timestamp":1760963535000},"page":"1887","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver"],"prefix":"10.22331","volume":"9","author":[{"given":"Pedro C.S.","family":"Costa","sequence":"first","affiliation":[{"name":"ContinoQuantum, Sydney, NSW 2093, AU"},{"name":"School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, AU"}]},{"given":"Dong","family":"An","sequence":"additional","affiliation":[{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA"}]},{"given":"Ryan","family":"Babbush","sequence":"additional","affiliation":[{"name":"Google Quantum AI, Venice, CA 90291, USA"}]},{"given":"Dominic","family":"Berry","sequence":"additional","affiliation":[{"name":"School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, AU"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations&apos;&apos;. Physical Review Letters 103, 150502 (2009).","DOI":"10.1103\/physrevlett.103.150502"},{"key":"1","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&apos;&apos;. ACM Transactions on Quantum Computing 3, 5 (2022).","DOI":"10.1145\/3498331"},{"key":"2","unstructured":"Andris Ambainis. ``Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations&apos;&apos; (2010). url: arxiv.org\/abs\/1010.4458."},{"key":"3","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems&apos;&apos;. Quantum 4, 361 (2020).","DOI":"10.22331\/q-2020-11-11-361"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Robin Kothari, and Rolando D. Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision&apos;&apos;. SIAM Journal on Computing 46, 1920\u20131950 (2017).","DOI":"10.1137\/16M1087072"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. ``Optimal scaling quantum linear-systems solver via discrete adiabatic theorem&apos;&apos;. PRX Quantum 3, 040303 (2022).","DOI":"10.1103\/PRXQuantum.3.040303"},{"key":"6","unstructured":"Aram W. Harrow and Robin Kothari. ``&apos;&apos;. In preparation (2025)."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems&apos;&apos;. Quantum 4, 361 (2020).","DOI":"10.22331\/q-2020-11-11-361"},{"key":"8","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&apos;&apos;. Physical Review Letters 122, 060504 (2019).","DOI":"10.1103\/PhysRevLett.122.060504"},{"key":"9","unstructured":"David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yi\u011fit Suba\u015f\u0131. ``Efficient quantum linear solver algorithm with detailed running costs&apos;&apos; (2023). url: arxiv.org\/abs\/2305.11352."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. ``Bounds for the adiabatic approximation with applications to quantum computation&apos;&apos;. Journal of Mathematical Physics 48, 102111 (2007).","DOI":"10.1063\/1.2798382"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. ``Compilation of fault-tolerant quantum heuristics for combinatorial optimization&apos;&apos;. PRX Quantum 1, 020312 (2020).","DOI":"10.1103\/prxquantum.1.020312"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Ryan Babbush, Dominic W. Berry, and Hartmut Neven. ``Quantum simulation of the sachdev-ye-kitaev model by asymmetric qubitization&apos;&apos;. Physical Review A 99, 040301 (2019).","DOI":"10.1103\/PhysRevA.99.040301"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, and Nathan Wiebe. ``Doubling the efficiency of hamiltonian simulation via generalized quantum signal processing&apos;&apos;. Phys. Rev. A 110, 012612 (2024).","DOI":"10.1103\/PhysRevA.110.012612"},{"key":"14","unstructured":"Pedro C. S. Costa. ``Qlsp via discrete adiabatic method - source code&apos;&apos;. https:\/\/github.com\/PcostaQuantum\/QLSP-via-discrete-adiabatic-method\/blob\/main\/Walk_error_Herm.m (2025). Accessed: 2025-01-24."},{"key":"15","unstructured":"Tim Davis and Yifan Hu. ``Suitesparse matrix collection&apos;&apos;. https:\/\/sparse.tamu.edu\/ (2024). Accessed: 2024-10-23."},{"key":"16","unstructured":"Pedro C. S. Costa. ``Qlsp via randomisation method - source code&apos;&apos;. https:\/\/github.com\/PcostaQuantum\/QLSP-via-randomisation-method (2024). Accessed: 2025-01-24."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Limit on the speed of quantum computation in determining parity&apos;&apos;. Phys. Rev. Lett. 81, 5442\u20135444 (1998).","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials&apos;&apos;. J. ACM 48, 778\u2013797 (2001).","DOI":"10.1145\/502090.502097"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-20-1887\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T12:32:17Z","timestamp":1760963537000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-20-1887\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,20]]},"references-count":19,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-20-1887","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,20]]},"article-number":"1887"}}