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

Bulletin of the American Physical Society

Quantum linear systems algorithm with exponentially improved dependence on precision

Rolando D. Somma, Andrew M. Childs, Robin Kothari

Published Mar 15, 2016• 15 citations
OpenAlex

Related papers

Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision

Dominic William Berry, Andrew M. Childs, Aaron Ostrander +1 more

arXiv:1701.03684•Communications in Mathematical Physics•Oct 7, 2017•219 citations

Quantum linear systems algorithm with exponentially improved dependence on precision

Andrew M. Childs, Robin Kothari, Rolando D. Somma

Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\mathrm{poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.

•Nov 7, 2015•30 citations

Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision

Andrew M. Childs, Robin Kothari, Rolando D. Somma

Harrow, Hassidim, and Lloyd [ Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x} = \vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time ${poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.

arXiv:1511.02306•SIAM Journal on Computing•Jan 1, 2017•645 citations

Benchmarking Refined Quantum Linear Systems Algorithms

Adrian Harkness, Kate Saltovets, Mohammadhossein Mohammadisiahroudi +1 more

Communications in computer and information science•Jan 1, 2026•0 citations

Benchmarking Highly Precise Quantum Linear Systems Algorithms

Adrian Harkness, Kate Saltovets, Mohammadhossein Mohammadisiahroudi +1 more

Systems of linear equations are ubiquitous across science, engineering, machine learning, and even finance. While classical methods can be prohibitively slow for large-scale problems, quantum linear systems algorithms offer the potential for exponential speedup in certain parameter regimes. However, a significant gap persists between this theoretical promise and practical implementation, as the advantages are often obscured by the substantial quantum resources and high sensitivity to noise inherent in current quantum hardware. One way to bridge this gap is through the use of Iterative Refinement, a classical post-processing scheme that can exponentially improve the accuracy to which a linear system of equations can be solved using low-precision arithmetic. In the context of quantum linear systems algorithms, such as the HHL algorithm proposed by Harrow, Hassidim, and Loyd, Iterative Refinement can greatly reduce the quantum resources required to calculate an accurate solution in terms of tomography cost, circuit volume, and fault-tolerant overhead. Here, we compute and benchmark highly precise solutions to linear systems of equations of up to eight variables by running HHL with Iterative Refinement on NISQ quantum computers. We also present our open-source implementation, emphasizing that our circuit is not tailored to specific problem instances, as most available implementations are.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Linear System Algorithms: Direct Methods

Osama M. Raisuddin, Suvranu De

Springer eBooks•Nov 14, 2025•0 citations
Harrow, Hassidim, and Lloyd showed that for a suitably specified N×NN \times NN×N matrix AAA and NNN-dimensional vector b⃗\vec{b}b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b. If AAA is sparse and well-conditioned, their algorithm runs in time poly(log⁡N,1/ϵ)\mathrm{poly}(\log N, 1/\epsilon)poly(logN,1/ϵ), where ϵ\epsilonϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log⁡(1/ϵ)\log(1/\epsilon)log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ\epsilonϵ is prohibitive.
Harrow, Hassidim, and Lloyd [ Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified N×NN \times NN×N matrix AAA and an NNN-dimensional vector b⃗\vec{b}b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax⃗=b⃗A\vec{x} = \vec{b}Ax=b. If AAA is sparse and well-conditioned, their algorithm runs in time poly(log⁡N,1/ϵ){poly}(\log N, 1/\epsilon)poly(logN,1/ϵ), where ϵ\epsilonϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log⁡(1/ϵ)\log(1/\epsilon)log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ\epsilonϵ is prohibitive.
Systems of linear equations are ubiquitous across science, engineering, machine learning, and even finance. While classical methods can be prohibitively slow for large-scale problems, quantum linear systems algorithms offer the potential for exponential speedup in certain parameter regimes. However, a significant gap persists between this theoretical promise and practical implementation, as the advantages are often obscured by the substantial quantum resources and high sensitivity to noise inherent in current quantum hardware. One way to bridge this gap is through the use of Iterative Refinement, a classical post-processing scheme that can exponentially improve the accuracy to which a linear system of equations can be solved using low-precision arithmetic. In the context of quantum linear systems algorithms, such as the HHL algorithm proposed by Harrow, Hassidim, and Loyd, Iterative Refinement can greatly reduce the quantum resources required to calculate an accurate solution in terms of tomography cost, circuit volume, and fault-tolerant overhead. Here, we compute and benchmark highly precise solutions to linear systems of equations of up to eight variables by running HHL with Iterative Refinement on NISQ quantum computers. We also present our open-source implementation, emphasizing that our circuit is not tailored to specific problem instances, as most available implementations are.