Quantum algorithm

Quantum mechanics

Adiabatic quantum computation

Algorithm

Quantum computer

Pure mathematics

Discrete mathematics

Quantum error correction

Applied mathematics

Time complexity

Computer science

Mathematical optimization

Solver

Quantum system

Physics

Quantum phase estimation algorithm

Mathematics

Quantum

Qubit

Adiabatic process

Hermitian matrix

ACM Transactions on Quantum Computing

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with $\mathcal{O}(\kappa~\text{poly}(\log(\kappa/\epsilon)))$ runtime, where $\kappa$ is the condition number, and $\epsilon$ is the target accuracy. This is near optimal with respect to both $\kappa$ and $\epsilon$. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.

Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm