Abstract
Answering the question of existence of efficient quantum algorithms for NP-hard problems require deep theoretical understanding of the properties of the low-energy eigenstates and long-time coherent dynamics in quantum spin glasses. We discovered and described analytically the property of asymptotic orthogonality resulting in a new type of structure in quantum spin glass. Its eigen-spectrum is split into the alternating sequence of bands formed by quantum states of two distinct types (x and z). Those of z-type are non-ergodic extended eigenstates (NEE) in the basis of {σ_z} operators that inherit the structure of the classical spin glass with exponentially long decay times of Edwards Anderson order parameter at any finite value of transverse field B_⊥. Those of x-type form narrow bands of NEEs that conserve the integer-valued x-magnetization. Quantum evolution within a given band of each type is described by a Hamiltonian that belongs to either the ensemble of Preferred Basis Levi matrices (z-type) or Gaussian Orthogonal ensemble (x-type). We characterize the non-equilibrium dynamics using fractal dimension D that depends on energy density (temperature) and plays a role of thermodynamic potential: D=0 in MBL phase, 0<D<1 in NEE phase, D→ 1 in ergodic phase in infinite temperature limit. MBL states coexist with NEEs in the same range of energies even at very large B_⊥. Bands of NEE states can be used for new quantum search-like algorithms of population transfer in the low-energy part of spin-configuration space. Remarkably, the intermitted structure of the eigenspectrum emerges in quantum version of a statistically featureless Random Energy Model and is expected to exist in a class of paractically important NP-hard problems that unlike REM can be implemented on a computer with polynomial resources.