PaperlayerView exact revision on arXiv

Source-linked AI summary

Weaker Assumptions for the Short Path Optimization Algorithm

M. B. Hastings

arXiv:1807.03758v1quant-ph

TL;DR

The short path algorithm previously relied on a unique ground state and conditions on low-energy-state density. This paper keeps the algorithm but revises its analysis, proving a slight density-free speedup for certain D=2 objective values while treating larger random-instance gains heuristically.

  • Problem

    The short path algorithm’s prior speedup results assumed a unique ground state and conditions on the density of low-energy states.

    Source: §I · p. 1

  • Method

    The paper retains the short path algorithm and uses a more careful analysis, including a modification of Brillouin-Wigner perturbation theory, to handle degenerate ground states.

    Source: A. Problem Statement and Summary of… · p. 2

  • Results

    The analysis removes the unique-ground-state requirement for arbitrary MAX-D-LIN-2 problems, and certain D=2 objective values have a slight unconditional super-Grover speedup.

    Source: §I · p. 1, A. Problem Statement and Summary of… · p. 2

  • Takeaways & Limitations

    Density-of-states assumptions can be dropped for the stated D=2 cases, while larger speedups for random models remain an expectation rather than a proved result.

    Source: A. Problem Statement and Summary of… · p. 2

Abstract

from arXiv · show

The short path algorithm gives a super-Grover speedup for various optimization problems under the assumption of a unique ground state and under an assumption on the density of low-energy states. Here, we remove the assumption of a unique ground state; this uses the same algorithm but a slightly different analysis and holds for arbitrary MAX-$D$-LIN-$2$ problems. Then, specializing to the case $D=2$, we show that for certain values of the objective function we can always achieve a super-Grover speedup (albeit a very slight one) without any assumptions on the density of states. Finally, for random instances, we give a heuristic treatment suggesting a more significant improvement.

I. INTRODUCTION

The paper broadens the short path algorithm’s analysis beyond unique ground states and shows that density-of-states promises can be removed for certain D=2 objective values. It also explains the algorithm’s overlap mechanism and gives only heuristic arguments for larger speedups on random instances.

A. Algorithm Review

  • Starting from the X-polarized state, the algorithm phase-estimates a perturbed Hamiltonian whose ground state has squared overlap with an HZ ground state significantly above 2^-N.The perturbation is intended to be small, so the perturbed ground state is close to a ground state of HZ.Source: §I · p. 1

I. INTRODUCTION

  • Short-path speedup exploits wavefunction tails that can be delocalized in the ℓ1 norm even when the squared amplitudes are localized in the ℓ2 norm.The Hamiltonian’s same-sign ground-state coefficients connect a large ℓ1 norm to overlap with the X-polarized state.Source: §I · p. 1

A. Problem Statement and Summary of Results

  • The same short path algorithm applies with degenerate ground states after a more careful analysis using a modification of Brillouin-Wigner perturbation theory.This removes the non-degeneracy requirement, with slight changes to subleading speedup terms.Source: A. Problem Statement and Summary of… · p. 2
  • For D=2, certain objective values admit a slight unconditional super-Grover speedup without density-of-states assumptions.The paper expects larger speedups for random models, but treats that case heuristically.Source: §I · p. 1, A. Problem Statement and Summary of… · p. 2

II. DEGENERATE GROUND STATES

  • For even K, the analysis can restrict Hs to a computational-basis parity block containing a ground state, where its ground state is unique.The full Hamiltonian may be reducible and have a non-unique ground state for even K.Source: A. Algorithm Review · pp. 2–3

B. Results

  • The theorem’s alternative to an algorithmic speedup is a large number of low-energy states, which a density-of-states assumption rules out.The paper describes this as the second possibility in its main theorem.Source: B. Results · p. 3

C. Modified Brillouin-Wigner Perturbation Theory

The analysis extends Brillouin-Wigner perturbation theory to a degenerate ground space and modifies the series to simplify overlap calculations. It constructs eigenvectors through an effective Hamiltonian whose energy parameter is determined self-consistently.

C. Modified Brillouin-Wigner Perturbation Theory

  • The perturbation analysis handles a degenerate ground space and modifies the theory to simplify the treatment of returning paths.The modification removes Q from the series used later to calculate overlaps.Source: C. Modified Brillouin-Wigner… · pp. 5–6
  • The effective Hamiltonian acts within the ground-space projector P, and its eigenvalue parameter ω must be computed self-consistently.The prose identifies G0(ω) as the Moore-Penrose pseudo-inverse on the range of Q.Source: C. Modified Brillouin-Wigner… · p. 5
  • The construction recovers an eigenvector of Hs with eigenvalue ω from an eigenvector of the effective Hamiltonian.The argument is presented as a formal power-series manipulation; convergence is addressed later.Source: C. Modified Brillouin-Wigner… · pp. 5–6
  • The usual series may fail to converge when ω is an eigenvalue of Hs, motivating the modified construction.The text notes that the inverse (ω−Hs)^−1 is then undefined in general.Source: C. Modified Brillouin-Wigner… · p. 6

D. Convergence and Overlap

The section establishes convergence for the chosen perturbation series and relates it to a random walk on computational-basis states. The modified analysis includes returning paths rather than conditioning them away.

D. Convergence and Overlap

  • The series converges for |s| ≤ 1 in the specified choices of ω, H0, V, and ζ.The argument uses the common sign of the series coefficients and Perron-Frobenius reasoning.Source: D. Convergence and Overlap · p. 7
  • The perturbation series is re-expressed as a random walk on computational-basis states, with each step repeating K random spin flips.The same spin may be flipped multiple times within one step.Source: D. Convergence and Overlap · p. 8
  • Unlike the earlier analysis, this walk includes all state sequences without conditioning on the walk not returning to a ground state.The authors identify this as the reason for modifying the Brillouin-Wigner perturbation theory.Source: D. Convergence and Overlap · p. 8
  • For polynomially large BN/(2DK|E0|), only terms with polynomially large t are non-negligible in the series expansion.The passage bounds the series by an exponential expression before drawing this conclusion.Source: D. Convergence and Overlap · p. 9

E. Proof of Theorem 2

The proof first establishes spectral and overlap bounds for a general block-structured Hamiltonian, then applies them to show the properties needed for Theorem 2. The application uses the ground-space projector P and its complement Q.

E. Proof of Theorem 2

  • The block-matrix lemma bounds the n0 lowest eigenvalues above by Emax_A and places the remaining eigenvalues at or above Emin_C.It also gives a lower bound on the smallest eigenvalue through a 2-by-2 matrix comparison.Source: E. Proof of Theorem 2 · pp. 9–10
  • For Theorem 2, the proof takes the diagonal blocks as PH1P and QH1Q and the off-diagonal block as PH1Q.The required block bounds follow under the stated norm assumption and the separation condition on the Q block.Source: E. Proof of Theorem 2 · p. 11
  • The proof uses the lemma to establish spectral separation and a lower bound on overlap with the ground-space projector for vectors in the low-energy subspace.The argument combines the lemma’s spectral bounds with an overlap estimate derived from lemma 1.Source: E. Proof of Theorem 2 · p. 11

F. Proof of Theorem 1

The proof adapts the earlier theorem argument to the generalized Theorem 2 and handles the two cases in Theorem 1. It removes the unique-ground-state requirement, with worse constants in one branch, and adjusts the energy binning for noninteger eigenvalues.

F. Proof of Theorem 1

  • If the stated energy condition holds, Theorem 2 implies item 1 of Theorem 1; otherwise, localization and tight log-Sobolev inequalities establish item 2.The latter branch requires three minor modifications to the earlier proof.Source: F. Proof of Theorem 1 · p. 12
  • The localization argument removes the unique-ground-state assumption at the cost of worse constants.The replacement lemma supplies an eigenvector with energy at most E0 + 1/2 and expectation of B(X/N)^K at least 1/4.Source: F. Proof of Theorem 1 · p. 12
  • Allowing even K can yield negative X expectation, which the proof corrects by applying Z1Z2…ZN to reverse its sign.This unitary commutes with Hs.Source: F. Proof of Theorem 1 · p. 12
  • For noninteger eigenvalues, W(E) counts eigenvalues in [E, E + 1) rather than only those exactly at energy E.The interval definition is used for binning in the entropy analysis.Source: F. Proof of Theorem 1 · p. 12

III. ARBITRARY D = 2 MODELS

For arbitrary D = 2 models with weights in {−1, 0, +1}, the section analyzes when the short path algorithm can obtain a speedup without a density-of-states promise. Theorem 3 gives parameter ranges in which either the algorithm finds a ground state in expected time or there are exponentially many ground states.

III. ARBITRARY D = 2 MODELS

  • The condition E_Q0,1 < E0 + 1/2 implies that there are many computational-basis states with energy close to the ground state; the section analyzes how it can hold.It begins with a toy model showing one way this can occur.Source: §III · p. 12
  • For |E0| ≥ cN^α with α ∈ (11/7, 2], Theorem 3 gives choices of K and b for which either the short path algorithm finds a ground state or log(n0) = Ω(N).In the latter case, Grover search finds a ground state.Source: §III · p. 12
  • For |E0| ≥ cN^α with α ∈ (10/7, 11/7], Theorem 3 likewise gives choices of K and b with one of the two stated outcomes.The alternatives are short-path ground-state finding or log(n0) = Ω(N), in which case Grover search applies.Source: §III · pp. 12–13

A. Toy Model

The toy model illustrates how many nearly flippable spins can challenge the short path analysis. A low-energy state can be formed from a configuration that is nearly optimal on one subset and polarized in the other.

A. Toy Model

  • The toy model generalizes the adiabatic-algorithm issue in which a near-ground configuration has flippable spins that lower its energy under a transverse field.Here the problematic configuration has many such spins rather than only a few.Source: A. Toy Model · p. 13
  • A configuration C′ that is close to the ground energy on the first subset can leave the second subset nearly energy-independent, even though no completion on that subset attains E0.The model assumes negligible interactions within the second subset and contrasts C′ with the first-subset configuration C of the unique ground state.Source: A. Toy Model · p. 13
  • Polarizing the second subset in the + direction yields a state of energy close to E0 with expectation B((N − N1)/N)^K.For large K this remains non-negligible only when N1 << N, so the model's difficulty involves many flippable spins.Source: A. Toy Model · p. 13

B. General Results

The general analysis bounds how the assumptions behind the short path result can fail, then chooses parameters to establish Theorem 3 for D = 2 and weights in {−1, 0, +1}. It yields a speedup in the stated energy ranges unless the number of ground states is exponential.

B. General Results

  • The proof first analyzes failure of the condition E_Q0,1 < E0 + 1/2 and decomposes HZ into within-set and cross-set interactions.It uses a product-state approximation and partitions qubits according to their X polarization to bound the contributions.Source: B. General Results · pp. 13–15
  • An extension of a separable-state approximation result for states with tr(ρX) close to N is used to prove Theorem 3 across its stated α range.Without this extension, the proof would be restricted to α ∈ (5/3, 2].Source: B. General Results · p. 14
  • For α ∈ (11/7, 2] and |E0| ≥ cN^α, the parameter choice makes the short path speedup hold unless log(n0) = Ω(N).For α ∈ (10/7, 11/7], the analysis also supplies a parameter range for which the relevant inequality has no solution.Source: B. General Results · p. 17
  • The parameter choice also ensures ∥PB(X/N)^K∥ ≤ 1/4 for sufficiently large N unless log(n0) = Ω(N).The speedup follows for the selected K and b when this condition and the preceding inequality are controlled.Source: B. General Results · p. 17

C. Return to Toy Model

The returned toy model combines a weak antiferromagnetic interaction within one spin set with a cross-set interaction. This construction supports a state with both a large transverse-field term and a large negative cross-set contribution.

C. Return to Toy Model

  • The construction chooses positive Z polarization in S2, giving H22 positive expectation while H12 has negative expectation proportional to δx^3/2.The H12-induced field only slightly polarizes the spins in S2.Source: C. Return to Toy Model · p. 17
  • A weak antiferromagnetic H22 gives a positive energy contribution that balances the negative H12 contribution in the constructed state.With the balancing choice, the energy cannot be lowered below that of the comparison state τ.Source: C. Return to Toy Model · pp. 17–18
  • The toy model has a state with a large expectation of (X/N)^K and a large negative expectation of H12.The cross-set term arises from weakly polarizing spins in S2 under the effective field produced by spins polarized in S1.Source: C. Return to Toy Model · pp. 17–18

D. Classical Algorithms

The section examines whether a classical search exploiting large |F_i| can match the short-path algorithm’s speedup. Its analysis concludes that Grover-amplifying this search is still slower for α < 2.

D. Classical Algorithms

  • The authors suggest that Grover search applied to a classical algorithm might achieve similar performance, but their simple proposed idea does not quite work.They leave open whether a refinement could work.Source: D. Classical Algorithms · p. 18
  • If |E0| ≥ cN^α for any c > 0 and α, some i has F_i = Ω(N^(α−1)).This follows from the bound that some i has |F_i| ≥ 2|E0|/N.Source: D. Classical Algorithms · p. 18
  • The proposed classical search checks all N choices of i, then brute-force searches states with |F_i| ≥ 2E0/N.For a given i, the number of such states depends on the number M of nonzero interactions J_ij; M ≤ N − 1.Source: D. Classical Algorithms · p. 18
  • For α < 2, Grover-amplifying the proposed classical search remains slower than the short-path algorithm, and gives no nontrivial speedup for α ≤ 3/2.The authors note that further speedup might be possible by exploiting that many choices of i must have large |F_i|.Source: D. Classical Algorithms · p. 18

IV. RANDOM MODELS

The paper offers heuristic arguments that random models may yield larger short-path speedups, while its discussion summarizes a weak speedup for arbitrary models and a failure-mode characterization when E0 is large.

IV. RANDOM MODELS

  • The random-model discussion is heuristic; for discrete couplings, the ground-to-first-excited-state gap is automatically 1, while the needed entropy bounds at very small E − E0 remain uncertain.The authors also say the power-law behavior for the ±1 model seems likely but lacks a cited reference.Source: §IV · pp. 18–19
  • For random choices of J_ij, the authors argue heuristically that with high probability the density-of-states condition in item 2 of theorem 1 fails for some K and b, allowing polynomial speedup over Grover search.Their argument assumes log(W(E)) is polynomially bounded in E − E0 and log(n0) = O(N^γ) for some γ < 1.Source: §IV · pp. 18–19
  • For Gaussian D = 2 couplings, log(W(E)) ∼ (E − E0)^(2/3), but it is unclear whether this scaling holds when E − E0 is much smaller than E0.The paper connects this entropy behavior to the heuristic random-model argument.Source: §IV · p. 19
  • For D > 2, distant basins may make the density-of-states condition sufficient but not necessary, potentially allowing it to be checked within a single basin.The authors suggest that this could permit smaller K and larger B.Source: §IV · p. 19

V. DISCUSSION

  • For arbitrary models, the paper derives a very weak speedup; when E0 is large, its precise failure analysis leaves many flippable spins as the only possibility.The authors expect larger speedups for random models.Source: §V · p. 19

Appendix A: Generalized Log-Sobolev Inequality and bounds on ∥P(X/N)K∥

Appendix A develops bounds on powers of X/N using entropy information about quantum states. It also shows why computational-basis entropy alone is insufficient and gives a support-size bound with a tight example.

Appendix A: Generalized Log-Sobolev Inequality and bounds on ∥P(X/N)K∥

  • For states supported on n0 computational basis states, the appendix gives a bound on ⟨ψ|(X/N)^(2K)|ψ⟩ in terms of n0.The main result is stated as Eq. (A11), with a looser version also given.Source: Appendix A · p. 20
  • A bound on ⟨ψ|X|ψ⟩ in terms of computational-basis entropy is tight, with equality for a product state whose single-qubit measurement entropy matches the entropy density.The appendix uses S(comp)(ψ) for the entropy of computational-basis measurement outcomes.Source: Appendix A · p. 20
  • Computational-basis entropy alone cannot give a useful bound on ⟨ψ|(X/N)^(2K)|ψ⟩: a state formed from a basis state and N^(-1/2)ψ+ has entropy O(1) but expectation roughly 1/N.The appendix therefore develops bounds using several entropies and a sequence of states.Source: Appendix A · pp. 19–20
  • When n0 = 1 and K is fixed as N grows, the bound gives ⟨ψ|(X/N)^(2K)|ψ⟩ ≤ O(1/N^K), matching the exact result.This example indicates that the bound is not far from optimal in this case.Source: Appendix A · p. 21
Loading 1807.03758v1…