On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
Davide Orsucci1 and Vedran Dunjko2
1Institut für Kommunikation und Navigation, Deutsches Zentrum für Luft- und Raumfahrt (DLR), Münchener Str. 20, 82234 Weßling, Germany
2Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is $\kappa$, the condition number of the coefficient matrix $A$, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in $\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as $\sqrt{\kappa}$, a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in $\kappa$ also when $A$ is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in $\kappa$: the first is based on efficiently implementing a matrix-block-encoding of $A^{-1}$, the second constructs a decomposition of the form $A = L L^\dagger$ to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.
Featured image: Qualitative bi-logarithmic plots of the runtimes of quantum linear system solvers for general matrices (red) and positive-definite matrices (blue). In the left plot we represent the query complexity for methods based on direct matrix-vector multiplication in terms of the variable $||A^{-1}|\textbf{b}\rangle||^{-1}$. In the right plot we represent the query complexity for methods based on Variable-Time Amplitude Amplification in terms of the variable $\Gamma_{A,\textbf{b}} = \sqrt{\kappa} \,\frac{||A^{-1/2}|\textbf{b}\rangle||}{||A^{-1}|\textbf{b}\rangle||}$. In both plots we express all the variables in units of powers of $\kappa$ (the condition number of $A$) assuming that $\kappa \gg 1$.
@article{Orsucci2021solvingclassesof, doi = {10.22331/q-2021-11-08-573}, url = {https://doi.org/10.22331/q-2021-11-08-573}, title = {On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number}, author = {Orsucci, Davide and Dunjko, Vedran}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {5}, pages = {573}, month = nov, year = {2021} }
[1] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103, 150502 (2009) [arXiv:0811.3171].
[2] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes: The Art of Scientific Computing, Third Edition, Cambridge University Press (2007).
[3] Y. Saad, Iterative methods for sparse linear systems, SIAM (2003).
[4] A. Ambainis, Variable time amplitude amplification and quantum algorithms for linear algebra problems, 29th Symposium on Theoretical Aspects of Computer Science 14, 636–647 (2012) [arXiv:1010.4458].
http:/​/​drops.dagstuhl.de/​opus/​volltexte/​2012/​3426/​
[5] A. M. Childs, R. Kothari, and R. D. Somma, Quantum linear systems algorithm with exponentially improved dependence on precision, SIAM J. Comput. 46, 1920–1950 (2017) [arXiv:1511.02306].
https:/​/​doi.org/​10.1137/​16M1087072
[6] L. Wossnig, Z. Zhao, and A. Prakash, Quantum linear system algorithm for dense matrices, Physical Review Letters 120, 050502 (2018) [arXiv:1704.06174].
[7] Y. Subaşı, R. D. Somma, and D. Orsucci. Quantum algorithms for linear systems of equations inspired by adiabatic quantum computing, Physical Review Letters 122, 060504 (2019) [arXiv:1805.10549].
[8] Dong An and Lin Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, arXiv:1909.05500 (2019).
[9] J. Wen, X. Kong, S. Wei, B. Wang, T. Xin, and G. Long, Experimental realization of quantum algorithms for a linear system inspired by adiabatic quantum computing, Physical Review A 99, 012320 (2019) [arXiv:1806.03295].
[10] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subaşı, L. Cincio, and P. J. Coles, Variational quantum linear solver: A hybrid algorithm for linear systems, arXiv:1909.05820 (2019).
[11] H. Y. Huang, K. Bharti, and P. Rebentrost, Near-term quantum algorithms for linear systems of equations, arXiv:1909.07344.
[12] L. Lin and Y. Tong, Optimal quantum eigenstate filtering with application to solving quantum linear systems, Quantum 4, 361 (2020) [arXiv:1910.14596].
[13] S. Aaronson, Read the fine print, Nature Physics 11, 291-293 (2015) [citeseerx].
https:/​/​doi.org/​10.1038/​nphys3272
[14] A. Montanaro and S. Pallister, Quantum algorithms and the finite element method, Physical Review A 93, 032324 (2016) [arXiv:1512.05903].
[15] R. Babbush, J. McClean, C. Gidney, S. Boixo, and H. Neven, Focus beyond quadratic speedups for error-corrected quantum advantage, PRX Quantum 2 (2021) [arXiv:2011.04149].
[16] A. N. Chowdhury and R. D. Somma, Quantum algorithms for Gibbs sampling and hitting-time estimation, Quant. Inf. Comp. 17, 0041–0064 (2017) [arXiv:1603.02940].
https:/​/​doi.org/​10.26421/​QIC17.1-2
[17] B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned quantum linear system algorithm, Physical Review Letters 110, 250504 (2013) [arXiv:1301.2340].
[18] J. R. Shewchuk, An introduction to the conjugate gradient method without the agonizing pain, Carnegie Mellon University (1994).
https:/​/​www.cs.cmu.edu/​~quake-papers/​painless-conjugate-gradient.pdf
[19] S. Chakraborty, A. Gilyén, and S. 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) [arXiv:1804.01973].
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33
[20] C. Shao and H. Xiang, Quantum circulant preconditioner for linear system of equations, Physical Review A 98, 062321 [arXiv:1807.04563].
[21] Y. Tong, D. An, N. Wiebe, and L. Lin. Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions, Physical Review A 104, 032422 [arXiv:2008.13295].
[22] B. Wu, M. Ray, L. Zhao, X. Sun, and P. Rebentrost, Quantum-classical algorithms for skewed linear systems with optimized Hadamard test, Physical Review A 103, 042422 [arXiv:2009.13288].
[23] A. C. Vazquez, R. Hiptmair, and S. Woerner, Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation, arXiv:2009.04484 (2020).
[24] G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Physical Review Letters 118, 010501 (2017) [arXiv:1606.02685].
[25] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204 (2019) [arXiv:1806.01838].
[26] A. M. Childs and N. Wiebe, Hamiltonian Simulation Using Linear Combinations of Unitary Operations, Quantum Information & Computation [arXiv:1202.5822].
https:/​/​doi.org/​10.26421/​QIC12.11-12
[27] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari and R. D. Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Physical Review Letters 114, 090502 (2015) [arXiv:1412.4687].
[28] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
[29] A. C. Schaeffer, Inequalities of A. Markoff and S. Bernstein for polynomials and related functions, Bulletin of the American Mathematical Society 47, 565–579(1941).
[30] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53–74 (2002) [arXiv:0005055].
[31] See e.g. the Cholesky decomposition page on Wikipedia.
https:/​/​en.wikipedia.org/​wiki/​Cholesky_decomposition
[32] R. D. Somma and S. Boixo, Spectral gap amplification, SIAM Journal on Computing 42, 593-610 (2013) [arXiv:1110.2494].
[33] M. A. Nielsen, and I. Chuang, Quantum computation and quantum information, Cambridge University Press (2000).
[34] L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv:0208112 (2002).
[35] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical Review Letters 100, 160501 (2008) [arXiv:0708.1879].
[36] I. Kerenidis and A. Prakash, Quantum recommendation systems, arXiv:1603.08675.
[37] M. Boyer,G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, , 493–505 (1998) [arXiv:9605034].
[38] András Gilyén, private communication.
[39] R. Chao, D. Ding, A. Gilyén, C. Huang and M. Szegedy, Finding angles for quantum signal processing with machine precision, arXiv:2003.02831 (2020).
[40] Y. Dong, X. Meng, K. B. Whaley and L. Lin, Efficient phase factor evaluation in quantum signal processing, Phys. Rev. A 103, 042419 (2021) [arXiv:2002.11649].
[41] See e.g. the Gershgorin circle theorem page on Wikipedia.
https:/​/​en.wikipedia.org/​wiki/​Gershgorin_circle_theorem
[42] V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006) [arXiv:0406176].
[43] R. Merris, Laplacian matrices of graphs: a survey, Linear algebra and its applications 197, 143–176 (1994).
https:/​/​doi.org/​10.1016/​0024-3795(94)90486-3
[44] D. A. Spielman, Algorithms, graph theory, and linear equations in Laplacian matrices, Proceedings of the International Congress of Mathematicians 2010, 2698–2722 (2010).
https:/​/​doi.org/​10.1142/​9789814324359_0164
[45] L. K. Grover, Synthesis of quantum superpositions by quantum computation, Physical Review Letters 85, 1334 (2000).
[46] Y. R. Sanders, G. H. Low, A. Scherer and D. W. Berry, Black-box quantum state preparation without arithmetic, Physical Review Letters 122, 020502 (2019) [arXiv:1807.03206].
[47] R. D. Somma and Y. Subaşı, Quantum state verification in the quantum linear systems problem, PRX Quantum 2, 010315 (2021) [arXiv:2007.15698].
[48] A. Gilyén, Quantum walk based search methods and algorithmic applications, Doctoral dissertation, Eötvös Loránd University (2014).
[49] E. Malvetti, R. Iten, and R. Colbeck, Quantum Circuits for Sparse Isometries arXiv:2006.00016 (2020).
[50] X. Jiang, Minimum rank positive semidefinite matrix completion with chordal sparsity pattern, Doctoral dissertation, UCLA (2017).
https:/​/​escholarship.org/​uc/​item/​8p2397x1
[51] A. Nayak and F. Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the 31st annual ACM symposium on Theory of computing, 384–393 (1999) [arXiv:9804066].
[52] S. U. Pillai, T. Suel, and S. Cha, The Perron-Frobenius theorem: some of its applications, IEEE Signal Processing Magazine 22, 62–75 (2005).
https:/​/​doi.org/​10.1109/​MSP.2005.1406483
[53] S. Arora and B. Barak, Computational complexity: a modern approach, Cambridge University Press (2009).
[54] J. C. Mason, and D. C. Handscomb, Chebyshev polynomials, CRC press (2002).
[55] J. Bausch and E. Crosson, Analysis and limitations of modified circuit-to-Hamiltonian constructions, Quantum 2, 94 (2018).
[1] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, and Patrick Rebentrost, "Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test", Physical Review A 103 4, 042422 (2021).
[2] Tongyang Li, Xinzhao Wang, and Shengyu Zhang, "A Unified Quantum Algorithm Framework for Estimating Properties of Discrete Probability Distributions", arXiv:2212.01571, (2022).
[3] Changpeng Shao and Ashley Montanaro, "Faster quantum-inspired algorithms for solving linear systems", arXiv:2103.10309, (2021).
[4] Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi, "Improving quantum linear system solvers via a gradient descent perspective", arXiv:2109.04248, (2021).
The above citations are from SAO/NASA ADS (last updated successfully 2023-01-27 02:27:57). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2023-01-27 02:27:55).