September 26, 2022

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.

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)

Read more.