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

Abstract

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.

arXiv comment28 pages, 3 figures

References in corpus (21)

• Quantum algorithm for solving linear systems of equations
• Adiabatic Quantum Computing
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Search by Local Adiabatic Evolution
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Theory of Trotter Error
• Bounds for the adiabatic approximation with applications to quantum computation
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A quantum linear system algorithm for dense matrices
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• How Powerful is Adiabatic Quantum Computation?
• Quantum Adiabatic Brachistochrone
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Improved Error-Scaling for Adiabatic Quantum State Transfer
• Necessary Condition for the Quantum Adiabatic Approximation
• Optimal control of superconducting gmon qubits using Pontryagin's minimum principle: preparing a maximally entangled state with singular bang-bang protocols
• How Quantum is the Speedup in Adiabatic Unstructured Search?

Cited by in corpus (9)

• Variational algorithms for linear algebra
• Large gradients via correlation in random parameterized quantum circuits
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Minimizing estimation runtime on noisy quantum computers
• Concentration for random product formulas
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Complexity of quantum state verification in the quantum linear systems problem
• Success of digital adiabatic simulation with large Trotter step