Experimental Quantum Computing to Solve Systems of Linear Equations

Abstract

Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables $N$. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order $\log (N)$, giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving $2\times 2$ linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.