Variational Quantum Linear Solver: A Hybrid Algorithm for Linear Systems

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> such that A|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> and A|x>, and we derive an operational meaning for this cost in terms of the solution precision. 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 × 32. Furthermore, we numerically find that the complexity of our algorithm scales efficiently in both 1/ and κ, with κ the condition number of A. Our algorithm provides a heuristic for quantum linear systems that could make this application more near term.