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

The condition number dependence is a crucial aspect of quantum linear system solvers. We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can solve a quantum linear system problem with O(κ/ε) runtime, where κ is the condition number, and ε is the target accuracy. This achieves at least quadratic speedup over the standard vanilla AQC and reaches the complexity lower bound with respect to κ. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) can also achieve the O(κ) complexity with respect to κ. 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 O(κ*poly(log(1/ε))).