Quantum linear system solver based on continuous and discrete adiabatic quantum computing

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can solve a quantum linear system problem with O(κ*poly(log(κN/ε))) complexity, where κ is the condition number, N is the dimension of the linear system, and ε is the desired level of errors. This achieves an exponential speedup over classical iterative linear system solvers such as conjugate gradient method in terms of the dimension N, and the scalings in terms of all parameters are near optimal. Furthermore, we carefully discuss how to discretize our AQC-based algorithm. Amazingly, it turns out that the simplest first order Trotterization can preserve the O(κ*poly(log(κN/ε))) complexity without incurring any overhead, thus promising to be implemented on near-term quantum devices. Such an unexpected exponential convergence of the first order Trotterization can be proved via discrete version of adiabatic theorem, and also motivates further research on general applications of AQC other than solving quantum linear system problem.