Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.35660

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 9 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper determines the quantum query complexity of preparing a normalized solution state for a sparse linear system $A\vec x=\vec b$. In the standard sparse-matrix access model, with sparsity bound $d$, $\|A\|\leq1$, $\|A^{-1}\|\leq\kappa$, and trace-distance error $\epsilon$, it proves matching bounds $\Theta(\kappa\sqrt d\log(1/\epsilon))$. This combines the parameter dependences previously achieved separately by algorithms costing $O(\kappa d\log(1/\epsilon))$ and $\kappa\sqrt d(\kappa d/\epsilon)^{o(1)}$. The upper bound replaces the original system by an enlarged system whose matrix $M$ has an exact block encoding using $O(1)$ sparse-oracle queries and satisfies $\|M^{-1}\|\leq5\kappa\sqrt d$. Auxiliary variables split a matrix product into separate constraints, while entry-dependent normalization avoids preparing entire matrix rows. The desired solution is recovered from the enlarged solution with probability at least $1/3$, allowing an existing block-encoded linear-systems algorithm to achieve the stated complexity. The lower bound encodes a circuit computing the parity of $\Theta(\kappa\log(1/\epsilon))$ independent search-derived bits into a geometrically weighted history state. A quantum XOR lemma supplies hardness even when extracting the answer yields only a small advantage over random guessing. The construction also gives a constant-normalization block encoding of any Hermitian norm-bounded $d$-sparse matrix using $O(\sqrt d\log(1/\eta))$ queries at operator-norm error $\eta$, and implements an entry-oracle unitary using $O(\sqrt N\log(1/\epsilon))$ queries, optimal for constant error. The complexity statements count matrix-oracle queries, not total gates or input-state preparation; the output is a quantum state, not a classical solution vector. Multiparameter lower bounds assume sufficiently large parameters.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
20 pages

Related papers

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers

Dhrumil Patel

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 $\varepsilon$. The dependence on $κ$ and $\varepsilon$ is already well understood through the lower bound $Ω(κ\log(1/\varepsilon))$, 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 $Ω(κ\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $Ω(κ\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $Ω(κ\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.

quant-pharXiv:2609.22445•Sep 22, 2026•5 citations

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. 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 $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. 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/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686•Sep 29, 2026•1 citation

Solving quantum linear system problem with near-optimal complexity.

Lin Lin, Yu Tong

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal $\mathcal{\widetilde{O}}(d\kappa\log(1/\epsilon))$ query complexity for a $d$-sparse matrix, where $\kappa$ is the condition number, and $\epsilon$ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

•Oct 31, 2019•4 citations

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

Hitomi Mori, Yuta Kikuchi, Marcello Benedetti +1 more

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 $Ω( κ\sqrt{s}\log(1/ε))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{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.

quant-pharXiv:2601.16697•Quantum Science and Technology•Jan 26, 2026•6 citations

A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell

Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(κ\log(1/\varepsilon))$, where $κ$ is the condition number of $A$, and $\varepsilon$ 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 $\lVert\boldsymbol{x}\rVert$ 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(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(κ))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))$ 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/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56κ+1.05κ\ln(1/\varepsilon)+o(κ)$ for the complexity of our optimal QLSS.

arXiv:2406.12086•Jun 17, 2024•69 citations

Faster quantum linear system solver beyond the condition number

Alexander M. Dalzell, Jianqiang Li, Yuan Su

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\rangle$ of linear system $Ax=| b \rangle$ to accuracy $ε$ with complexity independent of the condition number $κ=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{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\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε$ 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.

quant-pharXiv:2607.07691•Jul 9, 2026•9 citations
In the quantum linear systems problem (QLSP), we are given query access to a ddd-sparse N×NN\times NN×N matrix AAA with condition number κκκ, and the ability to prepare a quantum state proportional to a vector b⃗\vec bb. The goal is to output an εεε-approximation to the quantum state proportional to the solution x⃗\vec xx of Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog⁡(1/ε))O(κd\log(1/ε))O(κdlog(1/ε)) and κd(κd/ε)o(1)κ\sqrt d(κd/ε)^{o(1)}κd​(κd/ε)o(1), while the best known lower bounds were Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κlog(1/ε)) and Ω(κd)Ω(κ\sqrt d)Ω(κd​). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog⁡(1/ε))Θ(κ\sqrt d\log(1/ε))Θ(κd​log(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×NN\times NN×N unitary can be implemented with bounded error using O(N)O(\sqrt N)O(N​) queries to its matrix entries.
The paper determines the quantum query complexity of preparing a normalized solution state for a sparse linear system Ax⃗=b⃗A\vec x=\vec bAx=b. In the standard sparse-matrix access model, with sparsity bound ddd, ∥A∥≤1\|A\|\leq1∥A∥≤1, ∥A−1∥≤κ\|A^{-1}\|\leq\kappa∥A−1∥≤κ, and trace-distance error ϵ\epsilonϵ, it proves matching bounds Θ(κdlog⁡(1/ϵ))\Theta(\kappa\sqrt d\log(1/\epsilon))Θ(κd​log(1/ϵ)). This combines the parameter dependences previously achieved separately by algorithms costing O(κdlog⁡(1/ϵ))O(\kappa d\log(1/\epsilon))O(κdlog(1/ϵ)) and κd(κd/ϵ)o(1)\kappa\sqrt d(\kappa d/\epsilon)^{o(1)}κd​(κd/ϵ)o(1).
The upper bound replaces the original system by an enlarged system whose matrix MMM has an exact block encoding using O(1)O(1)O(1) sparse-oracle queries and satisfies ∥M−1∥≤5κd\|M^{-1}\|\leq5\kappa\sqrt d∥M−1∥≤5κd​. Auxiliary variables split a matrix product into separate constraints, while entry-dependent normalization avoids preparing entire matrix rows. The desired solution is recovered from the enlarged solution with probability at least 1/31/31/3, allowing an existing block-encoded linear-systems algorithm to achieve the stated complexity.
The lower bound encodes a circuit computing the parity of Θ(κlog⁡(1/ϵ))\Theta(\kappa\log(1/\epsilon))Θ(κlog(1/ϵ)) independent search-derived bits into a geometrically weighted history state. A quantum XOR lemma supplies hardness even when extracting the answer yields only a small advantage over random guessing.
The construction also gives a constant-normalization block encoding of any Hermitian norm-bounded ddd-sparse matrix using O(dlog⁡(1/η))O(\sqrt d\log(1/\eta))O(d​log(1/η)) queries at operator-norm error η\etaη, and implements an entry-oracle unitary using O(Nlog⁡(1/ϵ))O(\sqrt N\log(1/\epsilon))O(N​log(1/ϵ)) queries, optimal for constant error. The complexity statements count matrix-oracle queries, not total gates or input-state preparation; the output is a quantum state, not a classical solution vector. Multiparameter lower bounds assume sufficiently large parameters.
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 sss of the input matrix, and the target precision ε\varepsilonε. The dependence on κκκ and ε\varepsilonε is already well understood through the lower bound Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity sss is included, however, the expected lower bound has long been conjectured to be Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(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)Ω(κ\sqrt{s})Ω(κs​) for constant error ε\varepsilonε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(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 UAU_AUA​ and the right-hand side through a state-preparation oracle UbU_bUb​. The optimal query complexities of these two oracles are known separately: O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) queries to UAU_AUA​ and O(κ/s)O(κ/s)O(κ/s) queries to UbU_bUb​, where s=α∥A−1b∥s=α\|A^{-1}b\|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 sss, we give a quantum linear-system algorithm that prepares the normalized solution to error ε\varepsilonε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UAU_AUA​ and O(κ/s)O\left(κ/{s}\right)O(κ/s) queries to UbU_bUb​. 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/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)) matrix queries and Ω(κ/s)Ω(κ/s)Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal O~(dκlog⁡(1/ϵ))\mathcal{\widetilde{O}}(d\kappa\log(1/\epsilon))O(dκlog(1/ϵ)) query complexity for a ddd-sparse matrix, where κ\kappaκ is the condition number, and ϵ\epsilonϵ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.
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 sss of the linear system, and the target error εεε. To date, the best known query-complexity lower bound is Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κ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 sss of the linear system, it has become folklore that it should read as Ω(κslog⁡(1/ε))Ω( κ\sqrt{s}\log(1/ε))Ω(κs​log(1/ε)). In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of Ω(κs)Ω(κ\sqrt{s})Ω(κs​) for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters κ,s,εκ,s,εκ,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=bA\boldsymbol{x}=\boldsymbol{b}Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩|\boldsymbol{x}\rangle∣x⟩ for which the amplitudes are proportional to the solution vector x\boldsymbol{x}x. Asymptotically optimal QLSSs have query complexity O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)), where κκκ is the condition number of AAA, and ε\varepsilonε 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∥\lVert\boldsymbol{x}\rVert∥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/ε)(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)(1+O(ε))κln(22​/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(log⁡log⁡(κ))O(\log\log(κ))O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κlog⁡log⁡(κ)log⁡log⁡log⁡(κ)+κlog⁡(1/ε))O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ)O(κ)O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))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(κ)56κ+1.05κ\ln(1/\varepsilon)+o(κ)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⟩|x\rangle∣x⟩ of linear system Ax=∣b⟩Ax=| b \rangleAx=∣b⟩ to accuracy εεε with complexity independent of the condition number κ=∥A−1∥κ=\lVert A^{-1}\rVertκ=∥A−1∥. We focus on the standard input model where AAA is accessed through a block encoding and ∣b⟩| b \rangle∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes AAA and ∣b⟩| b \rangle∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩| b \rangle∣b⟩ and O⁡(κeffpolylog⁡(κeffε))\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)O(κeff​polylog(εκeff​​)) queries to AAA. We prove a family of upper bounds on the effective condition number, including κeff≤∥(A†A)−t/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥(A†A)−t/2∣x⟩∥1/t​ for positive even integer ttt and κeff≤∥A−1†(A†A)−(t−1)/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t​ for positive odd ttt, 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⟩∥ε3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε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.