Many-body quantum systems provide a mechanism for robust and efficient quantum search

Searching low energy subspace of a classical spin glass is computationally hard due to ladscape of deep local minima separated by barriers. Applying a transverse field gives rise to tunneling between the quantum states defined within individual spin-glass minima. The number of transitions from a state grows exponentially with the number d of spin flips during the transition. This growth can compensate the decrease of the matrix elements with d leading to a transition from many-body localized to non-ergodic extended phase, where eigenstaes are sparse superpositions of spin configurations corresponding to local minima within a narrow energy belt. We demonstrate a remarkable structure in the low energy eigenspectrum: it is partitioned into the alternating sequence of bands of two qualitatively different types, x- and z-, which retain characteristics of transverse field eigenstates and classical spin glass, respectively. We demonstrate this novel intermittency in a "wide band" impurity model with a bi-modal classical density of states with a delta-peak at zero energy containing most states and the second peak containing an exponentially smaller number of states lying at low energy. This non-ergodic structure of the eignespectrum provides a mechanism for efficient quantum search.