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 κ , 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 κ [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 κ , 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 κ 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 κ : the first is based on efficiently implementing a matrix-block-encoding of A−1 , the second constructs a decomposition of the form A=LL† to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.
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 κ , 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 κ [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 κ , 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 κ 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 κ : the first is based on efficiently implementing a matrix-block-encoding of A−1 , the second constructs a decomposition of the form A=LL† to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution ∣x⟩ of linear system Ax=∣b⟩ to accuracy ε with complexity independent of the condition number κ=∥A−1∥. We focus on the standard input model where A is accessed through a block encoding and ∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes A and ∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩ and O(κeffpolylog(εκeff)) queries to A. We prove a family of upper bounds on the effective condition number, including κeff≤ε1/t∥(A†A)−t/2∣x⟩∥1/t for positive even integer t and κeff≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t for positive odd t, overcoming the κ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3ε∥A−1†∣x⟩∥ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.
Given a matrix A of dimension M×N and a vector b, the quantum linear system (QLS) problem asks for the preparation of a quantum state ∣y⟩ proportional to the solution of Ay=b. Existing QLS algorithms have runtimes that scale linearly with the condition number κ(A), the sparsity of A, and logarithmically with inverse precision, but often overlook structural properties of b, whose alignment with A's eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector b. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix H=[A,−b], the inverse precision, the ℓ2 norm of the solution y=A+b, and a new instance-dependent parameter ET=∑i=1Mpi2⋅di, where p=(AA⊤)+b, and di denotes the squared ℓ2 norm of the i-th row of H. We also introduce a structure-aware rescaling technique tailored to the solution y=A+b. Unlike left preconditioning methods, which transform the linear system to DAy=Db, our approach applies a right rescaling matrix, reformulating the linear system as ADz=b. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.
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.
Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.
Quantum algorithms for linear systems produce the solution state A − 1 | b ⟩ 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 Θ ( 1 / p ) queries to O b , which is optimal in the success probability, and O ( κ log ( 1 / p ) ( log log ( 1 / p ) + log ( 1 / ϵ ) ) ) 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 a priori . This contrasts with recent results achieving O ( κ log ( 1 / ϵ ) ) complexity to both oracles, which, while optimal in O A , is highly suboptimal in O b as κ can be arbitrarily larger than 1 / 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 p