Variational Quantum Linear Solver
A near-term hybrid method that solves linear systems by minimizing a cost function measuring how far Ax deviates from b.
Motivation
The HHL algorithm solves linear systems with deep circuits requiring phase estimation, beyond near-term hardware. The Variational Quantum Linear Solver (VQLS) instead uses a shallow parameterized circuit and a classical optimizer, trading provable speedups for feasibility on noisy devices. It targets A x = b by preparing a trial |x(theta)> and adjusting theta until A|x(theta)> aligns with |b>.
The cost function
Assume A is given as a linear combination of unitaries A = sum_l c_l A_l, and that a unitary U prepares |b> = U|0>. The trial solution is |x(theta)> = V(theta)|0> for an ansatz V. A natural cost measures the overlap between A|x(theta)> and |b>: the algorithm minimizes 1 - |
Evaluating the cost
- Terms of A^dagger A expand into products A_l^dagger A_{l'}, each measurable with Hadamard-test circuits.
- The overlap with |b| uses the state-preparation unitary U and controlled operations.
- Local cost functions replace the global overlap with per-qubit terms to keep gradients from vanishing.
The loop
Prepare |x(theta)>, estimate the cost via Hadamard tests over the unitary decomposition, and let a classical optimizer update theta. Convergence yields a state proportional to the solution. As with all variational methods, the ansatz must be expressive enough to contain the solution and shallow enough to run reliably.
Strengths and limits
VQLS runs on current hardware and avoids phase estimation, but it inherits variational pitfalls: local minima, barren plateaus for global costs, and measurement overhead that grows with the number of terms in A. Its output, like HHL's, is a quantum state, so extracting full solution vectors costs O(N). It is most useful when the solution feeds an expectation value or a downstream quantum routine. See HHL caveats for the shared readout limitation.