Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Dong An, Lin Lin

Published 2019-09-12Version 1

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can solve a quantum linear system problem (QLSP) with $\mathcal{O}(\kappa/\epsilon)$ runtime, where $\kappa$ is the condition number, and $\epsilon$ is the target accuracy. This achieves the optimal time complexity with respect to $\kappa$. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) can also achieve the $\mathcal{O}(\kappa)$ complexity with respect to $\kappa$. Our method is applicable to general non-Hermitian matrices (possibly dense), but the efficiency can be improved when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method. The runtime of QAOA is observed numerically to be only $\mathcal{O}(\kappa\text{poly}(\log(1/\epsilon)))$.