Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
We analyze the role of coherent tunneling that gives rise to bands of delocalized quantum states providing a coherent pathway for population transfer (PT) between computational states with similar energies. Given an energy function ${\cal E}(z)$ of a binary optimization problem and a bit-string $z_i$ with atypically low energy, our goal is to find other bit-strings with energies within a narrow window around ${\cal E}(z_i)$. We study PT due to quantum evolution under a transverse field $B_\perp$ of an n-qubit system that encodes ${\cal E}(z)$. We focus on a simple yet nontrivial model: $M$ randomly chosen "marked" bit-strings ($2^n \gg M$) are assigned energies in the interval ${\cal E}(z)\in[-n -W/2, n + W/2]$ with $W << B_\perp$, while the rest of the states are assigned energy $0$. The PT starts at a marked state $z_i$ and ends up in a superposition of $\sim Ω$ marked states inside the PT window. The scaling of a typical runtime for PT with $n$ and $Ω$ is the same as in the multi-target Grover's algorithm, except for a factor that is equal to $\exp(n \,B_{\perp}^{-2}/2)$ for $n \gg B_{\perp}^{2} \gg 1$. Unlike the Hamiltonians used in analog quantum search algorithms, the model we consider is non-integrable, and the transverse field delocalizes the marked states. PT protocol is not sensitive to the value of B and may be initialized at a marked state. We develop microscopic theory of PT. Under certain conditions, the band of the system eigenstates splits into mini-bands of non-ergodic delocalized states, whose width obeys a heavy-tailed distribution directly related to that of PT runtimes. We find analytical form of this distribution by solving nonlinear cavity equations for the random matrix ensemble. We argue that our approach can be applied to study the PT protocol in other transverse field spin glass models, with a potential quantum advantage over classical algorithms.