In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.
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.
Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number κ, the sparsity s of the input matrix, and the target precision ε. The dependence on κ and ε is already well understood through the lower bound Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity s is included, however, the expected lower bound has long been conjectured to be Ω(κslog(1/ε)). Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound Ω(κs) for constant error ε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UA and the right-hand side through a state-preparation oracle Ub. The optimal query complexities of these two oracles are known separately: O(κlog(1/ε)) queries to UA and O(κ/s) queries to Ub, where s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open.
We resolve this question affirmatively. Given a constant-factor estimate of s, we give a quantum linear-system algorithm that prepares the normalized solution to error ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UA and O(κ/s) queries to Ub. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy.
We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog(1/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
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.
Given a linear system of equations Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is (1+O(ε))κln(22/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog(1/ε)) complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of 56κ+1.05κln(1/ε)+o(κ) for the complexity of our optimal QLSS.
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.
We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ∥H∥1→2. For tΛ≥1/2, simulation with operator-norm error ε uses O(tΛd+dlog(2/ε)) sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1 and tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of Λ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters.
As applications, we obtain O(κdpolylog(κ/ε)) queries for solving d-sparse quantum linear systems with ∥A∥≤1 and ∥A−1∥≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most d nonzero entries per row and column using O(dlog(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(N) queries for arbitrary N×N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].