On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
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
Published: | 2021-11-08, volume 5, page 573 |
Eprint: | arXiv:2101.11868v3 |
Doi: | https://doi.org/10.22331/q-2021-11-08-573 |
Citation: | Quantum 5, 573 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
![](https://quantum-journal.org/wp-content/uploads/2021/11/RuntimesPlots.png)
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$.
► BibTeX data
► References
[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].
https://doi.org/10.1103/PhysRevLett.103.150502
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].
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
arXiv:1511.02306
[6] L. Wossnig, Z. Zhao, and A. Prakash, Quantum linear system algorithm for dense matrices, Physical Review Letters 120, 050502 (2018) [arXiv:1704.06174].
https://doi.org/10.1103/PhysRevLett.120.050502
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].
https://doi.org/10.1103/PhysRevLett.122.060504
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).
arXiv:1909.05500
[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].
https://doi.org/10.1103/PhysRevA.99.012320
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).
arXiv:1909.05820
[11] H. Y. Huang, K. Bharti, and P. Rebentrost, Near-term quantum algorithms for linear systems of equations, arXiv:1909.07344.
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].
https://doi.org/10.22331/q-2020-11-11-361
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].
https://doi.org/10.1103/PhysRevA.93.032324
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].
https://doi.org/10.1103/PRXQuantum.2.010103
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
arXiv:1603.02940
[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].
https://doi.org/10.1103/PhysRevLett.110.250504
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
arXiv:1804.01973
[20] C. Shao and H. Xiang, Quantum circulant preconditioner for linear system of equations, Physical Review A 98, 062321 [arXiv:1807.04563].
https://doi.org/10.1103/PhysRevA.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].
https://doi.org/10.1103/PhysRevA.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].
https://doi.org/10.1103/PhysRevA.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).
arXiv:2009.04484
[24] G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Physical Review Letters 118, 010501 (2017) [arXiv:1606.02685].
https://doi.org/10.1103/PhysRevLett.118.010501
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].
https://doi.org/10.1145/3313276.3316366
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
arXiv:1202.5822
[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].
https://doi.org/10.1103/PhysRevLett.114.090502
arXiv:1412.4687
[28] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[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).
https://doi.org/10.1090/S0002-9904-1941-07510-5
[30] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53–74 (2002) [arXiv:0005055].
arXiv:quant-ph/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].
https://doi.org/10.1137/120871997
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).
arXiv:quant-ph/0208112
[35] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical Review Letters 100, 160501 (2008) [arXiv:0708.1879].
https://doi.org/10.1103/PhysRevLett.100.160501
arXiv:0708.1879
[36] I. Kerenidis and A. Prakash, Quantum recommendation systems, arXiv:1603.08675.
arXiv:1603.08675
[37] M. Boyer,G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, , 493–505 (1998) [arXiv:9605034].
arXiv:quant-ph/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).
arXiv:2003.02831
[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].
https://doi.org/10.1103/PhysRevA.103.042419
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].
https://doi.org/10.1109/TCAD.2005.855930
arXiv:quant-ph/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).
https://doi.org/10.1103/PhysRevLett.85.1334
[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].
https://doi.org/10.1103/PhysRevLett.122.020502
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].
https://doi.org/10.1103/PRXQuantum.2.010315
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).
https://doi.org/10.22331/q-2021-03-15-412
arXiv:2006.00016
[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].
https://doi.org/10.1145/301250.301349
arXiv:quant-ph/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).
https://doi.org/10.22331/q-2018-09-19-94
Cited by
[1] Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi, "An optimal linear-combination-of-unitaries-based quantum linear system solver", ACM Transactions on Quantum Computing 3649320 (2024).
[2] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao, "A theory of quantum differential equation solvers: limitations and fast-forwarding", arXiv:2211.05246, (2022).
[3] Changpeng Shao and Ashley Montanaro, "Faster quantum-inspired algorithms for solving linear systems", arXiv:2103.10309, (2021).
[4] 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).
[5] Qian Zuo and Tongyang Li, "Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems", arXiv:2307.06627, (2023).
[6] Osama Muhammad Raisuddin and Suvranu De, "Quantum Relaxation for Linear Systems in Finite Element Analysis", arXiv:2308.01377, (2023).
[7] Tongyang Li, Xinzhao Wang, and Shengyu Zhang, "A Unified Quantum Algorithm Framework for Estimating Properties of Discrete Probability Distributions", arXiv:2212.01571, (2022).
[8] 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 Crossref's cited-by service (last updated successfully 2024-03-28 02:10:58) and SAO/NASA ADS (last updated successfully 2024-03-28 02:10:59). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.