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.
Researchers 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. They propose a cost function based on the overlap between |b⟩ and A|x⟩, and they derive an operational meaning for this cost in terms of the solution precision ϵ. They also introduce a quantum circuit to estimate this cost, while showing that this cost cannot be efficiently estimated classically. Using Rigetti’s quantum computer, they successfully implement their algorithm up to a problem size of 32×32. Furthermore, they numerically find that the complexity of their algorithm scales efficiently in both 1/ϵ and κ, with κ the condition number of A. Their algorithm provides a heuristic for quantum linear systems that could make this application more near term. (SciRate)
