PIRSA:18090052

Adiabatic optimization without a priori knowledge of the spectral gap

(2018). Adiabatic optimization without a priori knowledge of the spectral gap. Perimeter Institute. https://pirsa.org/18090052

Adiabatic optimization without a priori knowledge of the spectral gap. Perimeter Institute, Sep. 19, 2018, https://pirsa.org/18090052 

          @misc{ pirsa_PIRSA:18090052,
            doi = {10.48660/18090052},
            url = {https://pirsa.org/18090052},
            author = {},
            keywords = {Quantum Information},
            language = {en},
            title = {Adiabatic optimization without a priori knowledge of the spectral gap},
            publisher = {Perimeter Institute},
            year = {2018},
            month = {sep},
            note = {PIRSA:18090052 see, \url{https://pirsa.org}}
          }
Talk numberPIRSA:18090052
DOI10.48660/18090052
Collection
Talk Type Scientific Series
Subject

Abstract

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 Õ(V2/3)  without any a priori knowledge of γ(t). This work was done in collaboration with Brad Lackey, Aike Liu, and Kianna Wan.