- Home »
- Adiabatic optimization without a priori knowledge of the spectral gap

Performing a quantum adiabatic optimization (AO) algorithm with the time-dependent Hamiltonian H(t) requires one to have some idea of the spectral gap γ(t) of H(t) at all times t. With only a promise on the size of the minimal gap γ_{min}, a typical statement of the adiabatic theorem promises a runtime of either O(γ_{min}^{-2}) or worse. In this talk, I provide an explicit algorithm that, with access to an oracle that returns the spectral gap γ(t) to within some multiplicative constant, reliably performs QAO in time Õ(γ_{min}^{-1}) with at most O(log(γ_{min}^{-1})) oracle queries. I then construct such an oracle using only computational basis measurements for the toy problem of a complete graph driving Hamiltonian on V vertices and arbitrary cost function. I explain why one cannot simply perform adiabatic Grover search and prove that one can still perform QAO in time Õ(V^{2/3}) without any *a priori* knowledge of γ(t). This work was done in collaboration with Brad Lackey, Aike Liu, and Kianna Wan.

Collection/Series:

Event Type:

Seminar

Scientific Area(s):

Speaker(s):

Event Date:

Wednesday, September 19, 2018 - 16:00 to 17:30

Location:

Bob Room

Room #:

405

©2012 Perimeter Institute for Theoretical Physics