Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike)

Technical Summary: Log-concavity and Tunneling in Adiabatic Quantum Optimization for Convex Functions (with a Spike)

Problem Statement
Adiabatic Quantum Optimization (AQO) aims to find the global minimum of a cost function $V: \{0, 1\}^n \to \mathbb{R}$ by evolving a quantum system from an easily preparable initial Hamiltonian to a target Hamiltonian $H(1) = V$. The efficiency of this process depends on the spectral gap $\Delta$ of the interpolating Hamiltonian $H(s) = -(1-s)\sum X_i + sV$. If $\Delta$ remains inverse-polynomial in $n$, the adiabatic theorem guarantees efficient preparation of the ground state.

A significant challenge arises when $V$ contains a "spike"—a localized perturbation that creates local minima, potentially trapping classical algorithms like simulated annealing. Previous rigorous analyses of this phenomenon, such as the "Hamming weight with a spike" (HWS) problem, have relied on the specific property that the unperturbed linear potential $V(x) = |x|$ yields an exactly solvable Hamiltonian with known binomial ground states. This solvability has limited the understanding of quantum tunneling through spikes to linear potentials, leaving the behavior of AQO for more general convex potentials (e.g., quadratic) largely unexplored.

Methodology
The authors develop a framework based on discrete log-concavity to analyze the ground states of 1-dimensional Schrödinger operators of the form $H = -A + V$, where $A$ is a band-diagonal matrix with log-concave coefficients $a_k$. The methodology proceeds in three stages:

1. Establishing Structural Properties: The paper introduces conditions under which the ground state $\psi$ of such Hamiltonians is log-concave (or ultra-log-concave). Specifically, they define a $\gamma$-relative monotonicity (RM) condition relating the potential $V$ to the coefficients $a_k$. They prove that if $H$ satisfies the RM-condition, its ground state is $\gamma$-log-concave.

   • For the symmetry-reduced AQO Hamiltonian on the hypercube (where $a_k = \sqrt{k(n+1-k)}$), they show that if $V$ is convex, the ground state is ultra-log-concave. This serves as a discrete analogue to the continuous result by Brascamp and Lieb [BL76].
   • Crucially, the framework extends beyond convexity, capturing certain non-convex potentials with local minima (multi-well potentials) provided they satisfy the RM-condition.

2. Spectral Gap Bounds via Hardy Inequalities: Leveraging the established log-concavity, the authors apply discrete Hardy inequalities (following Miclo [Mic99]) to derive lower bounds on the spectral gap. They demonstrate that:

   • Log-concavity implies an inverse-polynomial gap ($\Omega(1/n)$) for hypercube Hamiltonians.
   • Ultra-log-concavity implies a constant gap ($\Omega(1)$) for convex potentials on the hypercube.
     These bounds generalize and, in some cases, improve upon existing results by Jarret and Jordan [JJ14].

3. Perturbative Analysis of Spikes: Using the structural properties of log-concave distributions (specifically unimodality and geometric decay away from the mean), the authors extend Reichardt's [Rei04] perturbative analysis of spike tunneling. They show that for a log-concave ground state, the spectral gap remains open under a spike perturbation $h$ if the spike's height and width satisfy specific bounds relative to the ground state's variance and distance from the mean.

Key Contributions and Results

• Discrete Log-Concavity Framework: The primary theoretical contribution is the proof that ground states of a broad family of discrete Schrödinger operators (including those with convex and certain multi-well potentials) are log-concave or ultra-log-concave. This provides a "handle" on ground states that lack closed-form expressions.
• New Spectral Gap Bounds: The authors derive new lower bounds on the spectral gap for log-concave ground states. For convex symmetric potentials on the hypercube, they recover the constant gap result, but for potentials satisfying the RM-condition (which includes non-convex cases), they establish an $\Omega(1/n)$ gap.
• Extension to Quadratic Potentials: As a concrete proof of concept, the paper applies these tools to the Quadratic Hamming Weight with a Spike (Quadratic HWS) problem.
  • Unlike the linear case, the ground state for a quadratic potential $V(k) = a(k-k_0)^2$ has no known closed-form expression.
  • The authors prove that the quadratic ground state maintains a constant overlap ($\ge 1/2$) with a specific binomial ansatz state.
  • Combining this overlap with log-concavity, they bound the mean and variance of the quadratic ground state throughout the annealing path.
  • Main Result: They demonstrate that AQO solves the Quadratic HWS problem in time $O(n^4)$, provided the spike parameters satisfy the same condition derived by Reichardt for the linear case: $\bar{h} \frac{u-\ell}{\sqrt{\ell}} \in O(1)$. This confirms that the tunneling mechanism persists for quadratic potentials.

Significance and Claims
The paper claims to open the study of quantum tunneling in the more general setting of discrete convex optimization with AQO, moving beyond the restrictive class of exactly solvable linear potentials. By establishing log-concavity as a critical structural property, the authors provide a method to analyze spectral gaps and tunneling efficiency for potentials where exact solutions are elusive.

The work suggests that the robustness of AQO against spikes is not an artifact of the linearity of the Hamming weight function but is a broader phenomenon applicable to convex potentials. The authors modestly note that while their results extend Reichardt's analysis to quadratic potentials, the extension to general convex potentials or non-symmetric potentials remains an open question, particularly regarding the definition of log-concavity in higher dimensions and the behavior of the overlap with binomial ansatz states for shifted minimizers.

The paper does not propose new experimental setups or claim superiority over all classical algorithms; rather, it provides rigorous theoretical bounds showing that AQO outperforms simple simulated annealing (which would require exponential time) for these specific spike problems, while acknowledging that more advanced classical algorithms like simulated quantum annealing might also succeed.