PIRSA:10070006

Anderson localization and adiabatic quantum optimization

Roland, J. (2010). Anderson localization and adiabatic quantum optimization. Perimeter Institute. https://pirsa.org/10070006

Roland, Jeremie. Anderson localization and adiabatic quantum optimization. Perimeter Institute, Jul. 04, 2010, https://pirsa.org/10070006 

          @misc{ pirsa_PIRSA:10070006,
            doi = {10.48660/10070006},
            url = {https://pirsa.org/10070006},
            author = {Roland, Jeremie},
            keywords = {},
            language = {en},
            title = {Anderson localization and adiabatic quantum optimization},
            publisher = {Perimeter Institute},
            year = {2010},
            month = {jul},
            note = {PIRSA:10070006 see, \url{https://pirsa.org}}
          }

Jeremie Roland

NEC Laboratories America (Princeton)

Talk number
PIRSA:10070006
Collection
Talk Type
Abstract
Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We show that this effect makes adiabatic quantum optimization fail, as the system gets trapped in one of the numerous local minima. We will also discuss recent developments including the effect of the exponential number of solutions and Hamiltonian path change. Joint work with Boris Altshuler and Hari Krovi Based on arXiv:0908.2782 and arXiv:0912.0746