Quantum Linear Algebra With Near-Optimal Complexities

We introduce some relatively simple algorithms to solve linear algebra problems, such as linear systems of equations and eigenvalue problems, with near-optimal query complexities. These algorithms are simple, in the sense that their effectiveness (e.g. dependence on the condition number), does not rely on complicated procedures such as variable time amplitude amplification, repeated phase estimation etc. For linear system problems, near-optimal complexity can be achieved by adiabatic quantum computing (AQC), with an optimized scheduling procedure. It can also be achieved by an eigenstate filtering procedure, which leads to an algorithm particularly suitable for a gate-based implementation. The eigenstate filtering procedure can also be used to obtain a near-optimal ground energy solver, assuming the availability of an initial state with a decent overlap with the desired ground state.

References:

D. An and L. Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm [arXiv:1909.05500]

L. Lin and Y. Tong, Optimal quantum eigenstate filtering with application to solving quantum linear systems [arXiv:1910.14596]

L. Lin and Y. Tong, Near-optimal ground state preparation [arXiv:2002.12508]