PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View

Zhihui Wang, Stuart Hadfield, Zhang Jiang, Eleanor G. Rieffel

arXiv:1706.02998v2quant-ph

TL;DR

QAOA parameter optimization becomes inefficient as circuit level increases, motivating practical parameter-setting strategies for MaxCut. The paper derives QAOA1 expressions for general graphs and uses a fermionic reduction for the ring of disagrees to analyze arbitrary levels, simplify numerical search, and characterize parameter symmetries and landscapes.

  • Problem

    Increasing QAOA level makes optimization over its 2p parameters inefficient, so effective parameter-setting strategies are needed for MaxCut.

    Source: §I · p. 1, §II · p. 3

  • Method

    The paper combines analytical MaxCut calculations with a fermionic representation that reduces the ring of disagrees to independent spins and enables symmetry-constrained numerical searches.

    Source: §I · p. 1, B. Fermionic representation · p. 5

  • Results

    The approach yields analytical expressions for QAOA1 on general graphs and arbitrary-level expressions for the ring of disagrees, while reducing searches through a lower-dimensional symmetric sub-manifold.

    Source: §I · p. 2, §V · p. 9

  • Takeaways & Limitations

    For the ring of disagrees, parameter optimization is simplified because the relevant search can be restricted to a symmetric sub-manifold and the studied landscape has only global optima.

    Source: §I · p. 2, F. Discussion: controllability and… · p. 8, §V · p. 9

Abstract

from arXiv · show

Farhi et al. recently proposed a class of quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), for approximately solving combinatorial optimization problems. A level-p QAOA circuit consists of p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here, we analytically and numerically study parameter setting for QAOA applied to MaxCut. For level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ring of disagrees, or the 1D antiferromagnetic ring, we provide an analysis for arbitrarily high level. Using a fermionic representation, the evolution of the system under QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of QAOA for any p. It also greatly simplifies numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional sub-manifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

I. INTRODUCTION

The paper studies how to set QAOA parameters for MaxCut as increasing circuit level makes search inefficient. It combines analytical reductions, symmetry analysis, and numerical landscape studies to make parameter optimization more tractable.

I. INTRODUCTION

  • The paper analytically and numerically studies parameter setting for QAOA applied to MaxCut, focusing on parameter symmetries and expectation-value landscapes.These analyses are intended to aid the search for optimal parameter values.Source: §I · p. 1
  • For the ring of disagrees, a fermionic representation reduces QAOA evolution to an ensemble of independent spins, enabling analytical expressions for arbitrary p.The reduction turns the many-body problem into n/2 non-interacting pseudospins.Source: §I · p. 1
  • The reduced representation makes numerical evaluation linear in problem size and requires approximately 2p multiplications of 2-by-2 matrices.This supports efficient numerical searches for higher-level optimal angles.Source: §I · p. 1
  • Symmetry analysis identifies a lower-dimensional sub-manifold containing the optimal parameters for small p and explains an observed symmetry in their values.Restricting the search to this manifold reduces the optimization effort.Source: §I · p. 2
  • The numerical parameter landscape has only global optima, while direct parameter search becomes inefficient as p increases.The paper presents the no-local-optima result for the studied landscape alongside the need for more effective parameter-setting strategies.Source: §I · pp. 1–2

II. RECAP OF THE ALGORITHM

  • QAOA uses 2p Hamiltonian-application times as parameters, but exhaustive search scales as m^2p when each parameter has m possible values.The parameters alternate between problem and mixing Hamiltonians, and increasing p creates a curse of dimensionality.Source: §II · pp. 2–3

III. QAOA1 FOR MAXCUT

This section derives QAOA1 expectation values for MaxCut on general graphs and specializes the result to triangle-free regular graphs. It shows that edge expectations depend on local graph structure, while higher-level direct calculations quickly become unwieldy.

III. QAOA1 FOR MAXCUT

  • The derived QAOA1 expression applies to MaxCut on arbitrary graphs and allows its expectation value to be computed classically.Producing an actual approximate solution bit string still requires preparing and measuring the quantum state.Source: §III · p. 3
  • For QAOA1, each edge expectation depends only on the endpoint degrees and the number of triangles containing that edge.The overall expectation is obtained by summing contributions over graph substructures and their multiplicities.Source: §III · p. 3
  • For triangle-free regular graphs, one optimal angle pair can be obtained analytically, and the resulting approximation ratio is lower-bounded for arbitrary triangle-free graphs with bounded maximum degree.The result extends the analysis beyond the ring of disagrees.Source: §III · pp. 3–4
  • For the ring of disagrees, QAOA1 achieves approximation ratio 0.75 at (β, γ) = (π/8, π/4), while triangle-free 3-regular graphs achieve ratio 0.692.These values reproduce results reported in Ref. [1].Source: §III · p. 4
  • For higher p, direct operator expansion becomes prohibitive because more non-commuting terms must be retained and edge expectations depend on increasingly complex local topology.The paper therefore motivates more advanced parameter-setting techniques for higher levels.Source: §III · p. 4

IV. ANALYSIS OF THE PROBLEM OF RING OF DISAGREES (ANTI-FERROMAGNETIC CHAIN)

The ring of disagrees is analyzed for arbitrary QAOA levels, with even-size instances formulated through an approximation ratio and a rescaled Hamiltonian. The resulting parameter-setting problem is to choose angles that minimize the cost expectation and maximize this ratio.

IV. ANALYSIS OF THE PROBLEM OF RING OF DISAGREES (ANTI-FERROMAGNETIC CHAIN)

  • The analysis extends prior numerical work on the ring of disagrees to QAOA at arbitrary level p.Source: §IV · p. 4

A. Formulation of the problem

B. Fermionic representation

A Jordan-Wigner-based fermionic representation converts QAOA on the ring of disagrees into independent two-level pseudospin problems. This reduction preserves the relevant dynamics while making parameter evaluation and optimization substantially simpler.

B. Fermionic representation

  • The fermionic representation reduces QAOA parameter setting to optimal quantum control of an ensemble of independent spin-1/2 systems.Source: B. Fermionic representation · p. 4
  • The Jordan-Wigner transformation maps the one-dimensional spin system to fermions while preserving the spin algebra through a long-range phase factor.Source: B. Fermionic representation · pp. 4–5
  • For nearest-neighbor couplings, the Jordan-Wigner phase factors cancel in neighboring-spin products, leaving short-ranged fermionic interactions.Source: B. Fermionic representation · p. 5
  • Periodic boundary conditions require a parity-sector treatment because the conserved gauge operator changes the sign of the j = n term for even n.Source: B. Fermionic representation · p. 5
  • After Fourier transformation and parity reduction, each momentum sector becomes a two-dimensional problem with driver 2σz and problem Hamiltonian 2σz cos θk + 2σx sin θk.Source: B. Fermionic representation · p. 5
  • The n-spin ring therefore reduces to n/2 non-interacting pseudospins, and each QAOA evolution operator consists only of single-spin operators.Source: B. Fermionic representation · pp. 5–6

C. Size-dependence of the approximation ratio

For sufficiently large even rings, the approximation ratio is independent of problem size because the fermionic formulation restricts the relevant dependence to a finite trigonometric structure determined by p. This gives a direct analytic explanation of size independence.

C. Size-dependence of the approximation ratio

D. Symmetry and criticality-constrained manifolds

Symmetries of the pseudospin rotations identify lower-dimensional parameter sub-manifolds containing extrema, motivating a reduced search. The ring can also be viewed as an ensemble of controlled pseudospins whose final magnetization is optimized.

D. Symmetry and criticality-constrained manifolds

  • Rotation symmetries identify sub-manifolds that contain extrema, and numerical evidence indicates that global minima lie within them.Source: D. Symmetry and… · p. 6

1. Physics: rotations of the Bloch vectors

  • A pseudospin starts along z, alternates rotations about k and z, and is measured along k through its fidelity Fk.Source: §1 · p. 6
  • Periodicity gives F(γ + l·π/2, β + l′·π/2) = F(γ, β), allowing the search to be restricted to βk, γk ∈ [0, π/2].Source: §1 · p. 6
  • The ring is an optimal-control ensemble in which pseudospins experience individual quantization fields while a uniform z-directed field supplies bang-bang control.Source: §1 · pp. 6–7
  • The control sequence is chosen to minimize the final average magnetization measured along z.Source: §1 · p. 7

2. Criticality-constrained sub-manifolds

The paper identifies symmetry-constrained parameter sub-manifolds whose critical points are also critical points of the full QAOA objective, then illustrates their optimization consequences for QAOA1 and QAOA2.

2. Criticality-constrained sub-manifolds

  • Critical points on the manifold γ_i + β_{p+1−i} = 0 are also critical points of the full objective because the gradient is tangent to that manifold.For p = 1, this relation is also necessary for global minima.Source: §2 · p. 7
  • The objective is even under simultaneous angle reversal, F(γ, β) = F(−γ, −β), and numerical searches place minima and maxima in two corresponding submanifolds.Minima were found in the manifold defined by Eq. (53), while maxima were found in the manifold defined by Eq. (55).Source: §2 · p. 7

E. Illustration of QAOA1 and QAOA2

  • For QAOA1, F is proportional to sin(4β)sin(4γ), with the n = 2 expression differing from the n > 2 expression by a factor of two.The QAOA1 expectation landscape is plotted as a function of γ1 and β1.Source: E. Illustration of QAOA1 and QAOA2 · p. 7, Figure 2 · p. 8
  • For the ring of disagrees, QAOAp perfectly optimizes instances with n ≤ 2^p, while for n ≥ 2^p + 2 the optimization ratio is a fixed constant below 1.For n = 2, F* = −n; for larger problem sizes, F* = −n/2.Source: E. Illustration of QAOA1 and QAOA2 · p. 8
  • For QAOA1, the symmetry line β1 + γ1 = 0 contains global minima and saddle points, whereas β1 − γ1 = 0 contains global maxima and saddle points.The optimal angles include π·(3/8, 1/8) and π·(1/8, 3/8).Source: E. Illustration of QAOA1 and QAOA2 · pp. 7–8
  • The numerically found QAOA2 optima satisfy integer-multiple-of-2π conditions and therefore lie in the manifold defined by Eq. (53).This supports using the constrained manifold to reduce the search space for higher-level parameter optimization.Source: E. Illustration of QAOA1 and QAOA2 · p. 8

F. Discussion: controllability and optimality

The paper finds that QAOA parameter landscapes for the ring of disagrees have globally optimal minima within a symmetry-defined sub-manifold, despite finite-p controllability limits. It also develops a fermionic analysis that simplifies arbitrary-level optimization while identifying open limits and conjectures.

F. Discussion: controllability and optimality

  • Random-initialized searches within the Eq. (53) sub-manifold converge to global minima, and QAOA2 shows no observed local minima.The QAOA2 landscape has four global minima per period, while the origin is a saddle point.Source: F. Discussion: controllability and… · p. 8, Figure 3 · p. 8
  • The no-trap landscape result is specific in scope: finite-p QAOA is generally not controllable, and general MaxCut graphs can exhibit local optima even at p = 1.For the ring of disagrees, all local minima are global minima only within the identified sub-manifold.Source: F. Discussion: controllability and… · p. 8

V. CONCLUSIONS

  • For QAOA1, the paper derives analytical parameter-setting results for general graphs, while higher-p operator expansions become cumbersome.For triangle-free fixed-degree graphs, driver angles can be read directly, whereas problem-Hamiltonian angles depend on vertex degree.Source: §V · pp. 8–9
  • The fermionic representation reduces the ring problem to n/2 independent pseudospin evolutions, yielding analytical expressions for any p and easier numerical optimization.The reduction is implemented through a Jordan-Wigner transformation and two-dimensional independent evolutions.Source: §V · p. 9
  • The fermionic picture explains parameter symmetries and motivates restricting searches to lower-dimensional manifolds, but the underlying finite-p landscape theory remains unresolved.The paper also leaves the best achievable approximation-ratio conjecture for sufficiently large rings open and identifies noise analysis as future work.Source: §V · p. 9

Appendix A: Proof of Theorem 1

The appendix derives the level-1 MaxCut expectation by isolating which local constraints contribute after conjugation by the problem Hamiltonian. The resulting expression depends on local degrees and mutual-neighbor structure, with triangle effects entering at higher orders.

Appendix A: Proof of Theorem 1

  • Only constraints involving vertices neighboring the selected edge contribute to its level-1 expectation; remaining constraints do not contribute.The local terms are grouped into constraints incident only on either endpoint and the remaining constraints.Source: Appendix A · p. 9
  • Conjugating the contributing terms and expanding Pauli products isolates terms proportional to σz, which determine the expectation contribution.The derivation introduces c′ = cos γ and s′ = sin γ before evaluating the surviving terms.Source: Appendix A · p. 9
  • The first contribution is independent of the number of mutual neighbors, while higher-order terms depend on triangle count when sufficiently many mutual-neighbor pairings occur.The appendix gives an example where three pairs generate terms proportional to s′6.Source: Appendix A · pp. 9–10
  • Summing the surviving terms produces the level-1 analytical expectation expression used in the theorem.The appendix obtains the final expression after applying the binomial theorem and combining the separated contributions.Source: Appendix A · p. 10

Appendix B: Proof of symmetry relation Eq. (48)

The appendix records reversed parameter vectors and a symmetry operation for the pseudospin dynamics, while the accompanying results organize optimal angles across QAOA levels. Optimal points are represented geometrically in the symmetry-defined submanifold.

Appendix B: Proof of symmetry relation Eq. (48)

  • The parameter vectors γ and β are paired with their reversed sequences γ′ and β′ to express the symmetry relation.The appendix explicitly defines γ′ and β′ by reversing the order of the p-level parameters.Source: Appendix B · p. 10
  • The symmetry operation uses a π rotation about the axis defined by k̂ + ẑ and satisfies R† = R and R^2 = 1.These identities characterize the involutory rotation used in the proof.Source: Appendix B · p. 10
  • Table I reports one optimal angle set for each QAOA level, although multiple optima exist for p ≥ 2 and searches converge to a global minimum within Eq. (53).Angles are given in units of π, and the table uses level-p optima to initialize level p + 1 searches.Source: Table I · p. 11
  • Fig. 4 plots optimal points in the complex plane, using (4γ, 4β) as the argument and QAOA level p as the radius.Levels p = 1 through p = 9 appear on inner-to-outer circles.Source: Figure 4 · p. 11

Appendix C: Detailed results for p = 2 and higher

The appendix expands the QAOA2 objective into trigonometric terms and then restricts it to the symmetry sub-manifold. It also documents numerical optimization of higher-level angles within that reduced manifold.

Appendix C: Detailed results for p = 2 and higher

  • For p = 2, the full objective contains a long trigonometric expansion involving combinations of β1, β2, γ1, and γ2.The displayed expression consists of many cosine terms with signed linear combinations of the four angles.Source: Appendix C · pp. 11–12
  • Restricting the QAOA2 objective to Eq. (53) yields a substantially shorter expression in β1 and γ1.The reduced form contains six cosine terms, including cos(8γ1).Source: Appendix C · p. 12
  • Higher-level optimal angles are obtained by numerical gradient descent in Eq. (53), with the appendix tabulating representative solutions.The objective evaluation uses the reduced matrix-based expression, making higher-p searches computationally simple.Source: Appendix C · p. 12
Loading 1706.02998v2…