Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1807.04792

Efficient population transfer via non-ergodic extended states in quantum spin glass

Kostyantyn Kechedzhi, Vadim Smelyanskiy, Jarrod R. McClean, Vasil S. Denchev, Masoud Mohseni, Sergei V. Isakov, Sergio Boixo, B. L. Altshuler, Hartmut Neven

Published Jul 12, 2018• 23 citations
arXivHTMLPDF

Abstract

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 /(2B^2))$ for finite transverse field $B\gg1$. 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.

DOI
10.48550/arxiv.1807.04792

Related papers

Efficient Population Transfer via Non-Ergodic Extended States in Quantum Spin Glass

Kostyantyn Kechedzhi, Vadim Smelyanskiy, Jarrod R. McClean +6 more

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.

Leibniz international proceedings in informatics•Jan 1, 2018•5 citations

Nonergodic Delocalized States for Efficient Population Transfer within a Narrow Band of the Energy Landscape

Vadim N. Smelyanskiy, Kostyantyn Kechedzhi, Sergio Boixo +3 more

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.

arXiv:1802.09542•Physical Review X•Jan 24, 2020•57 citations

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

Kostyantyn Kechedzhi, Vadim Smelyanskiy, Sergei V. Isakov +2 more

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.

Bulletin of the American Physical Society•Mar 5, 2018•0 citations

Multifractal Dynamics of the QREM

Tommaso Parolini, Gianni Mossi

We study numerically the population transfer protocol on the Quantum Random Energy Model and its relation to quantum computing, for system sizes of $n\leq 20$ quantum spins. We focus on the energy matching problem, i.e. finding multiple approximate solutions to a combinatorial optimization problem when a known approximate solution is provided as part of the input. We study the delocalization process induced by the population transfer protocol by observing the saturation of the Shannon entropy of the time-evolved wavefunction as a measure of its spread over the system. The scaling of the value of this entropy at saturation with the volume of the system identifies the three known dynamical phases of the model. In the non-ergodic extended phase, we observe that the time necessary for the population transfer to complete follows a long-tailed distribution. We devise two statistics to quantify how effectively and uniformly the protocol populates the target energy shell. We find that population transfer is most effective if the transverse-field parameter $Γ$ is chosen close to the critical point of the Anderson transition of the model. In order to assess the use of population transfer as a quantum algorithm we perform a comparison with random search. We detect a "black box" advantage in favour of PT, but when the running times of population transfer and random search are taken into consideration we do not see strong indications of a speedup at the system sizes that are accessible to our numerical methods. We discuss these results and the impact of population transfer on NISQ devices.

arXiv:2007.00315•Jul 1, 2020•7 citations

Intermittency of dynamical phases in a quantum spin glass

Vadim Smelyanskiy, Kostyantyn Kechedzhi, Sergio Boixo +2 more

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_{\perp}$. 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

arXiv:1907.01609•Jul 2, 2019•7 citations

Non-ergodic phenomena in many-body quantum systems

Tommaso Parolini

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.

•Oct 7, 2020•0 citations
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)E(z)E(z) encodes a classical optimization problem over the set of spin configurations zzz. 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: MMM randomly chosen marked bit-strings are assigned energies E(z)E(z)E(z) within a narrow strip [−n−W/2,n+W/2][-n -W/2, n + W/2][−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))\exp(n /(2B^2))exp(n/(2B2)) for finite transverse field B≫1B\gg1B≫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.
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 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 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<<2nM<<2^nM<<2n selected at random are assigned random energies distributed in a narrow window of width W<<1W<<1W<<1 around the mean energy −n-n−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.
We study numerically the population transfer protocol on the Quantum Random Energy Model and its relation to quantum computing, for system sizes of n≤20n\leq 20n≤20 quantum spins. We focus on the energy matching problem, i.e. finding multiple approximate solutions to a combinatorial optimization problem when a known approximate solution is provided as part of the input. We study the delocalization process induced by the population transfer protocol by observing the saturation of the Shannon entropy of the time-evolved wavefunction as a measure of its spread over the system. The scaling of the value of this entropy at saturation with the volume of the system identifies the three known dynamical phases of the model. In the non-ergodic extended phase, we observe that the time necessary for the population transfer to complete follows a long-tailed distribution. We devise two statistics to quantify how effectively and uniformly the protocol populates the target energy shell. We find that population transfer is most effective if the transverse-field parameter ΓΓΓ is chosen close to the critical point of the Anderson transition of the model. In order to assess the use of population transfer as a quantum algorithm we perform a comparison with random search. We detect a "black box" advantage in favour of PT, but when the running times of population transfer and random search are taken into consideration we do not see strong indications of a speedup at the system sizes that are accessible to our numerical methods. We discuss these results and the impact of population transfer on NISQ devices.
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 (xxx and zzz). Those of zzz-type are non-ergodic extended eigenstates (NEE) in the basis of {σz}\{σ_z\}{σ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⊥B_{\perp}B⊥​. Those of xxx-type form narrow bands of NEEs that conserve the integer-valued xxx-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 (zzz-type) or Gaussian Orthogonal ensemble (xxx-type). We characterize the non-equilibrium dynamics using fractal dimension DDD that depends on energy density (temperature) and plays a role of thermodynamic potential: D=0D=0D=0 in MBL phase, $0
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.