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

Large-scale quantum hybrid solution for linear systems of equations

Michael Romanovich Perelshtein, A. I. Pakhomchik, Alexey A. Melnikov, Novikov, A. A., Andreas Glatz, Gheorghe Sorin Paraoanu, V. M. Vinokur, Gordey B. Lesovik

Published Mar 28, 2020• 0 citations
arXivHTMLPDF

Abstract

State-of-the-art noisy intermediate-scale quantum devices (NISQ), although imperfect, enable computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to exploring specific simplified protocols, whereas the implementation of full-scale quantum algorithms aimed at solving concrete large scale problems arising in data analysis and numerical modelling remains a challenge. Here we introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup, utilizing quantum phase estimation, one of the exemplary core protocols for quantum computing. We introduce theoretically classes of linear systems that are suitable for current generation quantum machines and solve experimentally a $2^{17}$-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers. The considered large-scale algorithm shows superiority over conventional solutions, demonstrates advantages of quantum data processing via phase estimation and holds high promise for meeting practically relevant challenges.

DOI
10.48550/arxiv.2003.12770

Related papers

Advanced quantum supremacy using a hybrid algorithm for linear systems of equations

Michael Romanovich Perelshtein, A. I. Pakhomchik, Alexey A. Melnikov +5 more

A wealth of quantum algorithms developed during the past decades brought about the concept of quantum supremacy. The state-of-the-art noisy intermediate-scale quantum (NISQ) devices, although imperfect, enable certain computational tasks that are demonstrably beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to probing the quantum processor power, whereas implementation of specific full-scale quantum algorithms remains a challenge. Here we realize hybrid quantum algorithm for solving a linear system of equations with exponential speedup that utilizes quantum phase estimation, one of the exemplary core protocols for quantum computing. Our experiment carried out on superconducting IBMQ devices reveals the main shortcomings of the present quantum processors, which must be surpassed in order to boost quantum data processing via phase estimation. The developed algorithm demonstrates quantum supremacy and holds high promise to meet practically relevant challenges.

•Mar 28, 2020•4 citations

Solving Large‐Scale Linear Systems of Equations by a Quantum Hybrid Algorithm

Michael Romanovich Perelshtein, A. I. Pakhomchik, А. А. Мельников +5 more

Abstract Today's intermediate‐scale quantum computers, although imperfect, already perform computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, so far, quantum‐enabled large‐scale solutions have been realized only for limited set of problems. Here a hybrid algorithm based on phase estimation and classical optimization of the circuit width and depth is employed for solving a specific class of large linear systems of equations ubiquitous to many areas of science and engineering. A classification of linear systems based on the entanglement properties of the associated phase‐estimation unitary operation is introduced, enabling a highly efficient search for solutions that is facilitated by a straightforward matrix‐to‐circuit map. A 217‐dimensional problem is implemented on several IBM quantum computer superconducting quantum processors, a record‐breaking result for a linear system solved by a quantum computer. Demonstrated realisation sets a clear benchmark in the quest for the future quantum speedup in the linear systems of equations solution.

Annalen der Physik•May 17, 2022•15 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

Solving linear systems on quantum hardware with hybrid HHL++

Romina Yalovetzky, Pierre Minssen, Dylan Herman +1 more

The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid $$\hbox {HHL}^{++}$$ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.

arXiv:2110.15958•Scientific Reports•Sep 10, 2024•18 citations

A Variational Quantum Linear Solver Application to Discrete Finite-Element Methods

Corey Jason Trahan, Mark Loveland, Noah A. Davis +1 more

Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.

Entropy•Mar 28, 2023•33 citations

Quantum Speedup for Linear Systems: An Analysis of the HHL Algorithm Using IBM Qiskit

V Shwetha, Abinaya Selvarajan, A Aarthi +1 more

One of the most significant developments in quantum computing is the Harrow-Hassidim-Lloyd (HHL) method, which can solve linear equation systems at exponential speedup. Because linear systems are essential to many scientific fields, including physics, engineering, and machine learning, this approach has great potential to revolutionize computational paradigms. The HHL algorithm is thoroughly examined in this work, with particular attention paid to its theoretical framework, real-world application utilizing IBM's Qiskit platform, and the difficulties in simulating quantum algorithms on noisy intermediate-scale quantum (NISQ) devices. Using parameters like fidelity, time complexity, and scalability, the research further evaluates the HHL algorithm's performance in comparison to traditional methods. According to the findings, quantum simulations work well for small-scale matrices like 2x2 and 4x4, but expanding the approach to bigger systems is still difficult because of hardware and software constraints. Finally, the research emphasizes the key directions for advancing quantum hardware and algorithms to overcome current scalability challenges, enabling broader applicability of the HHL algorithm in solving complex linear systems.

Journal of Electronics and Informatics•Jan 9, 2025•0 citations
State-of-the-art noisy intermediate-scale quantum devices (NISQ), although imperfect, enable computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to exploring specific simplified protocols, whereas the implementation of full-scale quantum algorithms aimed at solving concrete large scale problems arising in data analysis and numerical modelling remains a challenge. Here we introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup, utilizing quantum phase estimation, one of the exemplary core protocols for quantum computing. We introduce theoretically classes of linear systems that are suitable for current generation quantum machines and solve experimentally a 2172^{17}217-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers. The considered large-scale algorithm shows superiority over conventional solutions, demonstrates advantages of quantum data processing via phase estimation and holds high promise for meeting practically relevant challenges.
A wealth of quantum algorithms developed during the past decades brought about the concept of quantum supremacy. The state-of-the-art noisy intermediate-scale quantum (NISQ) devices, although imperfect, enable certain computational tasks that are demonstrably beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to probing the quantum processor power, whereas implementation of specific full-scale quantum algorithms remains a challenge. Here we realize hybrid quantum algorithm for solving a linear system of equations with exponential speedup that utilizes quantum phase estimation, one of the exemplary core protocols for quantum computing. Our experiment carried out on superconducting IBMQ devices reveals the main shortcomings of the present quantum processors, which must be surpassed in order to boost quantum data processing via phase estimation. The developed algorithm demonstrates quantum supremacy and holds high promise to meet practically relevant challenges.
Abstract Today's intermediate‐scale quantum computers, although imperfect, already perform computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, so far, quantum‐enabled large‐scale solutions have been realized only for limited set of problems. Here a hybrid algorithm based on phase estimation and classical optimization of the circuit width and depth is employed for solving a specific class of large linear systems of equations ubiquitous to many areas of science and engineering. A classification of linear systems based on the entanglement properties of the associated phase‐estimation unitary operation is introduced, enabling a highly efficient search for solutions that is facilitated by a straightforward matrix‐to‐circuit map. A 217‐dimensional problem is implemented on several IBM quantum computer superconducting quantum processors, a record‐breaking result for a linear system solved by a quantum computer. Demonstrated realisation sets a clear benchmark in the quest for the future quantum speedup in the linear systems of equations solution.
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.
The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid HHL++\hbox {HHL}^{++}HHL++ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.
Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.
One of the most significant developments in quantum computing is the Harrow-Hassidim-Lloyd (HHL) method, which can solve linear equation systems at exponential speedup. Because linear systems are essential to many scientific fields, including physics, engineering, and machine learning, this approach has great potential to revolutionize computational paradigms. The HHL algorithm is thoroughly examined in this work, with particular attention paid to its theoretical framework, real-world application utilizing IBM's Qiskit platform, and the difficulties in simulating quantum algorithms on noisy intermediate-scale quantum (NISQ) devices. Using parameters like fidelity, time complexity, and scalability, the research further evaluates the HHL algorithm's performance in comparison to traditional methods. According to the findings, quantum simulations work well for small-scale matrices like 2x2 and 4x4, but expanding the approach to bigger systems is still difficult because of hardware and software constraints. Finally, the research emphasizes the key directions for advancing quantum hardware and algorithms to overcome current scalability challenges, enabling broader applicability of the HHL algorithm in solving complex linear systems.