Quantum Computing Seminar: Quantum linear system solvers based on continuous and discrete adiabatic quantum computing

Speaker:  Dong An, University of Maryland

Title:  Quantum linear system solvers based on continuous and discrete adiabatic quantum computing

Abstract:   During the past decade, designing quantum algorithms for solving linear systems of equations has attracted great attention due to its potential exponential speedup over classical algorithms and its wide applications in solving differential equations, optimization, and quantum machine learning. This talk will discuss how to design optimal quantum linear system solvers using adiabatic quantum computing (AQC). First, we will briefly introduce the framework of AQC and demonstrate that with an optimally tuned scheduling function, AQC can solve a quantum linear system problem with O(κ*poly(log(κN/ε))) complexity, where κ is the condition number, N is the dimension of the linear system, and ε is the desired level of errors. This is near-optimal in terms of both condition number and accuracy. Then, we carefully discuss how to discretize our AQC-based algorithm. Amazingly, it turns out that the simplest first-order Trotter method can preserve the optimal complexity without incurring any overhead, and the time step size can be as large as O(1). Such an unexpected performance of the first order Trotter method can be proved via the discrete version of the adiabatic theorem, and also motivates further research on general applications of AQC other than solving quantum linear system problems.

Time:   Monday, February 7, 12:00pm – 1:00pm

Place:  Zoom