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

Annalen der Physik

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

Michael Romanovich Perelshtein, A. I. Pakhomchik, А. А. Мельников, A. A. Novikov, Andreas Glatz, Gheorghe Sorin Paraoanu, V. M. Vinokur, Gordey B. Lesovik

Published May 17, 2022• 15 citations
Publisher

Abstract

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.

DOI
10.1002/andp.202200082

Related papers

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

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 Systems of Linear Equations with a Superconducting Quantum Processor

Yarui Zheng, Chao Song, Ming-Cheng Chen +15 more

Superconducting quantum circuits are a promising candidate for building scalable quantum computers. Here, we use a four-qubit superconducting quantum processor to solve a two-dimensional system of linear equations based on a quantum algorithm proposed by Harrow, Hassidim, and Lloyd [Phys. Rev. Lett. 103, 150502 (2009)PRLTAO0031-900710.1103/PhysRevLett.103.150502], which promises an exponential speedup over classical algorithms under certain circumstances. We benchmark the solver with quantum inputs and outputs, and characterize it by nontrace-preserving quantum process tomography, which yields a process fidelity of 0.837±0.006. Our results highlight the potential of superconducting quantum circuits for applications in solving large-scale linear systems, a ubiquitous task in science and engineering.

arXiv:1703.06613•Physical Review Letters•May 26, 2017•95 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

Experimental Quantum Computing to Solve Systems of Linear Equations

Xiang Cai, Christian Weedbrook, Zu-En Su +7 more

Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.

arXiv:1302.4310•Physical Review Letters•Jun 6, 2013•173 citations

Quantum–Classical Hybrid Architecture for Solving the Muskat–Leverett Model

Beimbet Daribayev, Aksultan Mukhanbet, Erlan Makhmut +2 more

ABSTRACT Hybrid quantum–classical architectures demonstrate significant potential for efficiently solving complex physical models. This study focuses on developing and implementing a hybrid quantum–classical algorithm to solve the Muskat–Leverett model by reformulating it as a system of linear equations. By expressing the Muskat–Leverett model in matrix form , we enable the application of quantum algorithms. We leverage classical computational platforms (CPU and GPU) alongside quantum computing to efficiently solve the model, achieving competitive accuracy and demonstrating potential for scalability compared to traditional methods. The Harrow–Hassidim–Lloyd algorithm and the variational quantum linear solver were utilised to design quantum circuits and variational ansatz. The study evaluates quantum solutions with classical optimisation, variational methods, fully classical solutions on graphical processors and purely quantum solutions. Experimental results show that the hybrid architecture, utilising cuQuantum and CUDA‐Q, achieves up to 6.42× faster execution compared to CPU implementations and provides a comparable speedup to GPU‐based solvers. When applied for large‐scale problems, the hybrid approach is also ∼10× faster than standard quantum simulators. Key factors, such as qubits, optimisers and cost functions, were analysed to determine optimal parameters. These results highlight the advantages of hybrid architecture in accelerating and optimising numerical solutions for complex physical models.

IET Quantum Communication•Jan 1, 2025•1 citation
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.
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.
Superconducting quantum circuits are a promising candidate for building scalable quantum computers. Here, we use a four-qubit superconducting quantum processor to solve a two-dimensional system of linear equations based on a quantum algorithm proposed by Harrow, Hassidim, and Lloyd [Phys. Rev. Lett. 103, 150502 (2009)PRLTAO0031-900710.1103/PhysRevLett.103.150502], which promises an exponential speedup over classical algorithms under certain circumstances. We benchmark the solver with quantum inputs and outputs, and characterize it by nontrace-preserving quantum process tomography, which yields a process fidelity of 0.837±0.006. Our results highlight the potential of superconducting quantum circuits for applications in solving large-scale linear systems, a ubiquitous task in science and engineering.
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.
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.
ABSTRACT Hybrid quantum–classical architectures demonstrate significant potential for efficiently solving complex physical models. This study focuses on developing and implementing a hybrid quantum–classical algorithm to solve the Muskat–Leverett model by reformulating it as a system of linear equations. By expressing the Muskat–Leverett model in matrix form , we enable the application of quantum algorithms. We leverage classical computational platforms (CPU and GPU) alongside quantum computing to efficiently solve the model, achieving competitive accuracy and demonstrating potential for scalability compared to traditional methods. The Harrow–Hassidim–Lloyd algorithm and the variational quantum linear solver were utilised to design quantum circuits and variational ansatz. The study evaluates quantum solutions with classical optimisation, variational methods, fully classical solutions on graphical processors and purely quantum solutions. Experimental results show that the hybrid architecture, utilising cuQuantum and CUDA‐Q, achieves up to 6.42× faster execution compared to CPU implementations and provides a comparable speedup to GPU‐based solvers. When applied for large‐scale problems, the hybrid approach is also ∼10× faster than standard quantum simulators. Key factors, such as qubits, optimisers and cost functions, were analysed to determine optimal parameters. These results highlight the advantages of hybrid architecture in accelerating and optimising numerical solutions for complex physical models.