Variational Quantum Linear Solver (VQLS)

Overview

The variational quantum linear solver, or VQLS, is a hybrid algorithm for solving linear systems of equations on a noisy quantum computer. Instead of the deep, fault-tolerant circuits of the HHL algorithm, VQLS uses a short parameterized circuit that is trained to prepare a state proportional to the solution, with a classical optimizer adjusting the parameters to minimize a cost that measures how well the candidate satisfies the equations.

As with other variational methods, there is no proven speedup. The appeal is that the circuits are shallow enough to run on today's devices, which makes VQLS a testbed for hybrid linear algebra and for studying the trainability of variational circuits.

The problem it solves

Solve the linear system Ax=b on NISQ hardware without the exponentially deep circuits required by HHL.

History and background

HHL, published in 2009, showed that quantum computers could in principle solve sparse linear systems exponentially faster, but its circuits are far beyond current hardware. In 2019, three groups proposed variational alternatives within months: Bravo-Prieto and coauthors at Los Alamos, Xu and coauthors, and Huang, Bharti, and Rebentrost, who each used a parameterized circuit and a cost function in place of phase estimation.

The Bravo-Prieto paper was published in Quantum in 2023. It introduced a local cost function that avoids barren plateaus in some cases, and showed numerical examples with matrices of enormous size but special structure, such as those built from Ising-model Hamiltonians, as well as experiments on small quantum hardware. Later work analyzed the trainability of VQLS and extended it to preconditioning, differential equations, and fluid dynamics problems, though results remain at toy scale.

How it works

Prepares a variational ansatz state and minimizes a cost function measuring how well Ax matches b. Uses a classical optimizer to tune circuit parameters, similar to VQE's approach for chemistry.

We want x such that A x equals b, where A is a large matrix and b a vector. On a quantum computer the vector b is a state and A is an operator, written as a sum of simple pieces such as Pauli strings. A parameterized circuit V of alpha prepares a trial state x of alpha.

If x of alpha is a good solution, then applying A gives a state proportional to b. VQLS quantifies this by the overlap between A times x of alpha and b. The cost is zero exactly when the two are parallel, and larger otherwise. The global cost looks at the overlap of the whole state and can be hard to train for many qubits. The local cost compares the states qubit by qubit, with a similar minimum but gradients that do not vanish as quickly.

The quantum computer's job is to estimate the cost and, with it, the gradient, using Hadamard tests between circuits that implement V, A, and the preparation of b. The classical computer's job is to update alpha. As in VQE, the loop repeats until the cost is small, at which point the circuit prepares the desired solution state.

Step by step

1. Write the matrix as a linear combination of unitaries, such as a sum of Pauli strings with coefficients, and write a circuit that prepares the state b.
2. Choose a parameterized ansatz circuit V of alpha that will prepare the candidate solution state.
3. Define a cost function, global or local, that is zero when A times the candidate is proportional to b.
4. Estimate the cost by running Hadamard tests that compute the needed overlaps between terms, using measurements on a quantum computer.
5. Feed the cost to a classical optimizer, which updates the parameters alpha, using gradients from parameter-shift rules if available.
6. Iterate until the cost falls below a tolerance, then use the final circuit to prepare the solution state and measure observables of interest.

A worked example

Take a small matrix A equal to the identity plus a small multiple of the Pauli X operator on each of three qubits, and b equal to a simple product state. The solution x is close to b with corrections that are easy to find. A hardware-efficient ansatz with a few layers and about a dozen parameters can learn x of alpha with a cost near zero after tens of iterations.

For a larger structured matrix, such as one built from an Ising-type Hamiltonian on 50 qubits, the number of terms in A grows only linearly, and the cost evaluation scales polynomially in the number of terms. Researchers have simulated such cases at sizes far beyond what is possible to solve classically in naive form, but those examples rely on special structure that also helps classical solvers.

Complexity and resources

What hardware it needs

• A near-term device capable of running Hadamard tests and the ansatz circuit with moderate fidelity.
• Many shots per cost evaluation and a classical optimizer.
• For useful problems, matrices with a sparse Pauli decomposition and a state b that is easy to prepare.

Applications

• Linear systems arising in solving differential equations, including simple fluid dynamics and electromagnetics problems.
• Regression and data fitting, in toy examples of quantum machine learning.
• A benchmark for variational methods and trainability studies.
• Preconditioning and subroutines inside larger hybrid algorithms.

Limitations and caveats

• No proven speedup over classical solvers, which are extremely efficient for most linear systems.
• Barren plateaus and local minima can make training hard, especially with the global cost.
• The number of terms in the Pauli decomposition of A can be large for general matrices.
• The output is a quantum state, so extracting the full solution vector is exponentially costly.

Common misconceptions

• VQLS is not a drop-in replacement for HHL with the same guarantees. It is a heuristic.
• A low cost does not always mean the solution state is accurate for every observable.
• Solving a structured 2 to the 50 by 2 to the 50 system in simulation does not demonstrate advantage if classical methods exploit the same structure.

How it compares

• HHL has provable scaling but needs fault-tolerant hardware, while VQLS runs on noisy devices without guarantees.
• QSVT-based solvers have optimal scaling in the condition number and need deep circuits.
• Classical conjugate gradient and direct solvers are fast and widely used.

Real-world impact

More practical than HHL on near-term hardware, though without provable exponential speedup. Used in early-stage quantum linear algebra pilots in finance and logistics.

Why it matters

VQLS is one of the clearest examples of the near-term strategy: replace a deep, provably efficient algorithm with a shallow, trainable one. It shows both the promise and the problems of that strategy, particularly trainability.

The cost-function lessons, especially the benefit of local costs, carry over to other variational algorithms.

Frequently asked questions

Keep learning

• Related algorithm: HHL Algorithm
• Related algorithm: Variational Quantum Eigensolver (VQE)
• Related algorithm: Quantum Singular Value Transformation (QSVT)
• Related algorithm: Quantum Natural Gradient Descent

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database