F07.00005. Variational Quantum Linear Solver: A Hybrid Algorithm for Linear Systems

Presented by: Carlos Bravo-Prieto


Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare $|x\rangle$ such that $A|x\rangle\propto|b\rangle$. VQLS assumes that $A = \sum_l c_l A_l$ is given as a linear combination of unitaries, and we provide an efficient procedure for obtaining this decomposition when $A$ is sparse. Furthermore, we derive an operationally meaningful termination condition for VQLS that allows one to verify that a desired solution precision $\epsilon$ is achieved. Specifically, we prove that $C \geq \epsilon^2 / \kappa^2$, where $C$ is the VQLS cost function and $\kappa$ is the condition number of $A$. We present efficient quantum circuits to estimate $C$, while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of $1024\times1024$. Finally, we numerically solve non-trivial problems of size up to $2^{50}\times2^{50}$. For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in $\epsilon$, $\kappa$, and the system size $N$.


  • Carlos Bravo-Prieto
  • Ryan LaRose
  • Marco Cerezo
  • Yigit Subasi
  • Lukasz Cincio
  • Patrick J. Coles


Powered by Q-CTRL

© 2020 Virtual APS March Meeting. All rights reserved.