Quantum algorithm for energy matching in hard optimization problems

We consider the ability of local quantum dynamics to solve the “energy-matching” problem: given an instance of a classical optimization problem and a low-energy state, find another macroscopically distinct low-energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here, we show that the introduction of quantum dynamics can provide a speedup over classical algorithms in a large class of hard optimization problems. Tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. Specifically, we study energy matching in the random $p$-spin model of spin-glass theory. Using perturbation theory and exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field “trapped” phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field “excited” phase, in which the field excites the system into high-energy states, effectively forgetting the initial energy; and (3) the intermediate “tunneling” phase, in which the system succeeds at energy matching. The rate at which distant states are found in the tunneling phase, although exponentially slow in system size, is exponentially faster than classical search algorithms.

Figure 1

(Top) A one-dimensional example of a rugged energy landscape $U\left(x\right)$. States with energy below the dashed line form disconnected clusters (shaded). A particle (black dot) remains in a cluster until it either surmounts or tunnels through the energy barriers. (Bottom) The dynamical phase diagram of the random energy model ($p\to \infty$ limit). The system tunnels between clusters in the “tunneling” phase (green), remains trapped in a cluster in the “trapped” phase, and is excited out of clusters in the “excited” phase. The trapped, tunneling, and large-$\mathrm{\Gamma }$ excited phases have been confirmed numerically. It is unclear whether the small-$\mathrm{\Gamma }$ excited phase is truly an excited phase or a portion of the tunneling phase in which perturbation theory does not apply.

Figure 2

Important transitions in the classical $p$-spin model. Each box represents the configuration space of $N$ spin-$\frac{1}{2}$'s, and the red areas represent the regions of configuration space that contain states of energy density $\epsilon$. Top: ${\epsilon }_d<\epsilon <0$, middle: ${\epsilon }_s<\epsilon <{\epsilon }_d$, bottom: ${\epsilon }_{\mathrm{GS}}<\epsilon <{\epsilon }_s$.

Figure 3

Transitions in the $p$-spin model exhibited through the FPP, $g(x,\epsilon |\epsilon )$. Compare to Fig. 2. Only $x<\frac{1}{2}$ is shown since (for even $p$) $g(x,\epsilon |\epsilon )$ is symmetric between $x\leftrightarrow 1-x$. For the curves shown, we made the annealed approximation using $p=6$ and $\epsilon =-0.68$ (red), $-0.78$ (purple), $-0.828$ (blue).

Figure 4

The effect of the Schrieffer-Wolff transformation. The left side shows $H$, the right side shows $H_{\mathrm{eff}}$. The top shows the full Hamiltonian, broken into ${\mathcal{P}}_0$ and ${\mathcal{Q}}_0$ subspaces. The transverse-field operator $V$ is broken into a block-diagonal part $V_d$ and a block-off-diagonal part $V_{od}$. The bottom is a schematic of the structure within ${\mathcal{P}}_0$. The superscripts refer to different clusters.

Figure 5

The configuration space (black vertices) for $N=3$. The gold arrows form a directed path from $|\sigma \rangle$ to $|{\sigma }^{\prime }\rangle$. $|{\sigma }^{\prime \prime }\rangle$ is an intermediate state. Distances between configurations are shown on the right.

Figure 6

Timescales for energy matching in the REM, as a function of $\mathrm{\Gamma }$ at the indicated $\epsilon$. Red is ${\tau }_{\mathrm{q}}$, black is ${\tau }_{\mathrm{th}}$. In each panel, the left dashed line is the location of the tunneling transition and the right dashed line is the location of the excitation transition. ${\tau }_{\mathrm{q}}$ is meaningful only in-between the two. The nonanalyticity in ${\tau }_{\mathrm{q}}$ comes from a change in the argmin of Eq. (32).

Figure 7

Quantum dynamics in the REM, starting from a classical state at energy density $\epsilon$. (Top) Average distance relative to the initial configuration $\mathbb{E}\left[\langle \widehat{x}\left(t\right)\rangle \right]\equiv \mathbb{E}[\langle \mathrm{\Psi }\left(t\right)|\widehat{x}|\mathrm{\Psi }\left(t\right)\rangle ]$. Three representative $\mathrm{\Gamma }$ at fixed $\epsilon$ are shown. The dashed line is $x=\frac{1}{2}$. (Bottom) Average classical energy density $\mathbb{E}\left[\langle \widehat{\epsilon }\left(t\right)\rangle \right]\equiv \mathbb{E}\left[\langle \mathrm{\Psi }\left(t\right)|\widehat{\epsilon }|\mathrm{\Psi }\left(t\right)\rangle \right]$. The same $\mathrm{\Gamma }$ and $\epsilon$ as in the top panels are used. The dashed line is the initial energy density $\epsilon$. Statistical error bars are smaller than the linewidths in all panels. The “tunneling phase” label refers to the observed behavior, not the location relative to the perturbatively obtained phase boundaries in Fig. 1 (see the discussion in Sec. 3c).

Figure 8

Quantum dynamics in the REM starting from a high-energy classical state. (Top) Average distance relative to the initial configuration $\mathbb{E}\left[\langle \widehat{x}\left(t\right)\rangle \right]\equiv \mathbb{E}\left[\langle \mathrm{\Psi }\left(t\right)|\widehat{x}|\mathrm{\Psi }\left(t\right)\rangle \right]$. The dashed line is $x=\frac{1}{2}$. (Bottom) Average classical energy density $\mathbb{E}\left[\langle \widehat{\epsilon }\left(t\right)\rangle \right]\equiv \mathbb{E}\left[\langle \mathrm{\Psi }\left(t\right)|\widehat{\epsilon }|\mathrm{\Psi }\left(t\right)\rangle \right]$. The dashed line is the initial energy density $\epsilon$. Statistical error bars are smaller than the linewidths in both panels.

Figure 9

Regions of the $(x,{\epsilon }^{\prime })$ plane in which the FPP is positive (white) and negative (gray), for $p=100$ and $\epsilon =-0.5$ (dashed line). Configurations at distance $x$ have energy densities exclusively in the white region. $x^{**}\left(\epsilon \right)$ is marked, and $x^{*}\left(\epsilon \right)$ is too close to 0 to be visible on this scale. The curve separating white and gray is ${\epsilon }_{-}^{\prime }\left(x\right)$ [Eq. (36)] [the corresponding upper root ${\epsilon }_{+}^{\prime }\left(x\right)$ is barely visible in the top-left corner].