We address the long-standing problem of the structure of the low-energy eigenstates and long-time coherent dynamics in quantum spin-glass models.Below the spin-glass freezing transition, the energy landscape of the spin system is characterized by a proliferation of local minima where classical dynamics gets trapped.A theoretical description of quantum dynamics in this regime is challenging due to the complex nature of the distribution of the tunneling matrix elements between the local minima of the energy landscape.We study the transverse-field-induced quantum dynamics of the following "impurity band" (IB) spin model: zero energy of all spin configurations except for a small fraction of spin configurations ("marked states") that form a narrow band at a large negative energy.At a zero transverse field, the IB model demonstrates the freezing transition at inverse temperature β f ∼ 1 characterized by a nonzero value of the Edwards-Anderson order parameter.At a finite transverse field, the low-energy dynamics can be described by the effective downfolded Hamiltonian that acts in the Hilbert subspace involving only the marked states.We obtain in an explicit form the heavy-tailed probability distribution of the off-diagonal matrix elements of the down-folded Hamiltonian.This Hamiltonian is dense and belongs to the class of preferred basis Levy matrices.Analytically solving nonlinear cavity equations for the ensemble of down-folded Hamiltonians allows us to describe the statistical properties of the eigenstates.In a broad interval of transverse fields, they are nonergodic, albeit extended.It means that the band of marked states splits into a set of narrow minibands.Accordingly, the quantum evolution that starts from a particular marked state leads to a linear combination of the states belonging to a particular miniband.An analytical description of this qualitatively new type of quantum dynamics is a key result of our paper.Based on our analysis, we propose the population transfer (PT) algorithm: The quantum evolution under constant transverse field B ⊥ starts at a low-energy spin configuration and ends up in a superposition of Ω spin configurations inside a narrow energy window.This algorithm crucially relies on the nonergodic nature of delocalized low-energy eigenstates.In the considered model, the run-time of the best classical algorithm (exhaustive search) is t cl ¼ 2 n =Ω.For ffiffiffi n p ≫ B ⊥ ≫ 1, the typical runtime of the quantum PT algorithm ffiffiffiffi ffi t cl p e n=ð2B 2 ⊥ Þ scales with n and Ω as that of Grover's quantum search, except for the small correction to the exponent.Unlike the Hamiltonians proposed for analog quantum unstructured search algorithms, the model we consider is nonintegrable and the transverse field delocalizes the marked states.As a result, our PT protocol does not require fine-tuning of the transverse field and may be initialized in a computational basis state.We find that the run-times of the PT algorithm are distributed according to the alpha-stable Levy law with tail index 1.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.
We address the long-standing problem of the structure of the low-energy eigenstates and long-time coherent dynamics in quantum spin-glass models.Below the spin-glass freezing transition, the energy landscape of the spin system is characterized by a proliferation of local minima where classical dynamics gets trapped.A theoretical description of quantum dynamics in this regime is challenging due to the complex nature of the distribution of the tunneling matrix elements between the local minima of the energy landscape.We study the transverse-field-induced quantum dynamics of the following "impurity band" (IB) spin model: zero energy of all spin configurations except for a small fraction of spin configurations ("marked states") that form a narrow band at a large negative energy.At a zero transverse field, the IB model demonstrates the freezing transition at inverse temperature β f ∼ 1 characterized by a nonzero value of the Edwards-Anderson order parameter.At a finite transverse field, the low-energy dynamics can be described by the effective downfolded Hamiltonian that acts in the Hilbert subspace involving only the marked states.We obtain in an explicit form the heavy-tailed probability distribution of the off-diagonal matrix elements of the down-folded Hamiltonian.This Hamiltonian is dense and belongs to the class of preferred basis Levy matrices.Analytically solving nonlinear cavity equations for the ensemble of down-folded Hamiltonians allows us to describe the statistical properties of the eigenstates.In a broad interval of transverse fields, they are nonergodic, albeit extended.It means that the band of marked states splits into a set of narrow minibands.Accordingly, the quantum evolution that starts from a particular marked state leads to a linear combination of the states belonging to a particular miniband.An analytical description of this qualitatively new type of quantum dynamics is a key result of our paper.Based on our analysis, we propose the population transfer (PT) algorithm: The quantum evolution under constant transverse field B ⊥ starts at a low-energy spin configuration and ends up in a superposition of Ω spin configurations inside a narrow energy window.This algorithm crucially relies on the nonergodic nature of delocalized low-energy eigenstates.In the considered model, the run-time of the best classical algorithm (exhaustive search) is t cl ¼ 2 n =Ω.For ffiffiffi n p ≫ B ⊥ ≫ 1, the typical runtime of the quantum PT algorithm ffiffiffiffi ffi t cl p e n=ð2B 2 ⊥ Þ scales with n and Ω as that of Grover's quantum search, except for the small correction to the exponent.Unlike the Hamiltonians proposed for analog quantum unstructured search algorithms, the model we consider is nonintegrable and the transverse field delocalizes the marked states.As a result, our PT protocol does not require fine-tuning of the transverse field and may be initialized in a computational basis state.We find that the run-times of the PT algorithm are distributed according to the alpha-stable Levy law with tail index 1.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.
Quantum tunneling has been proposed as a physical mechanism for solving binary optimization problems on a quantum computer because it provides an alternative to simulated annealing by directly connecting deep local minima of the energy landscape separated by large Hamming distances. However, classical simulations using Quantum Monte Carlo (QMC) were found to efficiently simulate tunneling transitions away from local minima if the tunneling is effectively dominated by a single path. We analyze a new computational role of coherent multi-qubit tunneling that gives rise to bands of non-ergodic extended (NEE) quantum states each formed by a superposition of a large number of deep local minima with similar energies. NEE provide a coherent pathway for population transfer (PT) between computational states with similar energies. In this regime, PT cannot be efficiently simulated by QMC. PT can serve as a new quantum subroutine for quantum search, quantum parallel tempering and reverse annealing optimization algorithms. We study PT resulting from quantum evolution under a transverse field of an n-spin system that encodes the energy function E(z) of an optimization problem over the set of bit configurations z. Transverse field is rapidly switched on in the beginning of algorithm, kept constant for sufficiently long time and switched off at the end. Given an energy function of a binary optimization problem and an initial bit-string with atypically low energy, PT protocol searches for other bitstrings at energies within a narrow window around the initial one. We provide an analytical solution for PT in a simple yet nontrivial model: M randomly chosen marked bit-strings are assigned energies E(z) within a narrow strip [-n -W/2, n + W/2], while the rest of the states are assigned energy 0. The PT starts at a marked state and ends up in a superposition of L marked states inside the narrow energy window whose width is smaller than W. The best known classical algorithm for finding another marked state is the exhaustive search. We find that the scaling of a typical PT runtime with n and L is the same as that in the multi-target Grover's quantum search algorithm, except for a factor that is equal to exp(n /(2B^2)) for finite transverse field B >>1. Unlike the Hamiltonians used in analog quantum unstructured search algorithms known so far, the model we consider is non-integrable and the transverse field delocalizes the marked states. As a result, our PT protocol is not exponentially sensitive in n to the weight of the driver Hamiltonian and may be initialized with a computational basis state. We develop the microscopic theory of PT by constructing a down-folded dense Hamiltonian acting in the space of marked states of dimension M. It belongs to the class of preferred basis Levy matrices (PBLM) with heavy-tailed distribution of the off-diagonal matrix elements. Under certain conditions, the band of the marked states splits into minibands of non-ergodic delocalized states. We obtain an explicit form of the heavy-tailed distribution of PT times by solving cavity equations for the ensemble of down-folded Hamiltonians. We study numerically the PT subroutine as a part of quantum parallel tempering algorithm for a number of examples of binary optimization problems on fully connected graphs.
We analyze a new computational role of coherent multi-qubit quantum tunneling that gives rise to bands of non-ergodic extended (NEE) quantum states each formed by a superposition of a large number of computational states (deep local minima of the energy landscape) with similar energies. NEE provide a mechanism for population transfer (PT) between computational states and therefore can serve as a new quantum subroutine for quantum search, quantum parallel tempering and reverse annealing optimization algorithms. We study PT in a quantum n-spin system subject to a transverse field where the energy function E(z) encodes a classical optimization problem over the set of spin configurations z. Given an initial spin configuration with low energy, PT protocol searches for other bitstrings at energies within a narrow window around the initial one. We provide an analytical solution for PT in a simple yet nontrivial model: M randomly chosen marked bit-strings are assigned energies E(z) within a narrow strip [−n−W/2,n+W/2], while the rest of the states are assigned energy 0. We find that the scaling of a typical PT runtime with n and L is the same as that in the multi-target Grover's quantum search algorithm, except for a factor that is equal to exp(n/(2B2)) for finite transverse field B≫1. Unlike the Hamiltonians used in analog quantum unstructured search algorithms known so far, the model we consider is non-integrable and population transfer is not exponentially sensitive in n to the weight of the driver Hamiltonian. We study numerically the PT subroutine as a part of quantum parallel tempering algorithm for a number of examples of binary optimization problems on fully connected graphs.
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
The two primary categories for eigenstate phases of matter at a finite temperature are many-body localization (MBL) and the eigenstate thermalization hypothesis (ETH). We show that, in the paradigmatic quantum p-spin models of the spin-glass theory, eigenstates violate the ETH yet are not MBL either. A mobility edge, which we locate using the forward-scattering approximation and replica techniques, separates the nonergodic phase at a small transverse field from an ergodic phase at a large transverse field. The nonergodic phase is also bounded from above in temperature, by a transition in configuration-space statistics reminiscent of the clustering transition in the spin-glass theory. We show that the nonergodic eigenstates are organized in clusters which exhibit distinct magnetization patterns, as characterized by an eigenstate variant of the Edwards-Anderson order parameter.
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<<2n 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.
The assumption of ergodicity is the cornerstone of conventional thermodynamics, connecting the equilibrium properties of macroscopic systems to the chaotic nature of the underlying microscopic dynamics, which eventuates in thermalization and the scrambling of information contained in any generic initial condition. The modern understanding of ergodicity in a quantum mechanical framework is encapsulated in the so-called eigenstate thermalization hypothesis, which asserts that thermalization of an isolated quantum system is a manifestation of the random-like character of individual eigenstates in the bulk of the spectrum of the system's Hamiltonian. In this work, we consider two major exceptions to the rule of generic thermalization in interacting many-body quantum systems: many-body localization, and quantum spin glasses. In the first part, we debate the possibility of localization in a system endowed with a non-Abelian symmetry. We show that, in line with proposed theoretical arguments, such a system is probably delocalized in the thermodynamic limit, but the ergodization length scale is anomalously large, explaining the non-ergodic behavior observed in previous experimental and numerical works. A crucial feature of this system is the quasi-tensor-network nature of its eigenstates, which is dictated by the presence of nontrivial symmetry multiplets. As a consequence, ergodicity may only be restored by extensively large cascades of resonating spins, explaining the system's resistance to delocalization. In the second part, we study the effects of non-ergodic behavior in glassy systems in relation to the possibility of speeding up classical algorithms via quantum resources, namely tunneling across tall free energy barriers. First, we define a pseudo-tunneling event in classical diffusion Monte Carlo (DMC) and characterize the corresponding tunneling rate. Our findings suggest that DMC is very efficient at tunneling in stoquastic problems even in the presence of frustrated couplings, asymptotically outperforming incoherent quantum tunneling. We also analyze in detail the impact of importance sampling, finding that it does not alter the scaling. Next, we study the so-called population transfer (PT) algorithm applied to the problem of energy matching in combinatorial problems. After summarizing some known results on a simpler model, we take the quantum random energy model as a testbed for a thorough, model-agnostic numerical characterization of the algorithm, including parameter setting and quality assessment. From the accessible system sizes, we observe no meaningful asymptotic speedup, but argue in favor of a better performance in more realistic energy landscapes.