PaperlayerView exact revision on arXiv

Source-linked AI summary

Obstacles to State Preparation and Variational Optimization from Symmetry Protection

Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang

arXiv:1910.08980v1quant-phcond-mat.str-el

TL;DR

The paper asks whether the NLTS property can extend to all low-energy states under an on-site Z2 symmetry. It proves an NLTS result in that setting and applies the symmetry-based bound to show a constant-level QAOA limitation for MaxCut. The stated scope matters: the same Hamiltonian family does not exhibit NLTS without the symmetry.

  • Problem

    The paper investigates whether local Hamiltonians can have only non-trivial low-energy states, as posed by the NLTS conjecture.

    Source: p. 1

  • Method

    The authors prove an NLTS result for Z2-symmetric local Hamiltonians by considering Z2-symmetric shallow circuits and product states.

    Source: p. 2

  • Results

    Constant-level QAOA is inferior to the Goemans-Williamson algorithm for the stated MaxCut instances, and a family of Ising Hamiltonians has level-1 RQAOA ratio 1 while level-p QAOA is bounded by p/(p + 1).

    Source: pp. 3–4

  • Takeaways & Limitations

    The NLTS property in this Hamiltonian family depends essentially on the Z2 symmetry, while the same Hamiltonians have product ground states without it.

    Source: p. 2

    The NLTS result does not hold for this family without Z2 symmetry.

    Source: p. 2

Abstract

from arXiv · show

Local Hamiltonians with topological quantum order exhibit highly entangled ground states that cannot be prepared by shallow quantum circuits. Here, we show that this property may extend to all low-energy states in the presence of an on-site $\mathbb{Z}_2$ symmetry. This proves a version of the No Low-Energy Trivial States (NLTS) conjecture for a family of local Hamiltonians with symmetry protected topological order. A surprising consequence of this result is that the Goemans-Williamson algorithm outperforms the Quantum Approximate Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant level. We argue that the locality and symmetry of QAOA severely limits its performance. To overcome these limitations, we propose a non-local version of QAOA, and give numerical evidence that it significantly outperforms standard QAOA for frustrated Ising models on random 3-regular graphs.

Appendix A: Proof of Corollary 1

Appendix A proves Corollary 1 by bounding QAOA circuit depth and applying Theorem 1 to bipartite regular expander graphs. It also shows that suitable edge-sign changes preserve expected QAOA approximation ratios.

Appendix A: Proof of Corollary 1

  • A level-p QAOA circuit has depth at most p(D + 1), or pD when the graph is D-regular and bipartite.The proof uses edge coloring to schedule the two-qubit gates.Source: Appendix A · p. 6
  • Flipping the signs of edges crossing a vertex subset leaves the expected QAOA approximation ratio unchanged.The proof relates the Hamiltonians by conjugation with Pauli-X operators on that subset.Source: Appendix A · p. 6
  • For bipartite graphs, the proof uses the sign-change lemma to relate the QAOA instances involved in Corollary 1.The result fragment identifies (D−1)/(2D) and says it is valid for all Ramanujan graphs.Source: Appendix A · pp. 6–7
  • Theorem 1 bounds QAOA performance for graphs with Cheeger constant at least h when n > 4828d.The proof applies this result to the bipartite regular graph family in Corollary 1.Source: Appendix A · pp. 6–7

Appendix B: Optimal variational circuit for the ring of disagrees

Appendix B proves tightness of the stated upper bound for the ring of disagrees when n is a multiple of 2p + 1. It constructs a Z2-symmetric range-p circuit using GHZ states on consecutive blocks.

Appendix B: Optimal variational circuit for the ring of disagrees

  • The appendix establishes tightness of Theorem 2’s upper bound when n is a multiple of 2p + 1.The construction uses a Z2-symmetric range-p circuit and GHZ states on consecutive blocks.Source: Appendix B · pp. 7–8
  • For n = 2p + 1 with integer p, Lemma B.1 states that a Z2-symmetric range-p quantum circuit exists; the cited excerpt does not specify its preparation target.The proof identifies c = p + 1 as the central qubit and discusses CX gates.Source: Appendix B · p. 7
  • In the block construction, ring-of-disagrees terms supported within a GHZ block have expected value 1, while terms crossing block boundaries have expected value 1/2.The circuit’s range-p condition is checked by considering observables on the central qubit and on either side of it.Source: Appendix B · p. 8

Appendix C: Recursive QAOA

Appendix C outlines Recursive QAOA (RQAOA) for general cost functions.

Appendix C: Recursive QAOA

C.1. Variable Elimination

Variable elimination reduces a constrained optimization over n variables to one over n − 1 variables. The reduction preserves the constrained maximum and yields an original-problem solution when a global maximum satisfies the constraint.

C.1. Variable Elimination

  • Under the constraint x_v = σ · x(f\{v}), the cost can be rewritten without dependence on x_v.The resulting objective is represented on a hypergraph with vertex set V′ = V \{v}.Source: §C.1 · p. 9
  • The reduced objective over n − 1 variables has the same maximum as the original cost over assignments satisfying the constraint.A maximum of the reduced objective can be translated back to a constrained assignment of the original variables.Source: §C.1 · pp. 9–10
  • If a global maximum of the original cost satisfies the constraint, the reduced problem yields a solution to the original problem.Source: §C.1 · p. 10

C.2. Correlation rounding

Correlation rounding uses QAOA-estimated term correlations to impose a constraint among variables, eliminate one variable, and reduce the problem. The selected correlation is the one with greatest absolute value.

C.2. Correlation rounding

  • The reduction uses a QAOA state maximizing the Hamiltonian's expected value and computes each interaction's mean value.The passage says these expected values can be efficiently approximated on a quantum computer.Source: §C.2 · p. 10
  • Selecting the term with maximal absolute correlation supplies a sign constraint among its variables, enabling one variable to be eliminated.The chosen sign is sign(M_f), and the eliminated variable is selected from the term's variables.Source: §C.2 · p. 10
  • The elimination routine takes a weighted hypergraph and returns a reduced hypergraph, updated weights, and a map back to assignments.It selects the interaction with greatest absolute mean value before defining the reduced instance.Source: §C.2 · p. 10

C.3. The recursive QAOA (RQAOA) algorithm

RQAOA repeatedly eliminates variables until a chosen size threshold remains, then solves that smaller instance classically. The threshold sets how work is divided between quantum and classical computation.

C.3. The recursive QAOA (RQAOA) algorithm

  • RQAOA iterates variable elimination until the instance reaches the specified threshold n_c.Each recursion step removes one variable from the cost function.Source: §C.3 · p. 10
  • The remaining n_c-variable instance is solved by a classical algorithm, so n_c controls the quantum–classical workload split.Brute force is given as one example of the classical solver.Source: §C.3 · p. 10
  • The pseudocode specifies a weighted hypergraph input and returns a variable assignment.The figure is identified as pseudocode for the recursive algorithm.Source: §C.3 · p. 11, Figure 2 · p. 11

C.4. Classical simulability of level-1 RQAOA for Ising models

For Ising models, level-1 RQAOA's simulation uses analytic QAOA expectation formulas, while broader cost functions require approximate correlation estimates. Its measurement strategy differs from QAOA, and its classical simulability depends on circuit depth and cost-function scope.

C.4. Classical simulability of level-1 RQAOA for Ising models

  • The level-1 Ising simulation derives the needed two-qubit QAOA means through analytic expressions for Pauli observables.The derivation treats ZZ and other two-qubit observables, combining intermediate expectation formulas to obtain the general Ising result.Source: §C.4 · pp. 11–12
  • With n_c=O(1), level-1 RQAOA simulation costs O(n^4), independent of circuit depth.Each step costs at most O(n^3), and the simulation may increase circuit depth from O(1) to O(n).Source: §C.4 · p. 11
  • For more general interactions, elimination can increase non-locality, and QAOA term means can be approximated using a Monte Carlo method.The described simulator has polynomial runtime in the number of qubits, cost terms, and inverse error tolerance, with no circuit-depth restriction.Source: §C.4 · p. 13
  • RQAOA replaces QAOA's final n-qubit measurement with successive correlation rounding; level-p RQAOA for p>1 and level-1 RQAOA on general cost functions are not known to be polynomial-time classically simulable.The passage says level-1 RQAOA for Ising-like cost functions can be efficiently simulated classically.Source: §C.4 · p. 13

D.1. QAOA versus Classical Local Algorithms

The section compares QAOA with local classical algorithms on a large family of instances, using graph-local dependence to define the classical competitors. On an exponential family, a 1-local classical algorithm and level-1 RQAOA outperform the stated QAOA bound.

D.1. QAOA versus Classical Local Algorithms

  • For every p ∈ N, a subset S ⊂ {1, −1}^n of 2n/3 instances satisfies QAOA_p(H(J)) ≤ p/(p + 1), and a 1-local uniform classical algorithm outputs energy 1 on every J ∈ S.Source: §D.1 · p. 14
  • The section defines an r-local classical algorithm by limiting each output bit to edge weights within graph distance r, and uniformity uses one local rule across vertices.The uniformity definition relies on vertex-transitive graphs and identifying neighborhoods through graph automorphisms.Source: §D.1 · p. 13
  • The hard family is constructed from sign patterns that define a subset of Ising instances.The proof then establishes the QAOA bound for that subset using QAOA's gauge-transformation invariance.Source: §D.1 · p. 14
  • For the classical comparison, the proof gives a uniform 1-local algorithm whose output has energy 1 on the constructed instances.Its output is specified by a rule applied to neighboring coupling signs.Source: §D.1 · p. 14

D.2. RQAOA on the Ising ring

On an Ising ring with couplings in {+1, −1}, level-1 RQAOA achieves approximation ratio 1. Its variable-elimination proof reduces the ring while preserving coupling parity.

D.2. RQAOA on the Ising ring

  • Level-1 RQAOA achieves approximation ratio 1 on the ring of disagrees and maximizes the cost for any 1D Ising model with couplings ±1.The result is stated for the ring and more generally for 1D Ising models with couplings in {+1, −1}.Source: §D.2 · p. 14
  • The authors identify broader analytically tractable families for RQAOA approximation ratios as an open direction.They call for examples where ratios can be computed or lower-bounded analytically.Source: §D.2 · p. 15
  • For the optimized QAOA1 state, the proof uses local two-point expectation values to select an edge and eliminate an adjacent variable.The cited expressions give nonzero correlations at separations one and two, with correlations zero beyond distance two.Source: §D.2 · p. 15
  • The elimination steps reduce the ring to a shorter Ising chain with couplings ±1, preserving coupling parity and imposing constraints on eliminated variables.The proof inductively eliminates variables until a chain of length n_c remains, then relates its maximum to the parity of the original couplings.Source: §D.2 · pp. 15–16
Loading 1910.08980v1…