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

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 ${\beta }_f\sim 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 down-folded 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_{\perp }$ starts at a low-energy spin configuration and ends up in a superposition of $\mathrm{\Omega }$ 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_{\mathrm{cl}}=2^n/\mathrm{\Omega }$. For $\sqrt{n}\gg B_{\perp }\gg 1$, the typical run-time of the quantum PT algorithm $\sqrt{t_{\mathrm{cl}}}{e}^{n/(2B_{\perp }^2)}$ scales with $n$ and $\mathrm{\Omega }$ 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.

Popular Summary

Computational search and optimization problems are key applications of quantum computers. New insight into how efficient quantum algorithms are at solving these problems can be gained by analyzing the dynamics of quantum extensions of closely related classical spin-glass models, which allow for an analytical description of their statistical mechanics and, in limited cases, classical dynamics. We report the first analytical treatment of quantum dynamics of a model of this type and propose a protocol for the efficient search of low-energy configuration space of spin glasses.

The key technical progress of our work is the derivation of an effective low-energy Hamiltonian, which describes quantum dynamics of the model within a subspace of states with energies within a narrow band. Our derivation reduces the original spin Hamiltonian to a model of random matrix theory of exponentially smaller dimension, specified by a probability distribution of matrix elements. Within this framework, we calculate the statistics of many-body relaxation rates and demonstrate that the run-time of our “population transfer protocol” is asymptotically optimal for the impurity band model, corresponding to the multitarget Grover’s algorithm for unstructured database search.

Extensions of our analysis to a wider range of search and optimization problems present an exciting new field of research with the potential for computational speedups.

Figure 1

Cartoon of the level diagram. Horizontal blue lines depict the energy levels $-B_{\perp }(n-2m)$ of the driver Hamiltonian $H_D$ in Eq. (1) separated by $2B_{\perp }$. A narrow impurity band of width $W\ll B_{\perp }$ is marked in light green. The sequence of short black lines depicts the energies of marked states $\mathcal{E}(z_i)$. Dashed lines depict the elementary path to the leading-order perturbation theory in $B_{\perp }$ for the tunneling matrix element $c_{ij}(E)$ given in Eq. (19). In this paper, we focus on the case of relatively large transverse fields $B_{\perp }>1$ so that the IB energies lie above the ground state of the total Hamiltonian (1) that corresponds to nearly all qubits polarized in the $x$ direction.

Figure 2

Colored lines show the dependence of the rescaled logarithm of the coupling coefficient $n^{-1}\log c^2(E,d)$ [Eq. (23)] on the rescaled Hamming distance $d/n$ for $n=400$. The energy $E$ is set to the value $E^{(0)}\simeq -n-B_{\perp }^2$ that reflects the overall shift of the impurity band due to the transverse field [cf. Eqs. (36) and (37)]. Different colors correspond to different values of the transverse field $B_{\perp }=1.93$ (red), 1.43 (blue), 1.11 (green), 1.01 (brown), 0.99 (purple), and 0.95 (gray). The scale along the $y$ axis suggests that $c(E^{(0)},d)$ scales exponentially with $n$ for $d/n=\mathcal{O}(n^0)$. The inset shows the leading-order factor in the $d$ dependence of the coupling coefficient for $B_{\perp }>|E|/n$ [cf. Eq. (33)]. Black dots show the boundaries $d=n/2-m_0,n/2+m_0$ of the region of the oscillatory behavior of $c(E,d)$ with $d$ given by the WKB theory [Eq. (32)] (see Appendix pp2 for details).

Figure 3

The black line shows the plot of $2u(m)$ (31) vs $m$ between the interval boundaries $\pm m=L=(n+1)/2$. The horizontal dashed-dotted blue line depicts the region of oscillatory behavior of $G_{m,n/2}(E)$ with $m$ for a given $E$ described by the WKB solution (33) [see also Eq. (b5) in Appendix pp2] and shown in Fig. 4. The boundaries of this region are the turning points $m=\pm m_0(E)$ given by Eq. (32) and depicted with blue dots. The regions of $m\in [m_0(E),L]\cup [-L,-m_0(E)]$ correspond to the exponential growth of $G_{m,n/2}(E)$ with $m$ (or decrease with $d=n/2-m$). The WKB solution for the right region is given in Eq. (b10).

Figure 4

The blue curve shows the $d$ dependence of the (rescaled) coupling coefficients $c(E,d)$ computed from the exact expression (23) with $n=224$ and $E=-226.15$. We denote the binomial coefficient as $(\genfrac{}{}{0ex}{}{n}{d})\equiv C_d^n$. The transverse field is $B_{\perp }=1.459$. For this value of $B_{\perp }$, the impurity band levels $\mathcal{E}(z_j)$ lie approximately in the middle of the interval between the $p=34$th and $p=35$th excited energy levels $-B_{\perp }(n-2p)$ of the driver Hamiltonian. Red points depict the $d$ dependence of the same rescaled coefficients $c(E,d)$ given by $G_{n/2-d,n/2}\exp (n\theta )$ and determined by the asymptotic WKB expressions given in Appendix pp2 [see Eqs. (b10) and (b13)]. Dashed lines indicate the boundaries of the oscillatory behavior of the WKB solution [Eq. (b9)]. The inset shows the plot for the exponential $d$ dependence of the rescaled coupling coefficient $-c(E,d)$ in the region of its monotonic behavior $d\in [1,n/2-m_0(E)]$ [cf. Eqs. (b13) and (29)]. The solid blue line corresponds to the exact expression (23), while the approximate WKB solution is shown with red points.

Figure 5

Plots of the WKB phase ${\varphi }_d\equiv \varphi (E,d)$ of the oscillations of the coupling coefficient $c(E,d)$ with the Hamming distance $d$ for a number of qubits $n=1000$. Both axes are rescaled by $n$. The phase is plotted relative to its value at $d=n/2$. We set the energy $E=E^{(0)}$, where $E^{(0)}\simeq -n-B_{\perp }^2$ reflects the overall shift of the impurity band due to the transverse field [cf. Eqs. (36) and (37)]. Different color curves correspond to different values of $B_{\perp }>|E|/n$ with $B_{\perp }=1.1$ (brown), $B_{\perp }=1.2$ (orange), $B_{\perp }=1.5$ (red), $B_{\perp }=2.1$ (green), $B_{\perp }=3.2$ (blue), and $B_{\perp }=10$ (black). Each curve varies in its own range $n/2-d\in [-m_0,m_0]$, where $m_0$ is given in Eq. (32) and determines the region of oscillatory behavior of the coupling coefficients (see Appendix pp2 for details). For $B_{\perp }\simeq 1$, the region of oscillatory behavior shrinks to a point $d\simeq n/2$. In the limit of large values of $B_{\perp }\gg 1$, this behavior occupies almost the entire range $d\in [0,n]$.

Figure 6

Solid lines show the dependence on the transverse field $B_{\perp }$ of the eigenvalues $E_{\beta }$ of the nonlinear eigenvalue problem with Hamiltonian $\mathcal{H}(E)$ for the case of $n=50$ and $M=2$. The plot shows the repeated avoided crossing between the two systems of eigenvalues. One system (colored lines) corresponds to the eigenvalues of the transverse-field (driver) Hamiltonian $H_D=-B_{\perp }{\sum }_{k=0}^n{\sigma }_x^k$ in the limit $H_{\mathrm{cl}}\to 0$. The second system of eigenvalues corresponds to the energies of the two marked states in the limit $B_{\perp }\to 0$. The splitting of the eigenvalues is exponentially small in $n$ and not resolved in the plot. The asymptotic expressions (36) and (37) for the two eigenvalues $E_{1,2}^{(0)}=E^{(0)}$ neglecting the tunneling splitting and setting $\mathcal{E}(z_j)=-n$ for all $j\in [1,M]$ are shown with a dashed gray line.

Figure 7

The solid red line shows the dependence of the total weight $Q$ vs transverse field $B_{\perp }$ for $n=40$. Vertical black and blue lines, respectively, depict the locations of $p$-even and $p$-odd resonances $B_{\perp }=B_{\perp p}$ defined in the text. The total weight $Q$ undergoes sharp decreases in the vicinity of even resonances. For $p<5$, the resonance regions are so narrow that dips in $Q$ are not seen. The width of the regions grows steeply with $p$.

Figure 8

Plot of the maximum value of the transverse field at midresonance point $B_{\perp }^{\max }$ as a function of $n$. We define $B_{\perp }^{\max }=(B_{\perp p}+B_{\perp p+1})/2$, where $B_{\perp ,p}\simeq n/(n-2p)$ satisfies the equation $E^{(0)}=-B_{\perp ,k}(n-2p)$ and the integer $p$ is equal to its maximum possible value $p=p_{\max }$ for which the weight factor $Q=Q((B_{\perp p}+B_{\perp p+1})/2)\ge 0.98$.

Figure 9

Red points show the empirical probability distribution $M_j^{(d)}$ vs $d$ with $M_j^{(d)}={\sum }_{j=1}^M\delta (d_{ij}-d)$. Here, $d_{ij}$ is a matrix of Hamming distances $d_{ij}$ between the set of $M$ randomly chosen $n$-bit strings (marked states), and $i$ is a randomly chosen marked state. The distribution corresponds to $M={10}^7$ and $n=60$. Black stars connected by a black line show the samples $m_d$ from multinomial distribution with mean values $⟨M_j^{(d)}⟩=M{p}_d$, where $p_d$ is binomial distribution (49).

Figure 10

The inverse participation ratio $I_2={\sum }_i|⟨i|{\psi }_{\beta }⟩{|}^4$ as a function of the average classical (at a vanishing transverse field) energy level spacing $\delta \epsilon$ in units of the typical coupling $V_{\text{typ}}$ for different numbers $M$ of states in the impurity band. We see that for $\delta \epsilon /V_{\text{typ}}\ge 1$ the eigenstates become localized and $I_2\to 1$ independent of $M$, indicative of eigenstates localized on single bit string each.

Figure 11

The rescaled inverse participation ratio $I_{2}M/3$ as a function of the rescaled impurity band width $W/(M{V}_{\text{typ}})$ for different numbers $M$ of states in the impurity band. We see that in the ergodic regime, $W/(M{V}_{\text{typ}})\le 1$, we have $I_{2}M/3=1$, corresponding to the orthogonal Porter-Thomas distribution of states in the impurity band. The inset shows the numerical probability distribution of normalized probabilities $Mp$ for an eigenstate over computational states $z$ in the ergodic regime in black and the analytical orthogonal Porter-Thomas distribution in red. Qualitative arguments in Sec. 8 suggest that in the nonergodic delocalized regime $I_{2}M/3\propto [W/(M{V}_{\text{typ}}){]}^2$. The black line is proportional to $[W/(M{V}_{\text{typ}}){]}^2$, and we see that $I_{2}M/3$ aligns with this quantity as long as we do not enter the localized regime $\delta \epsilon /V_{\text{typ}}\ge 1$; see Fig. 10.

Figure 12

The multifractal dimensions $D_1$ [defined in Eq. (66)] and $D_2$ [defined in Eq. (65)] as functions of $\gamma$ for the ensemble of IB Hamiltonians with the dispersion of classical energies $W=\lambda V_{\text{typ}}{M}^{\gamma /2}$, with $\lambda =3.3$. All the multifractal dimensions $D_q$ approach 1 in the ergodic regime ($\gamma =1$) and 0 in the localized regime ($\gamma =2$). The difference between $D_1$ and $D_2$ is also likely due to finite size effects. We also extract a scaling exponent from the dynamical correlator [see Eqs. (68) and (69)]. The dot-dashed line corresponds to the analytical value in the Rosenzweig-Porter limit given by Eq. (72).

Figure 13

We plot the rescaled overlap correlation function $K(\omega ){\mathrm{\Gamma }}_{ϵ}$ vs $\omega /{\mathrm{\Gamma }}_{ϵ}$, where ${\mathrm{\Gamma }}_{ϵ}={\mathrm{\Gamma }}_{\text{typ}}{M}^{ϵ}$ and ${\mathrm{\Gamma }}_{\text{typ}}=2{\mathrm{\Sigma }}_{\text{typ}}^{\prime \prime }$ is the typical miniband width and ${\mathrm{\Sigma }}_{\text{typ}}^{\prime \prime }\propto V_{\text{typ}}{M}^{1-\gamma /2}(\log M{)}^{1/2}$ [Eq. (128)]. Different curves correspond to different values of $M$ and collapse well with $ϵ=0.05$. We use the ensemble of IB Hamiltonians with a dispersion of classical energies $W=\lambda V_{\text{typ}}{M}^{\gamma /2}$, with $\gamma =1.2$ and $\lambda =3.3$.

Figure 14

Cartoon of the energies of the marked states ${\epsilon }_m$ within the impurity band. Energy levels are shown with solid black lines forming groups arranged vertically. All states $|z_m⟩$ within one group lie at the same Hamming distance $d_{jm}=d$ from a given state $|z_j⟩$ with $d$ increasing from right to left. The energy level ${\epsilon }_j$ is depicted at the right side of the figure with a thick black line. Arrows depict the transitions away from the initial state $|\psi (0)⟩=|z_j⟩$ into the marked states $|z_m⟩$ whose energy levels lie inside the miniband of the width ${\mathrm{\Gamma }}_j$ centered at ${\epsilon }_j$; i.e., they satisfy the condition $|{\epsilon }_j-{\epsilon }_m|\lesssim {\mathrm{\Gamma }}_j$. The miniband width is indicated with the gray shading area. Arrows of the same color depict transitions within one decay channel, connecting the state $|z_j⟩$ to the states a Hamming distance $d$ away from it. Smaller values of $d$ correspond to bigger typical level spacings $\delta {\epsilon }_j^d$ [Eq. (87)] and fewer states in a miniband ${\mathrm{\Omega }}_d$ [Eq. (98)] within the decay channel given by $d$.

Figure 15

The black solid line shows the plot of the Levy alpha-stable distribution $L_{\alpha }^{C,\beta }(x)$ [33] with tail index $\alpha =1$, asymmetry parameter $\beta =1$, and unit scale parameter $C=1$. The inset shows asymptotic behavior of the distribution at large positive $x$. At $-x\gg 1$, the function decays steeply as a double exponential, $\log L_1^{1,1}(x)\propto -\exp [-(\pi /2)x]$. The blue line shows the Cauchy distribution $L_1^{1,0}(x)=\{1/[\pi (1+x^2)]\}$. We follow here the definition introduced in Ref. [33] and used in subsequent papers on Levi matrices in the physics literature. In the mathematical literature [61, 62], a different definition is usually used, corresponding to $f(x;\alpha ,\beta ,C^{1/\alpha },0)=L_{\alpha }^{C,\beta }(x)$.

Figure 16

Plot of the PDF $g_Y(x)$ of the random variable $x=\{(w{Y}^2)/[(z-\epsilon {)}^2+Y^2]\}$, where random variables $\epsilon$ and $w$ obey distributions $W^{-1}{p}_A(\epsilon /W)$ and $g_{\infty }(w)$, respectively, and $W/(2Y)=\sqrt{30}$. A detailed discussion of $g_Y(x)$ is given in Appendix pp12 [see Eq. (l7)]. Its maximum is located at $x\sim (Y/W{)}^2$. The singularity at $x=1$ corresponds to $\epsilon =z$. For large values of $x\gg 1$, the conditional PDF of $\{Y^2/[(z-\epsilon {)}^2+X^2]\}$ is narrowly peaked around its mean value $\pi Y/W$ with $|\epsilon -z|\sim Y$, giving rise to the relation in Eq. (109).

Figure 17

The solid line shows the dependence of $\ell (w)$ on $\alpha =(1/n){\log }_{2}w$ from Eq. (g15). The dashed line shows the tangent to the solid curve at the point $\alpha =0$ ($w=1$). This line corresponds to $\ell (w)\simeq \sqrt{\log w}$, in accordance with Eq. (g24). The inset shows the dependence of the root ${\rho }_w$ of Eq. (g12) on $\alpha ={\log }_2{w}^{1/n}$. Small $\alpha \ll 1$ corresponds to Hamming distances ${\rho }_w\approx 1/2$. Near that point, the dependence of ${\rho }_w$ on $\alpha$ follows Eq. (g23).

Figure 18

Plot of the PDF of $p_{\eta }(h;0)\equiv p_{\eta }(h)$ given in Eq. (k6).

Figure 19

Plot of ${\overline{g}}_{\eta }(z)$ given in Eq. (l8) for $K_{\eta }=\sqrt{30}$.

Figure 20

Probability distribution of the ratio $|Y/X|$ defined in Eqs. (m1) and (m2) for $\gamma =0.6$.

Figure 21

The same as in Fig. 20 but with $\gamma =1.2$.

Figure 22

The same as in Fig. 20 but for $\gamma =1.6$.

Figure 23

$K(\omega )$ rescaled with the characteristic energy ${\mathrm{\Gamma }}_{ϵ}=2{\mathrm{\Sigma }}_{\text{typ}}^{\prime \prime }{M}^{ϵ}$ where the typical miniband width is given by Eq. (128). Here, $\gamma =1$ with fitting exponent $ϵ=-0.025$.

Figure 24

The same as in Fig. 23 but with $\gamma =1.4$ and fitting exponent $ϵ=0.04$.

Figure 25

The same as in Fig. 23 but with $\gamma =1.8$ and fitting exponent $ϵ=-0.05$.

Figure 26

The same as in Fig. 23 but with $\gamma =2$ and fitting exponent $ϵ=-0.055$.

Figure 27

Population transfer probability as a function of time $t$ in units of $1/V_{\text{typ}}$ for various values of parameter $\gamma =2a$.

Figure 28

Population transfer probability as a function of time rescaled with the effective miniband width $\sqrt{\mathrm{\Omega }}$ where the number of states in the miniband is estimated using Fermi’s golden rule $\mathrm{\Omega }=M^{2-\gamma }$; see Eq. (100) of the main text.