Mechanism of Quantum Speedup in Novel Population Transfer Protocol for Binary Optimization Problems

We consider a novel quantum population transfer protocol to solve binary optimization problems that exploits quantum many-body dynamics in the delocalized regime. Hard optimization problems are characterized by energy landscape with a large number of local minima separated by large Hamming distances which scale with the problem size. This landscape gives rise to an interesting computational primitive: given an initial bit-string, we are to produce other bit-strings within certain narrow range of energies around the initial state. We consider a specific model we call "impurity band": a system of n qubits in a transverse field, where a number of bitstrings $M<<2^n$ selected at random are assigned random energies distributed in a narrow window of width $W<<1$ around the mean energy $-n$. We demonstrate the existence of the many-body delocalized regime in this model when the spectrum of the model splits into many-body minibands, and a typical eigenstate wave function is a superposition of peaks centered at a large number of local minima. The typical width of the minibands in energy determines the efficiency of the population transfer protocol. We demonstrate theoretically that the population transfer protocol achieves Grover type speedup in the unstructured impurity band model.