{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:10:58Z","timestamp":1782263458869,"version":"3.54.5"},"reference-count":55,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T00:00:00Z","timestamp":1636329600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["24.003.037"],"award-info":[{"award-number":["24.003.037"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03ba<\/mml:mi><\/mml:math>, the condition number of the coefficient matrix <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>A<\/mml:mi><\/mml:math>, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03ba<\/mml:mi><\/mml:math> [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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msqrt><mml:mi>\u03ba<\/mml:mi><\/mml:msqrt><\/mml:math>, 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03ba<\/mml:mi><\/mml:math> also when <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>A<\/mml:mi><\/mml:math> 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03ba<\/mml:mi><\/mml:math>: the first is based on efficiently implementing a matrix-block-encoding of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>A<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\u2212<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math>, the second constructs a decomposition of the form <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>A<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>L<\/mml:mi><mml:msup><mml:mi>L<\/mml:mi><mml:mo>\u2020<\/mml:mo><\/mml:msup><\/mml:math> to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.<\/jats:p>","DOI":"10.22331\/q-2021-11-08-573","type":"journal-article","created":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T17:14:42Z","timestamp":1636391682000},"page":"573","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":15,"title":["On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number"],"prefix":"10.22331","volume":"5","author":[{"given":"Davide","family":"Orsucci","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Kommunikation und Navigation, Deutsches Zentrum f\u00fcr Luft- und Raumfahrt (DLR), M\u00fcnchener Str. 20, 82234 We\u00dfling, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vedran","family":"Dunjko","sequence":"additional","affiliation":[{"name":"Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2021,11,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103, 150502 (2009) [arXiv:0811.3171].","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"1","unstructured":"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)."},{"key":"2","doi-asserted-by":"crossref","unstructured":"Y. Saad, Iterative methods for sparse linear systems, SIAM (2003).","DOI":"10.1137\/1.9780898718003"},{"key":"3","unstructured":"A. Ambainis, Variable time amplitude amplification and quantum algorithms for linear algebra problems, 29th Symposium on Theoretical Aspects of Computer Science 14, 636\u2013647 (2012) [arXiv:1010.4458]."},{"key":"4","doi-asserted-by":"publisher","unstructured":"A. M. Childs, R. Kothari, and R. D. Somma, Quantum linear systems algorithm with exponentially improved dependence on precision, SIAM J. Comput. 46, 1920\u20131950 (2017) [arXiv:1511.02306].","DOI":"10.1137\/16M1087072"},{"key":"5","doi-asserted-by":"publisher","unstructured":"L. Wossnig, Z. Zhao, and A. Prakash, Quantum linear system algorithm for dense matrices, Physical Review Letters 120, 050502 (2018) [arXiv:1704.06174].","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Y. Suba\u015f\u0131, 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].","DOI":"10.1103\/PhysRevLett.122.060504"},{"key":"7","unstructured":"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)."},{"key":"8","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevA.99.012320"},{"key":"9","unstructured":"C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Suba\u015f\u0131, L. Cincio, and P. J. Coles, Variational quantum linear solver: A hybrid algorithm for linear systems, arXiv:1909.05820 (2019)."},{"key":"10","unstructured":"H. Y. Huang, K. Bharti, and P. Rebentrost, Near-term quantum algorithms for linear systems of equations, arXiv:1909.07344."},{"key":"11","doi-asserted-by":"publisher","unstructured":"L. Lin and Y. Tong, Optimal quantum eigenstate filtering with application to solving quantum linear systems, Quantum 4, 361 (2020) [arXiv:1910.14596].","DOI":"10.22331\/q-2020-11-11-361"},{"key":"12","doi-asserted-by":"publisher","unstructured":"S. Aaronson, Read the fine print, Nature Physics 11, 291-293 (2015) [citeseerx].","DOI":"10.1038\/nphys3272"},{"key":"13","doi-asserted-by":"publisher","unstructured":"A. Montanaro and S. Pallister, Quantum algorithms and the finite element method, Physical Review A 93, 032324 (2016) [arXiv:1512.05903].","DOI":"10.1103\/PhysRevA.93.032324"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PRXQuantum.2.010103"},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. N. Chowdhury and R. D. Somma, Quantum algorithms for Gibbs sampling and hitting-time estimation, Quant. Inf. Comp. 17, 0041\u20130064 (2017) [arXiv:1603.02940].","DOI":"10.26421\/QIC17.1-2"},{"key":"16","doi-asserted-by":"publisher","unstructured":"B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned quantum linear system algorithm, Physical Review Letters 110, 250504 (2013) [arXiv:1301.2340].","DOI":"10.1103\/PhysRevLett.110.250504"},{"key":"17","unstructured":"J. R. Shewchuk, An introduction to the conjugate gradient method without the agonizing pain, Carnegie Mellon University (1994)."},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Chakraborty, A. Gily\u00e9n, 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].","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"19","doi-asserted-by":"publisher","unstructured":"C. Shao and H. Xiang, Quantum circulant preconditioner for linear system of equations, Physical Review A 98, 062321 [arXiv:1807.04563].","DOI":"10.1103\/PhysRevA.98.062321"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevA.104.032422"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevA.103.042422"},{"key":"22","unstructured":"A. C. Vazquez, R. Hiptmair, and S. Woerner, Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation, arXiv:2009.04484 (2020)."},{"key":"23","doi-asserted-by":"publisher","unstructured":"G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Physical Review Letters 118, 010501 (2017) [arXiv:1606.02685].","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"24","doi-asserted-by":"publisher","unstructured":"A. Gily\u00e9n, 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\u2013204 (2019) [arXiv:1806.01838].","DOI":"10.1145\/3313276.3316366"},{"key":"25","doi-asserted-by":"publisher","unstructured":"A. M. Childs and N. Wiebe, Hamiltonian Simulation Using Linear Combinations of Unitary Operations, Quantum Information & Computation [arXiv:1202.5822].","DOI":"10.26421\/QIC12.11-12"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"27","doi-asserted-by":"publisher","unstructured":"G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).","DOI":"10.22331\/q-2019-07-12-163"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. C. Schaeffer, Inequalities of A. Markoff and S. Bernstein for polynomials and related functions, Bulletin of the American Mathematical Society 47, 565\u2013579(1941).","DOI":"10.1090\/S0002-9904-1941-07510-5"},{"key":"29","doi-asserted-by":"crossref","unstructured":"G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305, 53\u201374 (2002) [arXiv:0005055].","DOI":"10.1090\/conm\/305\/05215"},{"key":"30","unstructured":"See e.g. the Cholesky decomposition page on Wikipedia."},{"key":"31","doi-asserted-by":"publisher","unstructured":"R. D. Somma and S. Boixo, Spectral gap amplification, SIAM Journal on Computing 42, 593-610 (2013) [arXiv:1110.2494].","DOI":"10.1137\/120871997"},{"key":"32","unstructured":"M. A. Nielsen, and I. Chuang, Quantum computation and quantum information, Cambridge University Press (2000)."},{"key":"33","unstructured":"L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv:0208112 (2002)."},{"key":"34","doi-asserted-by":"publisher","unstructured":"V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical Review Letters 100, 160501 (2008) [arXiv:0708.1879].","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"35","unstructured":"I. Kerenidis and A. Prakash, Quantum recommendation systems, arXiv:1603.08675."},{"key":"36","doi-asserted-by":"crossref","unstructured":"M. Boyer,G. Brassard, P. H\u00f8yer and A. Tapp, Tight bounds on quantum searching, , 493\u2013505 (1998) [arXiv:9605034].","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"37","unstructured":"Andr\u00e1s Gily\u00e9n, private communication."},{"key":"38","unstructured":"R. Chao, D. Ding, A. Gily\u00e9n, C. Huang and M. Szegedy, Finding angles for quantum signal processing with machine precision, arXiv:2003.02831 (2020)."},{"key":"39","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevA.103.042419"},{"key":"40","unstructured":"See e.g. the Gershgorin circle theorem page on Wikipedia."},{"key":"41","doi-asserted-by":"publisher","unstructured":"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\u20131010 (2006) [arXiv:0406176].","DOI":"10.1109\/TCAD.2005.855930"},{"key":"42","doi-asserted-by":"publisher","unstructured":"R. Merris, Laplacian matrices of graphs: a survey, Linear algebra and its applications 197, 143\u2013176 (1994).","DOI":"10.1016\/0024-3795(94)90486-3"},{"key":"43","doi-asserted-by":"publisher","unstructured":"D. A. Spielman, Algorithms, graph theory, and linear equations in Laplacian matrices, Proceedings of the International Congress of Mathematicians 2010, 2698\u20132722 (2010).","DOI":"10.1142\/9789814324359_0164"},{"key":"44","doi-asserted-by":"publisher","unstructured":"L. K. Grover, Synthesis of quantum superpositions by quantum computation, Physical Review Letters 85, 1334 (2000).","DOI":"10.1103\/PhysRevLett.85.1334"},{"key":"45","doi-asserted-by":"publisher","unstructured":"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].","DOI":"10.1103\/PhysRevLett.122.020502"},{"key":"46","doi-asserted-by":"publisher","unstructured":"R. D. Somma and Y. Suba\u015f\u0131, Quantum state verification in the quantum linear systems problem, PRX Quantum 2, 010315 (2021) [arXiv:2007.15698].","DOI":"10.1103\/PRXQuantum.2.010315"},{"key":"47","unstructured":"A. Gily\u00e9n, Quantum walk based search methods and algorithmic applications, Doctoral dissertation, E\u00f6tv\u00f6s Lor\u00e1nd University (2014)."},{"key":"48","doi-asserted-by":"publisher","unstructured":"E. Malvetti, R. Iten, and R. Colbeck, Quantum Circuits for Sparse Isometries arXiv:2006.00016 (2020).","DOI":"10.22331\/q-2021-03-15-412"},{"key":"49","unstructured":"X. Jiang, Minimum rank positive semidefinite matrix completion with chordal sparsity pattern, Doctoral dissertation, UCLA (2017)."},{"key":"50","doi-asserted-by":"publisher","unstructured":"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\u2013393 (1999) [arXiv:9804066].","DOI":"10.1145\/301250.301349"},{"key":"51","doi-asserted-by":"publisher","unstructured":"S. U. Pillai, T. Suel, and S. Cha, The Perron-Frobenius theorem: some of its applications, IEEE Signal Processing Magazine 22, 62\u201375 (2005).","DOI":"10.1109\/MSP.2005.1406483"},{"key":"52","doi-asserted-by":"crossref","unstructured":"S. Arora and B. Barak, Computational complexity: a modern approach, Cambridge University Press (2009).","DOI":"10.1017\/CBO9780511804090"},{"key":"53","doi-asserted-by":"crossref","unstructured":"J. C. Mason, and D. C. Handscomb, Chebyshev polynomials, CRC press (2002).","DOI":"10.1201\/9781420036114"},{"key":"54","doi-asserted-by":"publisher","unstructured":"J. Bausch and E. Crosson, Analysis and limitations of modified circuit-to-Hamiltonian constructions, Quantum 2, 94 (2018).","DOI":"10.22331\/q-2018-09-19-94"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-11-08-573\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T17:14:51Z","timestamp":1636391691000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-11-08-573\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,8]]},"references-count":55,"URL":"https:\/\/doi.org\/10.22331\/q-2021-11-08-573","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,8]]},"article-number":"573"}}