Reshaping quantum annealing landscapes with diagonal catalysts

Technical Summary: Reshaping Quantum Annealing Landscapes with Diagonal Catalysts

Problem Statement
Quantum annealing (QA) is an optimization algorithm designed to find the ground state of a cost Hamiltonian ($H_P$) representing a Quadratic Unconstrained Binary Optimization (QUBO) problem. However, QA performance is frequently limited by the population becoming trapped in local minima that are far from the global solution in terms of Hamming distance. This issue is exacerbated on hard instances where the energy gap between the ground state and dynamically accessible excited states becomes exponentially small. Consequently, finite-time anneals often operate diabatically, leading to population redistribution across avoided crossings between states localized in distinct basins of the energy landscape. A critical challenge is that low-energy configurations do not necessarily correspond to configurations close to the solution in Hamming distance; distant configurations can "undercut" nearby ones, providing low-energy candidates for competing basins.

Methodology and Theoretical Framework
The authors introduce a mathematical framework linking energy and Hamming distance to design two-body diagonal catalysts. These catalysts are constructed solely from the coupling structure of the problem (signs, magnitudes, and graph topology) without requiring prior knowledge of the solution.

1. Hamming Shell Analysis: The authors define "Hamming shells" ($S_{d, z^\star}$) as sets of configurations at a specific Hamming distance $d$ from a reference ground state $z^\star$. They derive exact formulas for the mean and variance of the energy over these shells for any field-free two-body Ising operator.

   • Theorem 1 establishes that the mean energy of a shell follows a parabolic curve determined by combinatorial factors, while the variance (shell width) depends on the specific coupling matrix.
   • In the bare problem, shell means are correctly ordered, but the broad variance causes shell overlap, allowing distant configurations to have lower energies than closer ones.

2. Catalyst Design ($C$): The goal is to construct a diagonal catalyst $C$ that increases the separation between shell means relative to their within-shell fluctuations, effectively "funneling" the landscape.

   • The ideal catalyst would be proportional to $-z^\star_i z^\star_j$, but this requires knowledge of the unknown ground state.
   • Open-Path Construction: The authors propose estimating the ground-state pattern using self-avoiding paths on the interaction graph. By propagating spin patterns along these paths based on coupling signs ($g(p)_{v_{a+1}} = -\text{sgn}(J_{v_a v_{a+1}}) g(p)_{v_a}$), they generate locally satisfying patterns.
   • The catalyst $C^{(m)}$ is formed by summing contributions from all $m$-edge self-avoiding paths. Each path contributes a weighted rank-one estimate of the ideal coupling structure. The final operator is projected orthogonal to the original couplings and normalized.
   • This construction creates a denser interaction graph than the original problem, penalizing configurations that frustrate stronger bonds and reinforcing those that align with the propagated patterns.

Key Results
The authors benchmarked their method on 200 random 3-regular instances with $n=20$ spins and couplings drawn from $[-1, 1]$. Simulations were performed at sweep times $T = 2, 6, 10$.

• Energy Landscape Reshaping: The catalyst successfully reshapes the static landscape, reducing the overlap between Hamming shells and deepening the energy funnel toward the ground state.
• Probability Redistribution:
  • Energy Space: The catalyst shifts probability mass from intermediate-energy bands toward the ground-state band ($E/E_{GS} \ge 0.95$). At $T=6$, the median top-band mass increased from 0.067 (uncatalyzed) to 0.324, representing a median paired gain of +351%.
  • Hamming Space: The distribution shifts toward the ground-state manifold. At $T=6$, the probability mass at Hamming distance $\delta \le 2$ increased from 0.10 to 0.35 (+239%).
• Robustness and Comparison:
  • The gains persist across different graph connectivities (3-, 4-, and 5-regular graphs) and on the fully connected Sherrington–Kirkpatrick model, though the magnitude of improvement decreases as connectivity increases.
  • The open-path catalyst significantly outperforms a "reinforced-problem" baseline ($C = H_P$), demonstrating that the benefit arises from the specific structural redistribution of couplings rather than merely increasing the overall energy scale.
  • There is a trade-off between the order of the path ($m$) and graph density; moderate orders (e.g., $m=4$ for 3-regular graphs) offer the best balance between resolving local structure and maintaining fidelity to the true ground state ordering.

Significance and Claims
The paper claims to provide a practical method for improving quantum annealing on near-term hardware by utilizing native longitudinal controls (diagonal operators) that are two-local and do not require the complex gadgets needed for non-stoquastic catalysts.

• Solution-Agnostic Design: The catalysts are constructed without knowledge of the solution, relying only on the problem's coupling matrix.
• Static Criteria for Design: The derived shell-moment theorem offers static criteria (funnel depth and shell overlap) to screen candidate catalysts before running dynamic annealing simulations.
• Hardware Compatibility: Being diagonal and two-body, the catalysts preserve the transverse-field structure and are compatible with the connectivity and coupling-range constraints of current annealers.
• Future Directions: The authors suggest the framework can be extended to digital settings (e.g., as a phase separator in QAOA), combined with optimized diabatic protocols, or applied to reverse annealing. They also note that characterizing the scaling with system size and generalizing to field-inclusive cost functions remains an open task.