An ecient method to exactly compute the minimum gap for large quantum adiabatic optimizers

Salvatore Mandrà, Gian Giacomo Guerreschi, Alán Aspuru‐GuzikarXiv 2014 · arXiv

TL;DR

Researchers have developed a novel dimensionality reduction method that allows for the exact calculation of energy gaps in adiabatic quantum optimization (AQO) for systems with hundreds of qubits. By identifying hidden structures in the Hamiltonian, they demonstrate that quantum speedups can survive even in the presence of local noise and defects, proving that AQO is more robust than previously thought.

What Problem Does This Paper Address?

The success of Adiabatic Quantum Optimization (AQO) hinges on the "minimum energy gap"—the tiny sliver of space between the ground state and the first excited state. To avoid errors, a quantum computer must run slowly enough to stay in that ground state, and the required time scales inversely with the square of this gap.

The catch? Calculating this gap for large systems is notoriously difficult. Because the Hilbert space grows exponentially ($2^n$ for $n$ qubits), classical computers usually hit a wall at around 30 qubits. While some "tricks" exist to simplify these calculations, they almost always rely on perfect symmetry (like the system looking the same if you swap any two qubits). Real-world quantum hardware is messy and noisy, breaking these symmetries and making the math intractable. We haven't known for sure if the theoretical "quantum speedup" holds up when the system is riddled with local defects.

Methods

The authors propose a general-purpose dimensionality reduction method that doesn't require explicit symmetry.

  1. Hamiltonian Partitioning: They split the total Hamiltonian into two parts: $H_A$, a highly degenerate operator (many states with the same energy), and $H_B$, a sum of a small number ($k$) of rank-1 projectors.
  2. Hidden Block Structure: They prove that the total Hamiltonian has a hidden block-diagonal structure. By changing the basis to focus only on the subspace where the "action" happens, they reduce the problem from a $2^n$-dimensional space to an effective $(M \times K)$-dimensional space.
  3. Polynomial Scaling: If the number of distinct energy levels ($M$) and the number of projectors ($K$) grow only polynomially with the number of qubits, the problem becomes solvable on a standard laptop even for hundreds of qubits.

They applied this to the Grover search problem (finding a needle in a haystack) modified with discrete local noise (random energy shifts on individual qubits).

Datasets

As a theoretical physics paper, it does not use external "big data" sets. Instead, it evaluates the method using several synthetic problem models:

  • The Grover Problem: Both the ideal version and versions with "local noise" (disorder).
  • Tunneling Models: Systems with high-energy barriers surrounding the global minimum.
  • Random Energy Models: Arbitrary M-level energy problems.
  • Multi-solution Grover: Searching for $k$ target entries instead of one.

Key Insights and Ideas

  • Symmetry isn't Mandatory: You don't need a perfectly symmetric system to reduce dimensionality. You just need to find a way to partition the Hamiltonian so that one part is highly degenerate.
  • The "Robustness" Trade-off: The paper compares two types of "drivers" (the part of the Hamiltonian that creates quantum fluctuations). The Grover-style driver is faster in ideal conditions but very fragile—noise quickly kills its speedup. The Standard driver (transverse field) is slower but much more "robust," maintaining a quantum advantage even under significant noise.
  • Graceful Degradation: Quantum speedup isn't an all-or-nothing phenomenon. As noise increases, the speedup diminishes gradually rather than disappearing instantly, suggesting AQO is viable for "noisy intermediate-scale quantum" (NISQ) devices.

Key Results

  • Scale: The authors successfully calculated exact energy gaps for systems up to $n = 400$ qubits, a massive leap from the previous limit of $\sim 30$.
  • Survival of Speedup: They demonstrated that even with random local defects, AQO remains potentially faster than any classical algorithm for the Grover problem, provided an "optimal" annealing schedule is used.
  • Noise Thresholds: They identified a specific noise threshold ($\epsilon \approx 1$) where the target state might no longer be the true ground state. However, by repeating the algorithm (a standard practice), the speedup is retained.
  • Quantitative Scaling: For the noisy Grover problem, they showed the computational time scales as $2^{3n/2 - nh(q^*/n)}$, which is still significantly better than the classical $2^n$ scaling.

Limitations and Future Work

  • Manual Inspection Required: Currently, there is no "automatic" algorithm to find the best way to split a random Hamiltonian into $H_A$ and $H_B$. A researcher has to inspect the problem to find the right partition.
  • Static Noise: The model assumes the noise is "frozen" during a single run (static disorder). It doesn't account for noise that fluctuates rapidly during the adiabatic evolution (dynamical noise).
  • Beyond Grover: While the method is general, the most dramatic results were shown for Grover-like landscapes. Future work could explore how this reduction applies to more complex, "rugged" optimization landscapes like those found in protein folding or financial modeling.

Summary updated

Abstract

Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. Its success depends on our ability to confine the actual state close to the instantaneous ground state of the time dependent Hamiltonian: This condition is achieved when the duration of the adiabatic evolution is proportional to the inverse of the square of the minimum energy gap encountered in the dynamics. Despite many theoretical and numerical advances, the calculation of the minimum gap is strongly limited by the exponential scaling of the classical resources required to represent large quantum systems. In this paper, we propose and implement a method to exactly compute the energy spectrum of large quantum systems and that requires, under certain, but quite general conditions, only a polynomial amount of classical resources. Numerical results for quantum systems up to n = 400 qubits are provided.
BibTeX
@misc{mandra2014ecient,
  author = {Salvatore Mandrà and Gian Giacomo Guerreschi and Alán Aspuru‐Guzik},
  title = {{An ecient method to exactly compute the minimum gap for large quantum adiabatic optimizers}},
  year = {2014},
  eprint = {1407.8183},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.8183},
}

Loading related content...

Figure