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:2304.05960

Quantum Multi-Resolution Measurement with application to Quantum Linear Solver

Yoshiyuki Saito, Xinwei Lee, Cai, Dongsheng, Nobuyoshi Asai

Published Apr 12, 2023• 1 citation
arXivHTMLPDF

Abstract

Quantum computation consists of a quantum state corresponding to a solution, and measurements with some observables. To obtain a solution with an accuracy $ε$, measurements $O(n/ε^2)$ are required, where $n$ is the size of a problem. The cost of these measurements requires a large computing time for an accurate solution. In this paper, we propose a quantum multi-resolution measurement (QMRM), which is a hybrid quantum-classical algorithm that gives a solution with an accuracy $ε$ in $O(n\log(1/ε))$ measurements using a pair of functions. The QMRM computational cost with an accuracy $ε$ is smaller than $O(n/ε^2)$. We also propose an algorithm entitled QMRM-QLS (quantum linear solver) for solving a linear system of equations using the Harrow-Hassidim-Lloyd (HHL) algorithm as one of the examples. We perform some numerical experiments that QMRM gives solutions to with an accuracy $ε$ in $O(n\log(1/ε))$ measurements.

DOI
10.48550/arxiv.2304.05960

Related papers

Numerical Methods for Solving High-Order Mathematical Problems using Quantum Linear System Algorithm on IBM QISKit Platform

Simran Jakhodia, Babita Jajodia

Researchers are currently working on computational solutions based on quantum systems to accelerate the speed of complex mathematical models. This work presented how to formulate complex computational problems as a quantum system of linear equations and find solutions using Quantum Linear System Algorithm (QLSA), also called Quantum Harrow-Hassidim-Lloyd (HHL) algorithm. This paper showed experimental evaluation of multiple problem statements (curve-fitting functions, interpolating polynomials) as a quantum system of linear equations that involve computation of Vandermonde matrices as co-efficient matrices on IBM Quantum Information Software Kit for Quantum Computation (QISKit) platform. Along with a few examples demonstrating its evaluation on diagonal, Hermitian, and Non-Hermitian matrices as co-efficient matrices. The fidelity is used as a measure of performance for comparing the accuracy of quantum results with respect to existing classical solutions on IBM QISKit and drawing conclusions from the experimental results. Experimental evaluation shows that the fidelity depends on the sparsity of the input matrices and therefore the results vary depending on those matrices.

International Conference on Innovative Trends in Information Technology (ICITIIT)•Feb 12, 2022•1 citation

Quantum linear system solvers: A survey of algorithms and applications

Mauro E. S. Morales, Lirandë Pira, Philipp Schleich +7 more

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.

arXiv:2411.02522•Reviews of Modern Physics•Jan 8, 2026•4 citations

An Iterative Improvement Method for HHL algorithm for Solving Linear System of Equations

Yoshiyuki Saito, Xinwei Lee, Dongsheng Cai +1 more

We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However, the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naïve iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.

arXiv:2108.07744•Aug 17, 2021•3 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

Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience

Yonghae Lee, Jaewoo Joo, Soojoon Lee

We propose a hybrid quantum algorithm based on the Harrow-Hassidim-Lloyd (HHL) algorithm for solving a system of linear equations. In this paper, we show that our hybrid algorithm can reduce a circuit depth from the original HHL algorithm by means of a classical information feed-forward after the quantum phase estimation algorithm, and the results of the hybrid algorithm are identical to those of the HHL algorithm. In addition, it is experimentally examined with four qubits in the IBM Quantum Experience setups, and the experimental results of our algorithm show higher accurate performance on specific systems of linear equations than that of the HHL algorithm.

arXiv:1807.10651•Scientific Reports•Mar 18, 2019•77 citations

Solving Linear Systems of Equations with the Quantum HHL Algorithm: A Tutorial on the Physical and Mathematical Foundations for Undergraduate Students

Lucas Queiroz Galvão, de Souza, Anna Beatriz M., A. Santos +2 more

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(\log N)$, in contrast to classical approaches, which in the general case exhibit a complexity of $O(N^3)$, 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.

arXiv:2509.16640•Sep 20, 2025•0 citations
Quantum computation consists of a quantum state corresponding to a solution, and measurements with some observables. To obtain a solution with an accuracy εεε, measurements O(n/ε2)O(n/ε^2)O(n/ε2) are required, where nnn is the size of a problem. The cost of these measurements requires a large computing time for an accurate solution. In this paper, we propose a quantum multi-resolution measurement (QMRM), which is a hybrid quantum-classical algorithm that gives a solution with an accuracy εεε in O(nlog⁡(1/ε))O(n\log(1/ε))O(nlog(1/ε)) measurements using a pair of functions. The QMRM computational cost with an accuracy εεε is smaller than O(n/ε2)O(n/ε^2)O(n/ε2). We also propose an algorithm entitled QMRM-QLS (quantum linear solver) for solving a linear system of equations using the Harrow-Hassidim-Lloyd (HHL) algorithm as one of the examples. We perform some numerical experiments that QMRM gives solutions to with an accuracy εεε in O(nlog⁡(1/ε))O(n\log(1/ε))O(nlog(1/ε)) measurements.
Researchers are currently working on computational solutions based on quantum systems to accelerate the speed of complex mathematical models. This work presented how to formulate complex computational problems as a quantum system of linear equations and find solutions using Quantum Linear System Algorithm (QLSA), also called Quantum Harrow-Hassidim-Lloyd (HHL) algorithm. This paper showed experimental evaluation of multiple problem statements (curve-fitting functions, interpolating polynomials) as a quantum system of linear equations that involve computation of Vandermonde matrices as co-efficient matrices on IBM Quantum Information Software Kit for Quantum Computation (QISKit) platform. Along with a few examples demonstrating its evaluation on diagonal, Hermitian, and Non-Hermitian matrices as co-efficient matrices. The fidelity is used as a measure of performance for comparing the accuracy of quantum results with respect to existing classical solutions on IBM QISKit and drawing conclusions from the experimental results. Experimental evaluation shows that the fidelity depends on the sparsity of the input matrices and therefore the results vary depending on those matrices.
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.
We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However, the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naïve iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.
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.
We propose a hybrid quantum algorithm based on the Harrow-Hassidim-Lloyd (HHL) algorithm for solving a system of linear equations. In this paper, we show that our hybrid algorithm can reduce a circuit depth from the original HHL algorithm by means of a classical information feed-forward after the quantum phase estimation algorithm, and the results of the hybrid algorithm are identical to those of the HHL algorithm. In addition, it is experimentally examined with four qubits in the IBM Quantum Experience setups, and the experimental results of our algorithm show higher accurate performance on specific systems of linear equations than that of the HHL algorithm.
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(log⁡N)poly(\log N)poly(logN), in contrast to classical approaches, which in the general case exhibit a complexity of O(N3)O(N^3)O(N3), although they can achieve O(N)O(N)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.