Quantum linear system algorithm with optimal queries to initial state preparation
Summarize this article with:
AbstractQuantum algorithms for linear systems produce the solution state $A^{-1}|b\rangle$ by querying two oracles: $O_A$ that block encodes the coefficient matrix and $O_b$ that prepares the initial state. We present a quantum linear system algorithm making $\mathbf{\Theta}\left(1/\sqrt{p}\right)$ queries to $O_b$, which is optimal in the success probability, and $\mathbf{O}\left(\kappa\log\left(1/p\right)\left(\log\log\left(1/p\right)+\log\left({1}/{\epsilon}\right)\right)\right)$ queries to $O_A$, nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when $p$ is not known $\textit{a priori}$. This contrasts with recent results achieving $\mathbf{O}\left(\kappa\log\left({1}/{\epsilon}\right)\right)$ complexity to both oracles, which, while optimal in $O_A$, is highly suboptimal in $O_b$ as $\kappa$ can be arbitrarily larger than $1/\sqrt{p}$. In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on $p$ using a block preconditioning scheme to nearly match or outperform best previous results based on other methods, which also furnishes an extremely simple quantum linear system algorithm with an optimal query complexity to $O_A$. Underlying our results is a new Variable Time Amplitude Amplification algorithm with Tunable thresholds (Tunable VTAA), which fully characterizes generic nested amplitude amplifications, improves the $\ell_1$-norm input cost scaling of Ambainis to an $\ell_{\frac{2}{3}}$-quasinorm scaling, and admits a deterministic amplification schedule for the quantum linear system problem.Featured image: Illustration of the transition of amplitudes in a variable time amplitude amplification. Popular summarySolving large systems of linear equations is one of the most compelling sources of exponential speedups for quantum computers, and serves as a natural building block for more advanced quantum algorithms. In this work, we present two new quantum linear system solvers, the first achieving an optimal number of queries to initial state preparation using a deterministic amplification schedule, and the second reaching optimal dependence on the coefficient block encoding via a block preconditioning technique. Together, these results offer a remarkably simple approach to the quantum linear system problem, sharpening applications to differential equations and eigenvalue processing.► BibTeX data@article{Low2026quantumlinearsystem, doi = {10.22331/q-2026-03-23-2041}, url = {https://doi.org/10.22331/q-2026-03-23-2041}, title = {Quantum linear system algorithm with optimal queries to initial state preparation}, author = {Low, Guang Hao and Su, Yuan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2041}, month = mar, year = {2026} }► References [1] Abhijeet Alase and Salini Karuvade, Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues, 2024, arXiv:2410.04837, DOI: 10.48550/arXiv.2410.04837. https://doi.org/10.48550/arXiv.2410.04837 arXiv:arXiv:2410.04837 [2] Andris Ambainis, Variable time amplitude amplification and quantum algorithms for linear algebra problems, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), vol. 14, pp. 636–647, 2012, arXiv:1010.4458, DOI: 10.4230/LIPIcs.STACS.2012.636. https://doi.org/10.4230/LIPIcs.STACS.2012.636 arXiv:arXiv:1010.4458 [3] Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs, Improved algorithm and lower bound for variable time quantum search, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), vol. 266, pp. 7:1–7:18, 2023, arXiv:2302.06749, DOI: 10.4230/LIPIcs.TQC.2023.7. https://doi.org/10.4230/LIPIcs.TQC.2023.7 arXiv:arXiv:2302.06749 [4] Dong An, Andrew M. Childs, and Lin Lin, Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters, Communications in Mathematical Physics 407 (2025), no. 1, 19, arXiv:2312.03916, DOI: 10.1007/s00220-025-05509-w. https://doi.org/10.1007/s00220-025-05509-w arXiv:arXiv:2312.03916 [5] 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 (2022), 1–28, arXiv:1909.05500, DOI: 10.1145/3498331. https://doi.org/10.1145/3498331 arXiv:arXiv:1909.05500 [6] Yuto Ashida, Zongping Gong, and Masahito Ueda, Non-Hermitian physics, Advances in Physics 69 (2020), no. 3, 249–435, arXiv:2006.01837, DOI: 10.1080/00018732.2021.1876991. https://doi.org/10.1080/00018732.2021.1876991 arXiv:arXiv:2006.01837 [7] Carl M. Bender, Dorje C. Brody, Hugh F. Jones, and Bernhard K. Meister, Faster than Hermitian quantum mechanics, Physical Review Letters 98 (2007), 040403, arXiv:quant-ph/0609032, DOI: 10.1103/PhysRevLett.98.040403. https://doi.org/10.1103/PhysRevLett.98.040403 arXiv:arXiv:quant-ph/0609032 [8] Dominic W. Berry and Pedro C. S. Costa, Quantum algorithm for time-dependent differential equations using Dyson series, Quantum 8 (2024), 1369, arXiv:2212.03544, DOI: 10.22331/q-2024-06-13-1369. https://doi.org/10.22331/q-2024-06-13-1369 arXiv:arXiv:2212.03544 [9] Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang, Quantum algorithm for linear differential equations with exponentially improved dependence on precision, Communications in Mathematical Physics 356 (2017), 1057–1081, arXiv:1701.03684, DOI: 10.1007/s00220-017-3002-y. https://doi.org/10.1007/s00220-017-3002-y arXiv:arXiv:1701.03684 [10] Dominic W. Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Guang Hao Low, Sergio Boixo, Zhiyan Ding, Lin Lin, Seunghoon Lee, Garnet Kin-Lic Chan, Ryan Babbush, and Nicholas C. Rubin, Rapid initial-state preparation for the quantum simulation of strongly correlated molecules, PRX Quantum 6 (2025), 020327, arXiv:2409.11748, DOI: 10.1103/PRXQuantum.6.020327. https://doi.org/10.1103/PRXQuantum.6.020327 arXiv:arXiv:2409.11748 [11] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53–74, arXiv:quant-ph/0005055, DOI: 10.1090/conm/305/05215. https://doi.org/10.1090/conm/305/05215 arXiv:arXiv:quant-ph/0005055 [12] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery, The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol. 132, pp. 33:1–33:14, 2019, arXiv:1804.01973, DOI: 10.4230/LIPIcs.ICALP.2019.33. https://doi.org/10.4230/LIPIcs.ICALP.2019.33 arXiv:arXiv:1804.01973 [13] Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri, Quantum regularized least squares, Quantum 7 (2023), 988, arXiv:2206.13143, DOI: 10.22331/q-2023-04-27-988. https://doi.org/10.22331/q-2023-04-27-988 arXiv:arXiv:2206.13143 [14] Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, and Ronald de Wolf, Symmetry and quantum query-to-communication simulation, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), vol. 219, pp. 20:1–20:23, 2022, arXiv:2012.05233, DOI: 10.4230/LIPIcs.STACS.2022.20. https://doi.org/10.4230/LIPIcs.STACS.2022.20 arXiv:arXiv:2012.05233 [15] 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 (2017), 1920–1950, arXiv:1511.02306, DOI: 10.1137/16M1087072. https://doi.org/10.1137/16M1087072 arXiv:arXiv:1511.02306 [16] B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned quantum linear system algorithm, Physical Review Letters 110 (2013), 250504, arXiv:1301.2340, DOI: 10.1103/PhysRevLett.110.250504. https://doi.org/10.1103/PhysRevLett.110.250504 arXiv:arXiv:1301.2340 [17] Keith Conrad, $L^p$-spaces for $0