Since Harrow [A. W. Harrow, A. Hassidim, and S. Lloyd, ] showed that a system of linear equations with N variables and condition number κ can be solved on a quantum computer in poly [ log ( N ) , κ ] time, exponentially faster than any classical algorithms, its improvements and applications have been extensively investigated. The state-of-the-art quantum algorithm for this problem is due to Costa [P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry, ], with optimal query complexity Θ ( κ ) . An important question that is left is whether parallelism can bring further optimization. In this paper, we study the limitation of parallel quantum computing on this problem. We show that any quantum algorithm for solving systems of linear equations with time complexity poly [ log ( N ) , κ ] has a lower bound of Ω ( κ ) on the depth of queries, which is tight up to a constant factor. Published by the American Physical Society 2024
Since Harrow [A. W. Harrow, A. Hassidim, and S. Lloyd, ] showed that a system of linear equations with N variables and condition number κ can be solved on a quantum computer in poly [ log ( N ) , κ ] time, exponentially faster than any classical algorithms, its improvements and applications have been extensively investigated. The state-of-the-art quantum algorithm for this problem is due to Costa [P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry, ], with optimal query complexity Θ ( κ ) . An important question that is left is whether parallelism can bring further optimization. In this paper, we study the limitation of parallel quantum computing on this problem. We show that any quantum algorithm for solving systems of linear equations with time complexity poly [ log ( N ) , κ ] has a lower bound of Ω ( κ ) on the depth of queries, which is tight up to a constant factor. Published by the American Physical Society 2024
This review anatomises Bravo-Prieto, Harrow and Kothari (2026) on the query complexity of the quantum linear systems problem in the standard sparse-matrix oracle model, which they show is Θ(κ √d log(1/ε)). The upper bound is a reduction: after an enlargement and per-entry normalisation, a contraction whose inverse norm is at most 5κ √d is handed to the existing block-encoded solver of Costa, An, Sanders, Su, Babbush and Berry (2022), giving O(κ √d log(1/ε)) sparse-oracle queries. The matching lower bound multiplies unstructured search by a parity of length Θ(κ log(1/ε)); the quantum XOR lemma of Lee and Roland (2012) converts a vanishing advantage into the joint query lower bound. A corollary implements an N × N unitary from its entries with O(√N log(1/ε)) queries, closing the black-box unitary question posed by Berry and Childs (2012). Primary source: Bravo-Prieto, C., Harrow, A.W. and Kothari, R. (2026), An Optimal Quantum Linear Systems Algorithm, arXiv:2609.35660. This deposit is a KSCCN review by Syed Muntasir Mamun, not the BHK paper. KSCCN review article, 3 October 2026. Dr. Syed Muntasir Mamun, ORCID 0000-0001-6845-2853. The views expressed are those of the author.
Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number κ and sparsity s of the linear system, and the target error ε. To date, the best known query-complexity lower bound is Ω(κlog(1/ε)), which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity s of the linear system, it has become folklore that it should read as Ω(κslog(1/ε)). In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of Ω(κs) for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters κ,s,ε remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.
Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.
Quantum computing enables the efficient resolution of complex problems, often outperforming classical methods across various applications. In 2009, Harrow, Hassidim and Lloyd proposed an algorithm for solving linear systems of equations, demonstrating exponential speedup (under ideal conditions) with a complexity of poly(logN), in contrast to classical approaches, which in the general case exhibit a complexity of O(N3), although they can achieve O(N) in specific cases involving sparse matrices. This algorithm holds promise for advancements in machine learning, the solution of differential equations, linear regression, and cryptographic analysis. However, its structure is intricate, and there is a notable lack of detailed instructional materials in the literature. In this context, this paper presents a tutorial addressing the physical and mathematical foundations of the HHL algorithm, aimed at undergraduate students, explaining its theoretical construction and its implementation for solving linear equation systems. After discussing the underlying mathematical and physical concepts, we present numerical examples that illustrate the evolution of the quantum circuit. Finally, the algorithm's complexity, limitations, and future prospects are analyzed. The examples are compared with their classical simulations, allowing for an operational assessment of the algorithm's performance.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.
This review anatomises the argument of Bravo-Prieto, Harrow and Kothari (2026), hereafter BHK, that the query complexity of the quantum linear systems problem (QLSP) in the standard sparse-matrix oracle model is ( d log(1/ )). The paper closes a gap left by two incomparable upper bounds the discrete-adiabatic bound O( d log(1/ )) of Costa, An, Sanders, Su, Babbush and Berry (2022) and the spectral-norm simulation bound d ( d/ )o(1) of Low (2019) and by two partial lower bounds, ( log(1/ )) and ( d). The upper bound is not a new inversion primitive. It is a linear-algebraic enlargement: the factorisation A/ d = F T is split into two equations, each matrix entry is normalised separately, and the resulting contraction M, with M 5 d, is handed to an existing block-encoded solver. The lower bound multiplies unstructured search by a parity of length ( log(1/ )), with the quantum XOR lemma of Lee and Roland (2012) converting a vanishing advantage into a joint query lower bound. A corollary resolves the Berry and Childs (2012) question on black-box unitary implementation at O( N log(1/ )). The review reconstructs the proof anatomy, states pros and cons with explicit scope conditions, and compares BHK with fifteen neighbouring models spanning phase estimation, variable-time amplification, linear combinations of unitaries, adiabatic schedules, quantum singular value transformation, dense QRAM access, preconditioning, and the concurrent lower bound of Patel (2026). Also available on Academia.edu: https://www.academia.edu/attachments/134662881/download_file?s=portfolio