The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

Pedro C.S. Costa^1,2, Dong An³, Ryan Babbush⁴, and Dominic Berry²

¹ContinoQuantum, Sydney, NSW 2093, AU
²School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, AU
³Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA
⁴Google Quantum AI, Venice, CA 90291, USA

Published:	2025-10-20, volume 9, page 1887
Editor:	Di Fang
Eprint:	arXiv:2312.07690v3
Doi:	https://doi.org/10.22331/q-2025-10-20-1887
Citation:	Quantum 9, 1887 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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 $\kappa$ and the allowable error $\epsilon$ [6]. 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 [10] that claimed to be more efficient.

Featured image: Solution error for the adiabatic step ∆ as a function of ϵ chosen to minimize the total cost (adiabatic evolution + filtering) within the quantum-walk circuit.

Popular summary

Solving systems of linear equations is a key building block for many quantum algorithms. Recently an algorithm with optimal asymptotic scaling was discovered, but a major open question remained. Would it actually be best in practice, or would the constant factor in the scaling cause it to be slower? This is because the analytic upper bound on the constant factor for that method is exceptionally large. This question was brought to the forefront by the development of a randomized method with suboptimal scaling, but where the analytically proven constant factor is smaller. We put these methods to the test considering thousands of random matrices with different dimensions, and found that in practice the constant for the optimally scaling method is about 1,200× smaller than the analytic upper bound suggested. In other words, this method translates into much faster runtimes than expected—and in our benchmarks provides the best performance in practice as well as the optimal scaling.

► BibTeX data

@article{Costa2025discreteadiabatic,
  doi = {10.22331/q-2025-10-20-1887},
  url = {https://doi.org/10.22331/q-2025-10-20-1887},
  title = {The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver},
  author = {Costa, Pedro C.S. and An, Dong and Babbush, Ryan and Berry, Dominic},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1887},
  month = oct,
  year = {2025}
}

► References

[1] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).
https://doi.org/10.1103/physrevlett.103.150502

[2] 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, 5 (2022).
https://doi.org/10.1145/3498331

[3] Andris Ambainis. ``Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations'' (2010). url: arxiv.org/abs/1010.4458.
arXiv:1010.4458

[4] Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020).
https://doi.org/10.22331/q-2020-11-11-361

[5] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision''. SIAM Journal on Computing 46, 1920–1950 (2017).
https://doi.org/10.1137/16M1087072

[6] 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''. PRX Quantum 3, 040303 (2022).
https://doi.org/10.1103/PRXQuantum.3.040303

[7] Aram W. Harrow and Robin Kothari. ``''. In preparation (2025).

[8] Lin Lin and Yu Tong. ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems''. Quantum 4, 361 (2020).
https://doi.org/10.22331/q-2020-11-11-361

[9] Yiğit Subaşı, Rolando D Somma, and Davide Orsucci. ``Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing''. Physical Review Letters 122, 060504 (2019).
https://doi.org/10.1103/PhysRevLett.122.060504

[10] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yiğit Subaşı. ``Efficient quantum linear solver algorithm with detailed running costs'' (2023). url: arxiv.org/abs/2305.11352.
arXiv:2305.11352

[11] Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. ``Bounds for the adiabatic approximation with applications to quantum computation''. Journal of Mathematical Physics 48, 102111 (2007).
https://doi.org/10.1063/1.2798382

[12] 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''. PRX Quantum 1, 020312 (2020).
https://doi.org/10.1103/prxquantum.1.020312

[13] Ryan Babbush, Dominic W. Berry, and Hartmut Neven. ``Quantum simulation of the sachdev-ye-kitaev model by asymmetric qubitization''. Physical Review A 99, 040301 (2019).
https://doi.org/10.1103/PhysRevA.99.040301

[14] Dominic W. Berry, Danial Motlagh, Giacomo Pantaleoni, and Nathan Wiebe. ``Doubling the efficiency of hamiltonian simulation via generalized quantum signal processing''. Phys. Rev. A 110, 012612 (2024).
https://doi.org/10.1103/PhysRevA.110.012612

[15] Pedro C. S. Costa. ``Qlsp via discrete adiabatic method - source code''. https://github.com/PcostaQuantum/QLSP-via-discrete-adiabatic-method/blob/main/Walk_error_Herm.m (2025). Accessed: 2025-01-24.
https://github.com/PcostaQuantum/QLSP-via-discrete-adiabatic-method/blob/main/Walk_error_Herm.m

[16] Tim Davis and Yifan Hu. ``Suitesparse matrix collection''. https://sparse.tamu.edu/ (2024). Accessed: 2024-10-23.
https://sparse.tamu.edu/

[17] Pedro C. S. Costa. ``Qlsp via randomisation method - source code''. https://github.com/PcostaQuantum/QLSP-via-randomisation-method (2024). Accessed: 2025-01-24.
https://github.com/PcostaQuantum/QLSP-via-randomisation-method

[18] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Limit on the speed of quantum computation in determining parity''. Phys. Rev. Lett. 81, 5442–5444 (1998).
https://doi.org/10.1103/PhysRevLett.81.5442

[19] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. J. ACM 48, 778–797 (2001).
https://doi.org/10.1145/502090.502097

Cited by

[1] Matias Ginzburg and Ugo Marzolino, "Error convergence of quantum linear system solvers", Physical Review A 113 6, 062436 (2026).

[2] Austin Pechan, John Golden, and Daniel O’Malley, "Block encoding of the three-dimensional heterogeneous Poisson equation with application to fracture flow", Physical Review Applied 25 4, 044038 (2026).

[3] Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, and Matthias Rosenkranz, "Sparsity-dependent complexity lower bound of quantum linear system solvers", Quantum Science and Technology 11 3, 035063 (2026).

[4] Marcello Benedetti, Ansis Rosmanis, and Matthias Rosenkranz, "Probabilistic quantum algorithm for Lyapunov equations and matrix inversion", Physical Review Applied 25 4, 044040 (2026).

[5] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, and Yiğit Subaşı, "Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs", PRX Quantum 6 4, 040373 (2025).

[6] Guang Hao Low and Yuan Su, "Quantum linear system algorithm with optimal queries to initial state preparation", Quantum 10, 2041 (2026).

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

[8] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).

[9] Alexander M. Dalzell, "A shortcut to an optimal quantum linear system solver", arXiv:2406.12086, (2024).

[10] David Jennings, Matteo Lostaglio, Robert B. Lowrie, Sam Pallister, and Andrew T. Sornborger, "The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts", Quantum 8, 1553 (2024).

[11] Xi-Ning Zhuang, Zhao-Yun Chen, Ming-Yang Tan, Jiaxuan Zhang, Chuang-Chao Ye, Tian-Hao Wei, Teng-Yang Ma, Cheng Xue, Huan-Yu Liu, Qing-Song Li, Tai-Ping Sun, Xiao-Fan Xu, Yun-Jie Wang, Yu-Chun Wu, and Guo-Ping Guo, "A Pathway to Practical Quantum Advantage in Solving Navier-Stokes Equations", arXiv:2509.08807, (2025).

[12] Erenay Karacan, Conor Mc Keever, Michael Foss-Feig, David Hayes, and Michael Lubasch, "Filter-enhanced adiabatic quantum computing on a digital quantum processor", Physical Review Research 7 3, 033153 (2025).

[13] Tai-Ping Sun, Zhao-Yun Chen, Yun-Jie Wang, Cheng Xue, Huan-Yu Liu, Xi-Ning Zhuang, Xiao-Fan Xu, Yu-Chun Wu, and Guo-Ping Guo, "SparQSim: Simulating Scalable Quantum Algorithms via Sparse Quantum State Representations", arXiv:2503.15118, (2025).

[14] Sophia Simon, Dominic W. Berry, and Rolando D. Somma, "Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems", arXiv:2605.16195, (2026).

[15] Alexander M. Dalzell, Jianqiang Li, and Yuan Su, "Faster quantum linear system solver beyond the condition number", arXiv:2607.07691, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-23 05:56:44) and SAO/NASA ADS (last updated successfully 2026-08-22 16:35:31). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-23 05:56:44: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.