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

Hybrid quantum linear solver using Noisy Intermediate-Scale Quantum machines

Chih-Chieh Chen, Shiue-Yuan Shiau, Ming‐Feng Wu, Yuh‐Renn Wu

Published Mar 26, 2019• 0 citations
OpenAlex

Abstract

We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility using Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in $\mathcal{O}(N\log(N))$ time on a quantum circuit made of $\mathcal{O}(\log(N))$ qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready to implement for applications.

Related papers

Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines

Chih-Chieh Chen, Shiue-Yuan Shiau, Ming-Feng Wu +1 more

We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of [Formula: see text](log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.

arXiv:1903.10949•Scientific Reports•Nov 7, 2019•43 citations

Large-scale quantum hybrid solution for linear systems of equations

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

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.

arXiv:2003.12770•Mar 28, 2020•0 citations

Variational Quantum Linear Solver: A Hybrid Algorithm for Linear Systems

Carlos Bravo-Prieto, Ryan LaRose, Marco Cerezo +3 more

Solving linear systems of equations is central to many engineering and scientific fields. Several quantum algorithms have been proposed for linear systems, where the goal is to prepare $|x\rangle$ such that $A|x\rangle \propto |b\rangle$. While these algorithms are promising, the time horizon for their implementation is long due to the required quantum circuit depth. In this work, we propose a variational hybrid quantum-classical algorithm for solving linear systems, with the aim of reducing the circuit depth and doing much of the computation classically. We propose a cost function based on the overlap between $|b\rangle$ and $A|x\rangle$, and we derive an operational meaning for this cost in terms of the solution precision $\epsilon$. We also introduce a quantum circuit to estimate this cost, while showing that this cost cannot be efficiently estimated classically. Using Rigetti's quantum computer, we successfully implement our algorithm up to a problem size of $32 \times 32$. Furthermore, we numerically find that the complexity of our algorithm scales efficiently in both $1/\epsilon$ and $\kappa$, with $\kappa$ the condition number of $A$. Our algorithm provides a heuristic for quantum linear systems that could make this application more near term.

Bulletin of the American Physical Society•Sep 12, 2019•35 citations

On Quantum Solvers for Linear Algebraic Systems

Papagiannis Nikos, Vavalis Manolis

Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.

Quantum Information and Computation•Dec 1, 2025•0 citations

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

David Jennings, Matteo Lostaglio, Sam Pallister +2 more

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.

arXiv:2305.11352•PRX Quantum•Oct 7, 2025•6 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
We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility using Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in O(Nlog⁡(N))\mathcal{O}(N\log(N))O(Nlog(N)) time on a quantum circuit made of O(log⁡(N))\mathcal{O}(\log(N))O(log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready to implement for applications.
We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of [Formula: see text](log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.
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.
Solving linear systems of equations is central to many engineering and scientific fields. Several quantum algorithms have been proposed for linear systems, where the goal is to prepare ∣x⟩|x\rangle∣x⟩ such that A∣x⟩∝∣b⟩A|x\rangle \propto |b\rangleA∣x⟩∝∣b⟩. While these algorithms are promising, the time horizon for their implementation is long due to the required quantum circuit depth. In this work, we propose a variational hybrid quantum-classical algorithm for solving linear systems, with the aim of reducing the circuit depth and doing much of the computation classically. We propose a cost function based on the overlap between ∣b⟩|b\rangle∣b⟩ and A∣x⟩A|x\rangleA∣x⟩, and we derive an operational meaning for this cost in terms of the solution precision ϵ\epsilonϵ. We also introduce a quantum circuit to estimate this cost, while showing that this cost cannot be efficiently estimated classically. Using Rigetti's quantum computer, we successfully implement our algorithm up to a problem size of 32×3232 \times 3232×32. Furthermore, we numerically find that the complexity of our algorithm scales efficiently in both 1/ϵ1/\epsilon1/ϵ and κ\kappaκ, with κ\kappaκ the condition number of AAA. Our algorithm provides a heuristic for quantum linear systems that could make this application more near term.
Abstract Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.
Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.
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.