MECHANISM OF QUANTUM SPEEDUP IN POPULATION TRANSFER PROTOCOL FOR BINARY OPTIMIZATION PROBLEMS
A cura di
Vadim Smelyanskiy
→
Europe/Rome
Sala Cortini (Dip. di Fisica - Edificio E. Fermi)
Sala Cortini
Dip. di Fisica - Edificio E. Fermi
Descrizione
An important problem in quantum computation is whether quantum many-body effects can lead to a computational speedup in binary optimization problems. Typically the energy landscape is characterized by a large number of spurious local minima at the tail of the density of states. While close in energy, they can be separated by large Hamming distances. This landscape gives rise to an interesting computational primitive: given an initial bit-string with sufficiently low energy, we are to produce other bit-strings within certain narrow range of energies around the initial state. The relevant quantum model for this problem is a spin glass system in a transverse field which enables population transfer through tunneling transitions with large number of spin flips. On the tail of the density of states there exists a mobility edge that separates manybody delocalized and localized phases. If the energy of the initial state lies above the mobility edge, the coherent population transfer proceeds predominantly within an exponentially narrow (in the number of spins) energy miniband formed by non-ergodic delocalized eigenstates. We study the version of the random energy model in transverse field where a large number of computational basis states is selected at random with energies distributed within the narrow band. We obtain an analytical closed form solution of the Abou-Chakra-Anderson-Thouless equations for the distribution of the imaginary part of the Green function that is dominated by the tunneling transitions on large Hamming distances. This distribution is qualitatively different from both Rosenzweig-Porter and random regular graph models. We demonstrate a Grover speedup in this problem.
