PaperlayerView exact revision on arXiv

Source-linked AI summary

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

arXiv:1411.4028v1quant-ph

TL;DR

The paper introduces a quantum algorithm for approximate combinatorial optimization and studies its performance on MaxCut. It shows how the algorithm’s approximation quality and implementation strategy depend on the parameter p.

  • Problem

    The paper asks how quantum algorithms can produce approximate solutions for combinatorial optimization and evaluates this question on MaxCut.

  • Method

    The approach uses the QAOA parameterized by p, with fixed-p classical preprocessing and an alternate strategy when p grows with input size.

  • Results

    The paper analyzes QAOA performance on special cases of MaxCut, including regular graphs, and examines strategies for finding high-value cuts.

  • Takeaways & Limitations

    The results support studying QAOA as a general approximate-optimization framework across combinatorial search problems.

Abstract

from arXiv · show

We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.

I. INTRODUCTION

The paper presents a general quantum algorithm for approximate combinatorial optimization, studies it on MaxCut, and proposes an independent-set variant. Its p-layer state can be implemented with bounded-locality gates, while fixed-p angles can be found efficiently under bounded clause incidence.

  • Contributions: The paper introduces a general quantum algorithm for approximate optimization, studies special cases of MaxCut, and proposes an independent-set variant.Approximate optimization seeks a string whose objective value is close to the maximum.
  • Algorithm structure: The algorithm’s objective-function terms commute, and each term has locality equal to its corresponding clause.This follows from the terms being diagonal in the computational basis.
  • Algorithm structure: For any integer p ≥1, the algorithm prepares a state using alternating objective and one-bit operator layers parameterized by 2p angles.The state is defined as |γ, β⟩= U(B, βp) U(C, γp) · · ·U(B, β1) U(C, γ1) |s⟩.
  • Parameter selection: O(m2 + mn) bounds the partial derivatives of Fp, enabling a grid search that efficiently produces a string with C(z) close to Mp or larger.This grid-search strategy applies when p does not grow with n.
  • Parameter selection: When p is fixed and each bit belongs to at most a fixed number of clauses, an efficient classical calculation determines angles maximizing Fp.Using these angles, the quantum circuit produces samples whose mean objective value is Mp.

II. FIXED p ALGORITHM

For fixed p, bounded-degree MaxCut permits classical preprocessing of F_p using finitely many local subgraph types whose sizes do not grow with n. After optimizing the angles, repeated quantum sampling produces cut values with mean F_p and yields an outcome near that mean with high probability.

  • Local evaluation: For fixed p, each edge contribution depends only on a radius-p subgraph whose size is independent of n for bounded degree.This reduces F_p evaluation to quantum subsystems of n-independent size.
  • Subgraph aggregation: Isomorphic subgraphs give identical angle-dependent contributions, so the objective sum can be reorganized over finitely many subgraph types.The functions f_g do not depend on n or m; only their graph-derived weights do.
  • Classical preprocessing: For each fixed p, F_p(γ, β) can be evaluated classically with resources that do not grow with n.The required Hilbert-space dimension may be large for large p, but remains independent of n.
  • Quantum execution: After finding angles that maximize F_p, the quantum computer prepares the corresponding state, measures strings z, and evaluates C(z).Repeated measurements produce sampled objective values whose mean is F_p(γ, β).
  • Sampling guarantee: m log m repetitions yield an outcome of at least F_p(γ, β) −1 with probability 1 −1/m.The sampling procedure uses order m log m repetitions.

III. CONCENTRATION

For regular-graph MaxCut, when v is fixed and p is fixed or grows slowly with n, the distribution of C(z) concentrates near its mean. This concentration follows from the locality of correlations and implies that substantially above-average outcomes are unlikely.

  • CONCENTRATION: For fixed v and p, or p growing slowly with n, C(z) is concentrated near its mean in the state |γ, β⟩.The section studies the spread of C measured in the algorithm’s output state.
  • CONCENTRATION: Correlations between edge contributions vanish when their associated subgraphs share no qubits.This occurs when no path connects the two edges in the instance graph with length 2p + 1 or shorter.
  • CONCENTRATION: For fixed v and p, only finitely many nearby edge pairs can contribute to the variance sum, because each summand has norm at most 1.The contributing-edge count is bounded using the instance graph with p replaced by 2p + 1; for v = 2, the bound is 4p + 4.
  • CONCENTRATION: The concentration result implies that the sample mean of m^2 values of C(z) lies within 1 of Fp(γ, β) with probability 1 − 1.The supplied passage presents this quantitative probability statement incompletely.
  • CONCENTRATION: The concentrated distribution also makes it unlikely that the algorithm produces strings with C(z) much bigger than Fp(γ, β).Thus concentration limits the probability of substantially above-mean outcomes.

IV. THE RING OF DISAGREES

For MaxCut on connected 2-regular graphs, which are rings, the analysis gives an approximation ratio approaching 1 as p increases, while the circuit depth remains independent of n.

  • IV. THE RING OF DISAGREES: For connected degree-2 regular graphs, the graph is a ring, and the objective maximum is n or n−1 according to whether n is even or odd.The analysis considers the algorithm for all p.
  • IV. THE RING OF DISAGREES: For p less than n/2, every edge has the same local subgraph: a line segment of 2p + 2 connected vertices, with weight n.This uniform structure reduces the analysis to one subgraph type for each p.
  • IV. THE RING OF DISAGREES: For p = 1, 2, 3, 4, 5 and 6, the numerically obtained maxima are 3/4, 5/6, 7/8, 9/10, 11/12, and 13/14, yielding Mp = n(2p + 1)/(2p + 2).The maxima match the stated formula to 13 decimal places.
  • IV. THE RING OF DISAGREES: n(2p + 1)/(2p + 2) −1 or bigger is the cut size found by the quantum algorithm, compared with a best cut of n.Thus, the approximation ratio can be made arbitrarily close to 1 by increasing p, independently of n.
  • IV. THE RING OF DISAGREES: 3p is an achievable circuit depth after splitting the edge sum into even-j and odd-j terms, making the depth independent of n.The decomposition uses two sums over ⟨j, j + 1⟩.

V. MAXCUT ON 3-REGULAR GRAPHS

For p = 1, QAOA guarantees a cut at least 0.6924 times optimal on every 3-regular graph, with the analysis based on local subgraph counts. For p = 2, partial results give a 0.7559 limiting ratio for sparse-short-cycle graphs, while longer odd loops yield higher ratios.

  • p = 1: For p = 1, the approximation analysis characterizes graphs by n vertices, S crossed squares, and T isolated triangles.The resulting bound uses the constraints 4s+3t ≤1 after scaling S and T by n.
  • p = 1: O(n log n) measurements produce a string with cut value very near or above M1(n, S, T) after classical preprocessing and angle optimization.The maximizing angles are used to prepare the QAOA state before computational-basis measurement.
  • p = 1: 0.6924 is the minimum guaranteed approximation ratio for QAOA with p = 1 on any 3-regular graph.The bound means the algorithm always produces a cut at least 0.6924 times the optimal cut size.
  • p = 2: 0.7559 is obtained by numerically maximizing the p = 2 local expression for the 14-vertex tree subgraph type.The p = 2 analysis is explicitly partial because it is more complicated than the p = 1 case.
  • p = 2: 0.7559 is the limiting approximation ratio for bipartite 3-regular graphs with o(n) pentagons, squares, and triangles; graphs with many odd loops of length 7 or more have higher ratios.At p = 2, QAOA cannot distinguish bipartite graphs from graphs containing many sufficiently long odd loops.

VI. RELATION TO THE QUANTUM ADIABATIC ALGORITHM

The QAOA can approach the QAA’s optimal-solution behavior as p increases, but it may do so with exponentially large p. Unlike the QAA, QAOA can succeed in examples where the QAA is trapped or has impractical runtime behavior.

  • QAOA versus QAA: For a symmetric minimization example, the QAA is trapped at the false minimum w = n for subexponential run times, whereas p = 1 QAOA can concentrate near the true minimum w = 0.The QAOA succeeds for suitable values of γ1 and β1 even when p = 1.
  • QAOA versus QAA: As p increases, the QAOA approximation improves and can approach the QAA’s result, although sufficiently large p may be exponentially large in n.The QAA reaches the highest-energy solution for sufficiently long runtime, while its Trotterized approximation requires small angles and long total runtime, forcing p to be large.
  • QAOA versus QAA: The QAA’s success probability is generally nonmonotonic in runtime T, rising and then dropping dramatically on a particular 20-qubit Max2Sat instance.The eventual rise at very large T is not visible within reasonably simulable times.

VII. A VARIANT OF THE ALGORITHM

The variant adapts the algorithm to optimization over complicated subsets of bit strings, illustrated by maximum independent set. It restricts the Hilbert space to legal strings and uses alternating objective- and connectivity-dependent unitaries to search that space.

  • Motivation and encoding: The variant targets problems whose search space is a complicated subset of the n bit strings, using maximum independent set as an example.Independent sets correspond to legal bit strings, with 1 indicating membership and 0 indicating exclusion.
  • Motivation and encoding: The objective C(z) is the Hamming weight of a legal string z, and the goal is to find an independent set with large C(z).Legal strings are restricted to those representing independent sets, where no selected vertices share an edge.
  • Restricted Hilbert space: The algorithm operates in the Hilbert space spanned by independent-set strings, whose dimension can be exponentially large in n but is smaller than 2^n.This space is not a simple tensor product of qubits.
  • Quantum operators and state preparation: The operator B connects legal strings differing in one bit, making it the hypercube adjacency matrix restricted to independent-set strings.The state begins at the empty independent set, and the circuit alternates operators associated with B and C using p parameters.
  • Quantum subroutine: The resulting subroutine prepares |b, γ⟩, measures it to obtain an independent-set string, and repeats measurements to estimate F_p(b, γ) for classical maximization toward M_p.For p = 1, the process can be viewed as a continuous-time quantum walk on the graph of independent sets.

VIII. CONCLUSION

The conclusion presents QAOA as a parameterized quantum algorithm for approximate combinatorial optimization, with angle-selection strategies for fixed or growing p. It highlights efficient classical preprocessing for fixed p, a doubly exponential space limitation, and the prospect of surpassing classical algorithms.

  • VIII. CONCLUSION: QAOA uses an integer parameter p and seeks a string z whose objective value C(z) is close to the global maximum of C.The objective function C is the sum of m local terms over an n-bit instance.
  • VIII. CONCLUSION: For fixed p with bounded clause participation, an efficient classical algorithm determines the best angle set before the quantum computer is run.The quantum computation uses only that best set of angles.
  • VIII. CONCLUSION: Doubly exponential space in p may be required when the classical preprocessor evaluates the relevant expressions.This limitation applies to the classical algorithm that evaluates (25) using (24).
  • VIII. CONCLUSION: When p does not grow with n, a polynomial-size fine grid over [0, 2π]^p × [0, π]^p can search for suitable angles.The strategy relies on Fp lacking peaks too narrow for the grid to detect.
  • VIII. CONCLUSION: For p growing with n, QAOA remains runnable if an angle-selection strategy exists, including classical optimization of quantum evaluations of the smooth function Fp(γ, β).The quantum computer can evaluate Fp as the expectation of C in the state |γ, β⟩.
Loading 1411.4028v1…