Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve

The simplest quantum ferromagnet. –

• The Hamiltonian is H = Hz + ΓV, with Hz diagonal in the σz basis, and the analysis focuses on the ferromagnetic p-spin model.The longitudinal magnetization is M(σz), with magnetization per site m = M/N and mT = M_T/N.Source: The simplest quantum ferromagnet. – · p. 2
• For odd p, the classical ground state is uniquely all spins up; for even p, both fully aligned states are ground states.The analysis concentrates on odd p for simplicity.Source: The simplest quantum ferromagnet. – · p. 2
• The p = 2 Curie-Weiss model has a continuous transition, whereas both quantum and thermal transitions are discontinuous for p > 2.The p → ∞ limit is also singled out for study.Source: The simplest quantum ferromagnet. – · p. 2
• In the p → ∞ limit for odd p, m^p tends to ±1 at m = ±1 and to zero otherwise; the paper then specializes to this limit.The indicator function 11(x) is defined as 1 when x is true and 0 otherwise.Source: The simplest quantum ferromagnet. – · p. 2

The classical case: Γ = 0.

• At Γ = 0, only two energy levels are nonzero, E = N and E = −N; the partition sum is Z = 2^N − 2 + 2 cosh βN.Source: The classical case: Γ = 0 · p. 2
• The classical description notes that nucleation is expected to help in finite dimensions.The passage contrasts this with optimization problems, which are not generically finite-dimensional.Source: The classical case: Γ = 0 · p. 2
• At βc = log 2, the classical model has a first-order transition between locally stable ferromagnetic and paramagnetic phases.The ferromagnetic phase consists of the all-up configuration for β > βc; the phases have no spinodal.Source: The classical case: Γ = 0 · p. 2

The extreme quantum case: Γ = ∞.

• At Γ = ∞, the entropy density is the logarithm of a binomial over energies in [−ΓN, ΓN], yielding a perfect quantum paramagnet.For large Γ, the classical part of the Hamiltonian can be neglected, leaving independent spins in a field Γ in the σx basis.Source: The extreme quantum case: Γ = ∞ · p. 2

The general case.

• The phase diagram is set by f = min(fQP, fF), with a first-order transition where the quantum-paramagnetic and ferromagnetic free energies cross.The ferromagnetic phase occurs at low Γ and T; the quantum-paramagnetic free energy applies at larger Γ.Source: The general case · p. 2
• At the transition, the magnetization jumps from 0 to 1.Source: The general case · p. 2
• Rayleigh-Schrödinger perturbation theory about Γ = 0 uses single-spin-flip connections; odd orders vanish, and the finite-order terms can be computed because all excited classical levels have Ek = 0.The unperturbed ground-state energy is −N.Source: The general case · p. 2
• A complementary expansion starts from ΓV; its first-order shift is tiny because the z-basis amplitudes a(l) are of order 2^−N/2.The following correction sums over 2^N − 1 levels; the sum is entropically dominated by Ek = 0 states and contributes negligibly.Source: The general case · p. 3
• For Γ > Γc, the ground-state energy is EGS = −ΓN + o(1), with Γc = 1 + O(1/N).Source: The general case · p. 3

Exponential closure of the gap.

• At Γc = 1 in the large-N limit, the avoided crossing is between paramagnetic and ferromagnetic ground states.The Hamiltonian is rewritten in the σx basis to analyze the gap near the crossing.Source: Exponential closure of the gap · p. 3
• The eigenvalue equation’s interior roots are bracketed by poles separated by 2Γ, while the lowest eigenvalue can split off from this comb as a phase-transition signal.In the small-Γ phase, this brackets almost all eigenvalues near λ = 0.Source: Exponential closure of the gap · p. 3
• The gap closes exponentially fast at the transition, in a mean-field model where difficult instances have only one low-energy configuration among 2^N possibilities.The paper presents this as a first-order quantum transition and relates the p → ∞ model to Grover search.Source: Exponential closure of the gap · p. 3
• In the p → ∞ limit, the model is the Grover problem, whose best algorithm is exponential even when the evolution rate is adjusted to keep the process adiabatic.With that adjustment, the running time can scale as τ ∝ Δ^−1, which remains exponential.Source: Exponential closure of the gap · p. 3

• The study calculates the static phase diagram, then compares numerical gap closure with an instantonic calculation.Source: Behavior for general p. – · p. 3

Phase diagram.

• The static approximation removes the time indices after a numerical check, and the resulting minima crossing gives a first-order transition.Source: Phase diagram · p. 4
• The low-lying-state description is crude: it misses the unique first excited state and requires exponentially small free-energy corrections to resolve the gap.Source: Phase diagram · p. 4
• For p → ∞, the free energy is −1 at m = 1 and −β log 2 cosh(βΓ) otherwise.Source: Phase diagram · p. 4

Numerical methods.

• Because total angular momentum commutes with H, the transition can be studied in a subspace of dimension N + 1.The full-matrix Lanczos method extracts extremal eigenvalues for N ≤ 21; the reduced tridiagonal matrix enables studies near N ∼ 100.Source: Numerical methods · pp. 4–5
• For all p ≥ 3, the minimum gap decays exponentially with N.The reported form is ∆min ∝ N2−Nα.Source: Numerical methods · p. 5
• The gap-closing region around Γc narrows as N increases, so scans of Γ can miss it.Source: Numerical methods · p. 5, Figure 2 · p. 5

The Instantonic approach.

• At the transition, an instantonic path spends time in the ferromagnetic state before jumping to the paramagnetic state.Source: The Instantonic approach · p. 5
• Exact diagonalization shows that the minimum gap closes exponentially with N for the displayed p values.Source: Figure 3 · p. 5
• Summing paths with an even number of jumps produces an effective two-level system.The factor β^k/k! counts paths with k jumps.Source: The Instantonic approach · p. 5
• The instanton cost G sets the exponential gap, ∆ ∝ e−NG.Source: The Instantonic approach · p. 5

Computing the Instanton.

• The sharp-wall ansatz gives the previously obtained ∆≈N2−N/2 result as p→∞, but only a crude lower bound on the exponent for finite p.The sharp-wall estimate is an upper bound on the true value, as specified for αGap sharp in Table 1.Source: Computing the Instanton · pp. 5–6, Table 1 · p. 6
• The soft tanh instanton’s predicted gap-decay coefficient is indistinguishable from exact diagonalization, as reported in Table 1.The table compares the exact-diagonalization coefficient with the soft-instanton estimate.Source: Computing the Instanton · p. 6, Table 1 · p. 6
• A tanh-shaped magnetization path is optimized by varying its width to minimize the instanton free-energy estimate, from which the gap is deduced.The cost is computed by integrating Eq. (16).Source: Computing the Instanton · p. 6

Conclusions. –

• Even systems with trivial energy landscapes can exhibit quantum-annealing failure, without requiring more complex phenomena to explain it.The paper gives the p = 3 ferromagnet as an example with a first-order transition and exponentially closing gap.Source: Conclusions. – · p. 6
• The p = 3 ferromagnet’s first-order transition and exponentially closing gap make quantum annealing’s prospects pessimistic in this example.The conclusion describes this as a scenario that is very pessimistic for the algorithm’s success.Source: Conclusions. – · p. 6
• The p→∞ limit of the ferromagnetic model is related to the Grover problem, which the paper connects to the difficulty of first-order transitions.The conclusion says these transitions carry the signature of the most difficult problems.Source: Conclusions. – · p. 6
• The paper’s complete analytical and numerical treatment covers its presented models; extensions to dilute mean-field systems and random optimization problems are proposed as future work.The proposed extensions would use the quantum cavity approach.Source: Conclusions. – · p. 6