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

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

TL;DR

This paper investigates why quantum annealing, a promising technique for solving complex optimization problems, fails for certain classes of problems exhibiting first-order quantum phase transitions. The authors demonstrate that for these problems, the energy gap between the ground state and the first excited state closes exponentially with system size, rendering quantum annealing impractically slow. They analyze this phenomenon using exactly solvable models, including a connection to the Grover search problem, and develop an instantonic approach to precisely quantify the gap closure.

What Problem Does This Paper Address?

Many challenging computational problems, particularly in optimization and machine learning, can be framed as finding the minimum of a complex energy landscape. Quantum annealing offers a potential solution by leveraging quantum fluctuations (tunneling) to escape local minima and find the global minimum, analogous to how thermal annealing uses heat. The core question this paper addresses is: under what conditions does quantum annealing fail to provide a significant speedup over classical algorithms? Specifically, the authors focus on problems that exhibit first-order quantum phase transitions.

In statistical physics, phase transitions describe abrupt changes in a system's properties (like water freezing). A first-order transition is characterized by a discontinuity in certain thermodynamic quantities and, crucially, by the coexistence of distinct phases at the transition point. In the context of quantum annealing, this translates to a situation where the ground state (the desired solution) and the first excited state are fundamentally different configurations in the system's "phase space." The paper argues that when quantum annealing encounters such a transition, the energy gap between these states shrinks dramatically as the system size increases. This exponential shrinking of the gap means that quantum tunneling becomes exponentially inefficient, preventing the annealer from reaching the ground state in a reasonable amount of time.

Methods

The authors employ a multi-pronged approach:

  • Analytical Models: They analyze exactly solvable ferromagnetic p-spin models. These models are chosen because their mean-field treatment is exact, and they exhibit first-order quantum phase transitions. A key finding is that in a specific limit (p → ∞), these models reduce to the well-known Grover search problem, establishing a direct link between difficult optimization problems and the failure of quantum annealing.
  • Statistical Physics Techniques: Standard tools of statistical physics are used to solve the thermodynamics of these models.
  • Landauer-Zener Theory: This theory of level crossings is invoked to explain why quantum tunneling becomes inefficient across an avoided crossing, which is characteristic of first-order transitions. The time required to remain adiabatic is inversely proportional to the energy gap.
  • Instanton Approach: To precisely quantify the exponential closure of the gap, the authors use an "instanton" approach. This technique, borrowed from quantum field theory, involves finding "paths" in the system's configuration space that minimize the action and describe the tunneling process. By calculating the "cost" of these instantonic paths, they can predict the exponent in the exponential decay of the energy gap.
  • Numerical Diagonalization: For finite p, they use numerical diagonalization (specifically, Lanczos methods) to compute the energy gap for systems up to a certain size. This provides empirical validation for their analytical predictions.

Datasets

Not discussed in the paper. The paper focuses on theoretical models and numerical simulations of these models, rather than real-world datasets.

Key Insights and Ideas

  • First-Order Transitions are the Bottleneck: The paper strongly suggests that first-order quantum phase transitions are the primary reason quantum annealing fails for certain hard optimization problems. It's not just complexity, but a specific type of complexity.
  • Exponential Gap Closure is Generic: For mean-field models exhibiting first-order transitions, the energy gap closes exponentially with system size. This is a generic feature, not an artifact of a peculiar model.
  • Grover Problem Connection: The reduction of the p → ∞ p-spin model to the Grover problem is a significant insight. It implies that problems for which quantum computers are known to offer an exponential speedup (like Grover's search) can, in their mean-field formulation, exhibit the very exponential gap closure that hinders quantum annealing. This highlights a subtle but crucial distinction between quantum algorithms and quantum annealing.
  • Instanton as a Predictive Tool: The instantonic approach provides a powerful analytical tool to predict the precise rate of gap closure, offering a way to understand why and how fast quantum annealing will fail.

Key Results

  • Analytical Prediction of Gap Closure: The authors analytically compute the coefficient in the exponential closure of the energy gap, showing it follows the form $\Delta \propto N^{2-\alpha_{Gap}}e^{-N\alpha_{Gap}}$ (where $\alpha_{Gap}$ is a constant dependent on $p$).
  • Numerical Confirmation: Numerical simulations of the p-spin model confirm the exponential decay of the minimum energy gap with system size for various values of p.
  • Failure of Quantum Annealing: The paper concludes that for problems exhibiting these first-order transitions, quantum annealing is likely to be an exponentially slow algorithm, offering no practical advantage over classical methods for the hardest instances.

Limitations and Future Work

  • Mean-Field Models: The analysis is primarily based on mean-field models, which are often simplifications of real-world problems. The authors acknowledge that in finite dimensions, nucleation effects might play a role, but argue that optimization problems are often not finite-dimensional generically.
  • Generalization to Dilute Systems: The authors suggest that extending their instanton approach to dilute mean-field systems and random optimization problems would be an interesting future direction. This would involve using quantum cavity methods.
  • Practical Implications: While the paper clearly outlines the theoretical limitations, further work could explore specific classes of optimization problems where these first-order transitions are known to occur and quantify the expected performance of quantum annealing on them.

Summary updated

Abstract

We study first-order quantum phase transitions in models where the mean-field traitment is exact, and the exponentially fast closure of the energy gap with the system size at the transition. We consider exactly solvable ferromagnetic models, and show that they reduce to the Grover problem in a particular limit. We compute the coefficient in the exponential closure of the gap using an instantonic approach, and discuss the (dire) consequences for quantum annealing.
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