quantum-computing

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

Pedro C.S. Costa, Dong An, Ryan Babbush, and Dominic Berry

10 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractThe 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 summarySolving 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.502097Cited byOn Crossref's cited-by service no data on citing works was found (last attempt 2025-10-24 00:35:34). Could not fetch ADS cited-by data during last attempt 2025-10-24 00:35:34: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractThe 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 summarySolving 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''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

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

Tags

Source Information