Quantum-adiabatic like algorithms for linear systems of equations

Presenting Author: Yigit Subasi, Los Alamos National Laboratory
Contributing Author(s): Rolando Somma

We present a quantum method based on evolution randomization or adiabatic evolutions to prepare a quantum state that is proportional to the solution of the linear system of equations \(A \vec{x}=\vec{b}\). Our quantum algorithm is not obtained using equivalences between the circuit model and adiabatic quantum computing. We rather use simple Hamiltonians that are linear combinations of \(A\) and the projector in the initial state \(|b⟩\) when \(A>0\). The coefficients in this combination may be unknown a priori but can be estimated by running the algorithm for several intermediate times. Our quantum algorithm requires being able to measure expectation values of \(A\) and \(|b⟩⟨b|\). The overall time complexity of our approach is polynomial in the condition number \(\kappa\) and polynomial in \(1/\epsilon\), where \(\epsilon\) is the target precision. The case of non-positive \(A\) can be studied similarly by replacing \(A \mapsto A^2\), increasing the condition number to \(\kappa^2\). Our results are important in that this problem could be solved using a restricted, maybe non-universal quantum computing device that can implement evolutions with such Hamiltonians only. Just like other quantum algorithms for this problem, our method may result in an exponential quantum speedup for particular efficient specifications of \(A\) and \(b\), and when the condition number is polylogarithmic in the dimension.

(Session 5 : Thursday from 5:00pm - 7:00 pm)


SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor

SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor

Tweet About SQuInT 2018!