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

New Journal of Physics

Near-term quantum algorithms for linear systems of equations with regression loss functions

Hsin-Yuan Huang, Kishor Bharti, Patrick Rebentrost

Published Nov 1, 2021• 68 citations
Publisher

Abstract

Abstract Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations, with a focus on the two-norm and Tikhonov regression settings. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called ansatz tree. The CQS approach and the ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as 2 300 × 2 300 by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. Our methods may provide benefits for solving linear systems within the reach of near-term quantum devices.

DOI
10.1088/1367-2630/ac325f

Related papers

Near-term quantum algorithms for linear systems of equations

Hsin-Yuan Huang, Kishor Bharti, Patrick Rebentrost

Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax = b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300} \times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.

arXiv:1909.07344•Sep 16, 2019•60 citations

Near term algorithms for linear systems of equations

Aidan Pellow-Jarman, Ilya Sinayskiy, Anban W. Pillay +1 more

Abstract Finding solutions to systems of linear equations is a common problem in many areas of science and engineering, with much potential for a speed up on quantum devices. While the Harrow–Hassidim–Lloyd (HHL) quantum algorithm yields up to an exponential speed up over classical algorithms in some cases, it requires a fault-tolerant quantum computer, which is unlikely to be available in the near-term. Thus, attention has turned to the investigation of quantum algorithms for noisy intermediate-scale quantum (NISQ) devices where several near-term approaches to solving systems of linear equations have been proposed. This paper focuses on the Variational Quantum Linear Solvers (VQLS), and other closely related methods and adaptions. Several contributions are made in this paper, which include: the first application of the Evolutionary Ansatz to the VQLS (EAVQLS), the first implementation of the Logical Ansatz VQLS (LAVQLS), based on the Classical Combination of Quantum States (CQS) method, a proof of principle demonstration of the CQS method on real quantum hardware and a method for the implementation of the Adiabatic Ansatz on the VQLS (AAVQLS). These approaches are implemented and contrasted. The CQS method is run with moderate success on a real quantum device. The EAVQLS and AAVQLS show promise as possible improvements to the standard VQLS algorithm once refined.

arXiv:2108.11362•Quantum Information Processing•Jun 24, 2023•7 citations

Optimization of Quantum Algorithm Protocols without Barren Plateaus

Lukas Broers, Ludwig Mathey

Quantum machine learning has emerged as a promising method to improve near-term quantum computation devices. However, algorithmic classes such as variational quantum algorithms have been shown to suffer from barren plateaus due to vanishing gradients in their parameter spaces. We present an approach to quantum algorithm optimization that is based on trainable Fourier coefficients of Hamiltonian system parameters. Our ansatz applies to the extension of discrete quantum variational algorithms to analogue quantum optimal control schemes and is non-local in time. We demonstrate the viability of our ansatz on several objective functions using quantum natural gradient descent. In comparison to the temporally local discretization ans\atze in quantum optimal control and parametrized circuits, our ansatz exhibits faster and more consistent convergence with a distinct lack of barren plateaus. We propose our ansatz as a viable parametrization candidate for near-term quantum machine learning.

•Nov 15, 2021•1 citation

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Roetteler, Martin +1 more

Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.

arXiv:2404.16135•Apr 24, 2024•1 citation

Mathematical Foundations of Quantum Linear Regression: A Proof of Concept via Variational Hamiltonian Formulation

Methanon Kaeokrachang

We present a rigorous mathematical proof of concept demonstrating the theoretical feasibility of quantum linear regression through variational Hamiltonian formulation. Our framework systematically transforms classical linear regression into a quantum optimization problem by encoding regression weights as expectation values of Pauli-Z operators and reformulating the loss function as a quantum Hamiltonian. We provide explicit mathematical constructions, matrix representations, and convergence analysis to establish the theoretical foundation for quantum machine learning applications. Unlike previous quantum linear regression approaches that focus on exponential speedups through quantum linear systems solvers, our variational approach is designed for near-term quantum devices and naturally incorporates regularization through quantum parameter constraints. The mathematical framework demonstrates computational equivalence between classical and quantum approaches while revealing inherent advantages in constrained optimization scenarios. This work provides the theoretical groundwork for future empirical applications to financial time series prediction, including potential implementation on Thai SET Index forecasting using data from Yahoo Finance and quantum computing platforms. Our key contributions include: (1) complete mathematical mapping from classical to quantum regression formulation, (2) explicit Hamiltonian constructions with matrix representations, (3) theoretical convergence analysis for quantum gradient descent, and (4) identification of quantumspecific regularization properties that distinguish this approach from classical methods.

•Jun 27, 2025•0 citations

Variational Quantum Linear Solver

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

Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare | x ⟩ such that A | x ⟩ ∝ | b ⟩ . We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C ⩾ ϵ 2 / κ 2 , where C is the VQLS cost function and κ is the condition number of A . We present efficient quantum circuits to estimate C , while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of 1024 × 1024 . Finally, we numerically solve non-trivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ , κ , and the system size N .

arXiv:1909.05820•Quantum•Nov 22, 2023•261 citations
Abstract Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations, with a focus on the two-norm and Tikhonov regression settings. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called ansatz tree. The CQS approach and the ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as 2 300 × 2 300 by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. Our methods may provide benefits for solving linear systems within the reach of near-term quantum devices.
Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form Ax=bAx = bAx=b. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as 2300×23002^{300} \times 2^{300}2300×2300 by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about 100100100-300300300 qubits.
Abstract Finding solutions to systems of linear equations is a common problem in many areas of science and engineering, with much potential for a speed up on quantum devices. While the Harrow–Hassidim–Lloyd (HHL) quantum algorithm yields up to an exponential speed up over classical algorithms in some cases, it requires a fault-tolerant quantum computer, which is unlikely to be available in the near-term. Thus, attention has turned to the investigation of quantum algorithms for noisy intermediate-scale quantum (NISQ) devices where several near-term approaches to solving systems of linear equations have been proposed. This paper focuses on the Variational Quantum Linear Solvers (VQLS), and other closely related methods and adaptions. Several contributions are made in this paper, which include: the first application of the Evolutionary Ansatz to the VQLS (EAVQLS), the first implementation of the Logical Ansatz VQLS (LAVQLS), based on the Classical Combination of Quantum States (CQS) method, a proof of principle demonstration of the CQS method on real quantum hardware and a method for the implementation of the Adiabatic Ansatz on the VQLS (AAVQLS). These approaches are implemented and contrasted. The CQS method is run with moderate success on a real quantum device. The EAVQLS and AAVQLS show promise as possible improvements to the standard VQLS algorithm once refined.
Quantum machine learning has emerged as a promising method to improve near-term quantum computation devices. However, algorithmic classes such as variational quantum algorithms have been shown to suffer from barren plateaus due to vanishing gradients in their parameter spaces. We present an approach to quantum algorithm optimization that is based on trainable Fourier coefficients of Hamiltonian system parameters. Our ansatz applies to the extension of discrete quantum variational algorithms to analogue quantum optimal control schemes and is non-local in time. We demonstrate the viability of our ansatz on several objective functions using quantum natural gradient descent. In comparison to the temporally local discretization ans\atze in quantum optimal control and parametrized circuits, our ansatz exhibits faster and more consistent convergence with a distinct lack of barren plateaus. We propose our ansatz as a viable parametrization candidate for near-term quantum machine learning.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
We present a rigorous mathematical proof of concept demonstrating the theoretical feasibility of quantum linear regression through variational Hamiltonian formulation. Our framework systematically transforms classical linear regression into a quantum optimization problem by encoding regression weights as expectation values of Pauli-Z operators and reformulating the loss function as a quantum Hamiltonian. We provide explicit mathematical constructions, matrix representations, and convergence analysis to establish the theoretical foundation for quantum machine learning applications. Unlike previous quantum linear regression approaches that focus on exponential speedups through quantum linear systems solvers, our variational approach is designed for near-term quantum devices and naturally incorporates regularization through quantum parameter constraints. The mathematical framework demonstrates computational equivalence between classical and quantum approaches while revealing inherent advantages in constrained optimization scenarios. This work provides the theoretical groundwork for future empirical applications to financial time series prediction, including potential implementation on Thai SET Index forecasting using data from Yahoo Finance and quantum computing platforms. Our key contributions include: (1) complete mathematical mapping from classical to quantum regression formulation, (2) explicit Hamiltonian constructions with matrix representations, (3) theoretical convergence analysis for quantum gradient descent, and (4) identification of quantumspecific regularization properties that distinguish this approach from classical methods.
Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare | x ⟩ such that A | x ⟩ ∝ | b ⟩ . We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C ⩾ ϵ 2 / κ 2 , where C is the VQLS cost function and κ is the condition number of A . We present efficient quantum circuits to estimate C , while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of 1024 × 1024 . Finally, we numerically solve non-trivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ , κ , and the system size N .