Quantum energy gaps and first-order mean-field-like transitions

Thomas Jörg, Florent Krzakala, Jorge Kurchan, Anthony C. Maggs, J. Pujos

Introduction

Quantum annealing (QA) is often touted for its potential to outperform classical optimization by leveraging quantum tunneling to escape local minima. However, recent theoretical work suggests a fundamental limitation: for a broad class of "mean-field-like" optimization problems, QA encounters first-order phase transitions where the minimum energy gap closes exponentially with system size. This phenomenon imposes a severe "speed limit" on the annealing process, potentially negating any quantum advantage.

Methodology

The study utilizes the ferromagnetic $p$-spin model as a representative "mean-field" system. By adjusting the parameter $p$, the researchers can control the nature of the phase transition. To analyze the system's behavior, they employ:

  • Suzuki-Trotter Mapping: Mapping the quantum problem to a higher-dimensional classical statistical mechanics problem.
  • Symmetry-Reduced Exact Diagonalization: Exploiting total angular momentum conservation to simulate systems up to $N=150$ spins.
  • Instantonic Approach: A semi-classical method to analytically predict the exponential decay of the energy gap.
The minimum energy gap $\Delta_{min}$ as a function of the transverse field $\Gamma$ for $p=3$. The gap reaches its minimum at the critical point, becoming sharper as system size $N$ increases.

Key Insights: The Barrier to Tunneling

A critical finding is that first-order transitions involve competing states that are widely separated in configuration space. While quantum tunneling is effective for high but narrow barriers, it is significantly less effective for the "wide" barriers characteristic of these transitions. In the limit of large $p$, the model converges to the Grover search problem, which has a known lower bound on complexity, providing a rigorous baseline for QA's performance limits.

Results: Exponential Gap Closure

The primary result is the confirmation that the minimum energy gap $\Delta_{min}$ scales as $e^{-\alpha N}$. This exponential closure necessitates an exponentially increasing annealing time to maintain adiabaticity, effectively rendering QA no better than classical search for these hard problems.

Scaling of the normalized minimum energy gap $\Delta_{min}/N$ with system size $N$. The linear relationship on this log-linear plot confirms the exponential decay across various values of $p$.

Numerical simulations show a precise linear relationship for $\Delta_{min}/N$ vs $N$ on a log-linear scale, validating the theoretical predictions. Furthermore, analytical estimates using a "soft instanton" approach were found to be in excellent agreement with these numerical results, proving that the theoretical framework accurately captures the physics of the gap closure.

Conclusion and Future Directions

While these results present a sobering outlook for QA in mean-field-like problems, the authors note that finite-dimensional systems might behave differently due to nucleation processes. Future research will focus on "dilute" systems using the quantum cavity method to better understand how these limitations apply to sparse, real-world optimization problems like 3-SAT.

Summary updated

BibTeX
@misc{jorg2009quantum,
  author = {Thomas Jörg and Florent Krzakala and Jorge Kurchan and Anthony C. Maggs and J. Pujos},
  title = {{Quantum energy gaps and first-order mean-field-like transitions}},
  year = {2009},
  eprint = {0912.4865},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0912.4865},
}

Loading related content...

Figure