Theory Seminar: Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

Davide Orsucci
In this talk, I will present the results of the paper [Subasi, Somma, Orsucci, PRL 122(6), 060504 (2019)].

Davide Orsucci
Herbert-Walther Lecture Hall G0.25
Wed, 8. November 2019, 11:30 am

Abstract:

In this talk, I will present the results of the paper [Subasi, Somma, Orsucci, PRL 122(6), 060504 (2019)]. Here, a new quantum algorithms is developed that allows to prepare a quantum state |x⟩ that is proportional to the solution of the linear system of equations Ax=b. The algorithm is based on evolution randomization, a simple variant of adiabatic quantum computing. The time complexity is almost linear ϰ and linear in 1/ε, where ϰ is the condition number of A and ε is the precision. The algorithms is simple: it is not obtained using equivalences between the gate model and adiabatic quantum computing, does not use phase estimation, and does not use variable-time amplitude amplification. Further recent experimental results and theoretical developments are also presented and discussed.