Energy gap of quantum spin glasses: a projection quantum Monte Carlo study

Using a newly proposed unbiased energy-gap estimator in projection quantum Monte Carlo simulations, this study reveals that while the minimum energy gap in two-dimensional Edwards-Anderson spin glasses exhibits unfavorable super-algebraic scaling with infinite variance, the all-to-all Sherrington-Kirkpatrick model maintains a finite-variance distribution with a slow power-law scaling ($\Delta \propto N^{-1/3}$), suggesting greater potential for quantum annealing efficiency in densely connected optimization problems.

The Gist

Imagine you are trying to solve a massive, incredibly complex puzzle. You have a magical robot (a Quantum Computer) that can try to solve it by slowly changing its shape, sliding from a "messy" state to a "solved" state. This process is called Quantum Annealing.

However, there's a catch. As the robot changes shape, it has to pass through a narrow, dark tunnel. The width of this tunnel is determined by something called the Energy Gap.

• Wide Gap: The tunnel is wide and easy to walk through. The robot solves the puzzle quickly.
• Tiny Gap: The tunnel is a hairline crack. If the robot moves even a tiny bit too fast, it gets stuck or falls into the wrong solution. The time it takes to cross this tunnel grows exponentially, making the problem impossible to solve in a reasonable time.

This paper is a deep dive into how wide (or narrow) these tunnels are for two different types of puzzles, using a super-advanced simulation method called Projection Quantum Monte Carlo (PQMC).

The Two Puzzle Types

The researchers looked at two famous "puzzle models" used to test quantum computers:

1. The 2D-EA Model (The Neighborhood Grid): Imagine a puzzle where every piece only talks to its four immediate neighbors (up, down, left, right) on a flat grid. This is like a standard neighborhood.
2. The SK Model (The All-Hands Meeting): Imagine a puzzle where every piece talks to every other piece simultaneously. It's like a chaotic room where everyone is shouting to everyone else at once. This represents "dense connectivity."

The Big Discovery: The "Fat Tail" Problem

The researchers used a new, super-accurate way to measure the size of the energy gap (the tunnel width). They didn't just measure the average gap; they looked at the distribution of gaps across thousands of different puzzle variations.

1. The Neighborhood Grid (2D-EA): A Dangerous Gamble

For the grid model, they found something scary. As the puzzle gets bigger, the distribution of gap sizes develops a "Fat Tail."

• The Analogy: Imagine you are betting on how long it will take to cross a bridge. Usually, most bridges take about 10 minutes. But in this model, while most bridges are fine, there is a tiny, terrifying chance that a bridge is so narrow it takes forever to cross.
• The Result: As the puzzle gets bigger, these "forever" bridges become more likely. The math shows that the variance (the spread of possibilities) becomes infinite. This means that for a large grid puzzle, you might get incredibly unlucky and hit a gap so small that the quantum computer effectively freezes. It's a "super-algebraic" slowdown, meaning the time required explodes faster than you'd expect.

Key Takeaway: If your optimization problem is like a sparse grid (like a standard map), quantum annealing might struggle badly as the problem gets huge.

2. The All-Hands Meeting (SK Model): A Surprising Win

For the model where everyone talks to everyone (dense connectivity), the story is very different.

• The Analogy: Here, the "Fat Tail" disappears. The bridges are still narrow, but they are predictably narrow. There are no "forever" bridges.
• The Result: The gap shrinks as the puzzle gets bigger, but it does so in a very gentle, predictable way (following a power law). It's like a slow, steady decline rather than a cliff.
• The Math: They found the gap shrinks roughly as $1/N^{1/3}$. While this still gets smaller, it's a "favorable" rate. It suggests that for problems with dense connections (like complex financial portfolios or logistics networks where every item affects every other item), quantum annealing has a much better chance of success.

The Magic Tool: The "Unbiased" Estimator

How did they find this out? Previous methods were like trying to guess the depth of a well by throwing a stone and listening for the splash, but the wind (the "guiding wave function") kept blowing the stone off course.

The authors developed a new Unbiased Estimator.

• The Analogy: Imagine you are measuring the depth of a well in a storm. Old methods required you to guess the wind direction to correct your measurement. If you guessed wrong, your measurement was wrong.
• The New Method: Their new tool is like a sensor that measures the depth regardless of the wind. It doesn't matter what guess you start with; the final answer is always the true depth. This allowed them to get high-fidelity results for systems with over 100 spins (pieces), which was previously impossible.

Why This Matters

This paper is a "reality check" for the future of quantum computing:

1. Don't expect a magic bullet for everything: If your problem is structured like a simple grid (sparse), quantum annealing might hit a wall where the "tunnel" becomes impossibly thin.
2. Hope for complex problems: If your problem is highly interconnected (dense), like many real-world business or physics problems, the "tunnel" stays manageable. Quantum annealers might actually be very efficient for these specific types of dense problems.

In a nutshell: The researchers built a better ruler to measure the difficulty of quantum puzzles. They found that "neighborly" puzzles get exponentially harder to solve as they grow, but "social" (dense) puzzles get harder at a much slower, more manageable pace. This gives us a clear roadmap for where quantum computers will shine and where they might struggle.

Technical Summary

1. Problem Statement

The efficiency of Quantum Annealing (QA) for solving combinatorial optimization problems is fundamentally limited by the minimum energy gap ($\Delta$) between the ground state and the first excited state during the annealing path. According to the adiabatic theorem, the time required to avoid non-adiabatic transitions scales as $1/\Delta^2$.

• The Challenge: In spin-glass models, $\Delta$ is expected to vanish rapidly as the system size $N$ increases. However, previous literature has reported conflicting scaling behaviors (e.g., polynomial vs. super-algebraic/exponential) due to computational difficulties in estimating gaps for large $N$ and the sensitivity to disorder realizations.
• The Gap in Knowledge: Previous large-scale studies on the 2D Edwards-Anderson (2D-EA) model were restricted to binary couplings ($J_{ij} = \pm J$) and finite-temperature Path-Integral Monte Carlo (PIMC). It was unclear if the reported "super-algebraic" scaling (indicating poor QA efficiency) was a universal feature or an artifact of binary couplings. Furthermore, the scaling for models with dense connectivity (like the Sherrington-Kirkpatrick model) and continuous Gaussian couplings remained less characterized.

2. Methodology

The authors employed a combination of advanced numerical techniques to probe the energy gap scaling for system sizes up to $N \approx 125$.

• Models Studied:

  1. 2D Edwards-Anderson (2D-EA): Spins on a square lattice with nearest-neighbor interactions.
  2. Sherrington-Kirkpatrick (SK): All-to-all connectivity (mean-field).
  • Both models utilized Gaussian disorder ($J_{ij} \sim \mathcal{N}(0, J^2)$) and a uniform transverse field $\Gamma$.

• Primary Algorithm: Continuous-Time Projection Quantum Monte Carlo (PQMC)

  • Unbiased Gap Estimator: The authors developed and utilized a novel pure estimator for the energy gap. Unlike standard estimators that depend on the guiding wave function ($\psi_g$), this estimator is derived from the long-time exponential decay of imaginary-time correlation functions of odd operators (operators that anti-commute with the parity operator $\hat{P}$).
  • Guiding Wave Function: To improve statistics and eliminate population control bias, they used Neural Quantum States (NQS) in the form of Restricted Boltzmann Machines (RBMs), optimized via variational energy minimization using the NetKet library.
  • Symmetry Handling: The Hamiltonian commutes with the parity operator. The ground state is even. The smallest gap is typically the transition to the first odd excited state ($\Delta_o = E_{o,0} - E_0$). The PQMC method specifically targets this gap using odd operators (e.g., single-spin $\sigma^z_i$).

• Complementary Methods:

  • Exact Eigenvalue Solvers (Lanczos): Used for smaller systems ($N \lesssim 30$) to benchmark the PQMC results and validate the unbiased nature of the estimator.
  • Statistical Analysis: The distribution of the inverse gap $\eta = 1/\Delta$ was analyzed across thousands of disorder realizations using the Hill estimator to determine the tail index $\alpha$ of the probability distribution.

3. Key Contributions

1. Development of an Unbiased PQMC Gap Estimator: The paper demonstrates that the gap estimator is independent of the choice of the guiding wave function, ensuring high-fidelity results for systems where exact diagonalization is impossible ($N > 30$).
2. Extension to Continuous Couplings: The study moves beyond binary couplings to investigate Gaussian disorder, testing the universality of previous findings.
3. Comparative Scaling Analysis: A direct comparison between the sparse 2D-EA model and the dense SK model to understand how connectivity affects the energy gap scaling.

4. Key Results

A. The 2D-EA Model (Sparse Connectivity)

• Distribution Tail: The distribution of the inverse gap $\eta$ develops a fat tail with infinite variance as $N$ increases.
• Tail Index ($\alpha$): The Hill estimator shows the tail index $\alpha$ decreases with system size, dropping below $\alpha = 1$ for $L \approx 12$.
  • $\alpha < 1$ implies the disorder-averaged inverse gap $[\eta]$ diverges.
  • This confirms that the super-algebraic scaling of the gap (observed previously for binary couplings) persists for Gaussian couplings.
• Implication: The presence of rare disorder instances with exponentially small gaps makes the average annealing time prohibitively long, suggesting a fundamental limitation for QA on 2D sparse graphs.

B. The Sherrington-Kirkpatrick (SK) Model (Dense Connectivity)

• Distribution Tail: In contrast to 2D-EA, the SK model retains a finite-variance distribution for $\eta$. The tail index $\alpha$ remains well above 2 for all studied sizes.
• Scaling Law: The disorder-averaged gap follows a favorable power-law scaling:
  $$\Delta \propto N^{-\theta}$$
  where the exponent is found to be $\theta \approx 0.32(1)$ (close to $1/3$).
• Symmetry: Both the odd (symmetry-breaking) and even (symmetry-restricted) gaps exhibit similar power-law scaling at the critical point, indicating that dense connectivity suppresses the formation of the "bad" rare instances seen in 2D models.

C. Validation

• Benchmarks against exact diagonalization (Jordan-Wigner for 1D chains and Lanczos for 2D-EA) confirmed that the PQMC results are unbiased and independent of the number of hidden neurons in the RBM guiding function.

5. Significance and Outlook

• Universal Feature of 2D Spin Glasses: The study establishes that the unfavorable scaling of the energy gap in 2D spin glasses is a universal feature, persisting regardless of whether the couplings are binary or continuous. This suggests that standard QA may struggle with optimization problems mapped to 2D sparse graphs (e.g., planar Ising formulations).
• Promise for Dense Connectivity: The finding that the SK model (dense connectivity) exhibits a polynomial gap scaling with a small exponent ($\sim N^{-1/3}$) offers a promising outlook for quantum annealers. It suggests that optimization problems with dense connectivity (or those that can be mapped to such structures) may be solvable efficiently via quantum annealing, avoiding the super-algebraic bottlenecks of sparse models.
• Methodological Impact: The proposed unbiased PQMC estimator provides a robust tool for studying spectral properties in many-body quantum systems, applicable to fields ranging from frustrated magnetism to quantum chemistry.

Conclusion: The paper resolves conflicting reports on gap scaling by distinguishing between sparse and dense connectivity. It concludes that while 2D spin glasses pose a severe challenge for quantum annealing due to fat-tailed gap distributions, fully connected (mean-field) spin glasses offer a viable path for efficient quantum optimization.