Source-linked AI summary
Classical and Quantum Bounded Depth Approximation Algorithms
M. B. Hastings
TL;DR
The paper examines whether bounded-depth local classical algorithms can match or outperform QAOA on approximate optimization problems. It develops and compares local classical approaches, and analyzes QAOA through perturbative reasoning. The discussion reports classical advantages in many cases, while the perturbative MAX-3-LIN-2 analysis limits what can be guaranteed across angle regimes.
Problem
The paper asks how bounded-depth QAOA performs relative to local classical algorithms, including whether increasing QAOA depth can improve its performance on bounded-degree MAX-3-LIN-2.
Source: §VI · p. 16Method
The paper studies local classical algorithms alongside QAOA and analyzes QAOA's objective value by expanding in its angles.
Source: §III · p. 7, §V · p. 14Results
The discussion reports local classical algorithms can outperform QAOA in many cases; for MAX-3-LIN-2, the perturbative analysis gives no performance guarantee at sufficiently large angles and only O(D^1/4N) improvement at small angles.
Source: §V · p. 13, §VI · p. 16Takeaways & Limitations
The paper concludes that further investigation of adjustable-parameter local classical algorithms is likely to be at least as promising as QAOA.
Source: §VI · p. 16The QAOA scaling argument is perturbative and assumes JΦ >> D^-3/4; larger angles may break the expansion, with no evidence that they are useful.
Source: §V · p. 13
Abstract
from arXiv · showhide
We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of "global" classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.
I. LOCAL ALGORITHMS
The paper defines local algorithms as bounded-step updates using information from neighboring spins, then specializes this framework to classical tensor algorithms. Simulated annealing is one instance, and the framework can in principle solve MAX-K-LIN-2 with sufficiently many steps.
I. LOCAL ALGORITHMS
- Local algorithms initialize independent per-spin degrees of freedom, update them from neighboring spins for a bounded number of steps, then produce each output spin from its local state.The QAOA is a local quantum algorithm; local classical algorithms use classical variables and computations.Source: §I · p. 2
- Tensor algorithms initialize a vector independently across entries, update it using the objective and entrywise nonlinear maps, then convert it into a spin configuration.For higher-degree objectives, the update can use forces derived by substituting continuous variables for other spins.Source: §I · pp. 2–3
- Simulated annealing with local spin flips is an instance of a local tensor algorithm, with updates depending on each spin's force and incorporating randomness.The updates occur in parallel, unlike typical single-spin-at-a-time annealing; lowering the update probability approaches sequential updates.Source: §I · p. 3
- With sufficiently many steps, the algorithm can solve any MAX-K-LIN-2 instance with probability arbitrarily close to 1.This consequence follows from the framework's ability to reproduce simulated annealing.Source: §I · p. 3
II. MAX-3-LIN-2
A single-step local tensor algorithm for MAX-3-LIN-2 achieves the same asymptotic scaling as the one-step QAOA. The analysis extends to odd K greater than 3, while even K has a weaker outcome.
II. MAX-3-LIN-2
- The construction initializes entries independently and uniformly from {−1/2, +1/2}, then chooses each Zi arbitrarily when |(v1)i| > 1 or randomly with expectation (v1)i when |(v1)i| ≤ 1.For |(v1)i| ≤ 1, this method is sometimes called using soft spins.Source: §II · pp. 3–4
- Θ(D^1/4N) expected objective value gives Θ(D^-3/4) improvement per term, matching the one-step QAOA's scaling.The proof chooses c0 proportional to D^-3/4 so the leading contribution dominates the remaining terms.Source: §II · pp. 4, 6
- The proof controls higher-order terms by bounding tensor-network contractions, yielding an O(ND^5/2|c0|^3) bound for one contribution.A general lemma bounds a network contraction when each tensor has at most d nonzero entries bounded in absolute value by 1.Source: §II · p. 6
- The probability that an updated entry exceeds magnitude 1 is bounded by exp(−Ω(D^1/4)), making its contribution negligible for large D.This tail bound supports the claimed MAX-3-LIN-2 scaling.Source: §II · p. 7
- For odd K > 3, the same algorithm achieves Θ(D^1/4N), but for even K the expected objective value is only Θ(N).K-dependent prefactors are ignored in the odd-K scaling.Source: §II · p. 7
III. MAX-CUT ON A TRIANGLE FREE GRAPH
On triangle-free MAX-CUT graphs, the paper compares one-step QAOA with local classical algorithms, including the threshold algorithm. The threshold algorithm beats QAOA for most tested degrees, and a generalization covers the remaining exceptional degrees.
III. MAX-CUT ON A TRIANGLE FREE GRAPH
- The threshold algorithm randomly assigns spins, then flips a spin when enough of its neighbors agree with it.The threshold τ is the parameter controlling when the spin changes sides.Source: §III · p. 8
- For 3 ≤ D ≤ 1000, the numerically optimized threshold algorithm beats QAOA except at D = 3, 4, 6, 11, while both tie at D = 2.Numerical scaling analysis suggests classical superiority for D > 1000, but the paper does not prove that asymptotic comparison.Source: §III · p. 8
- For D = 6 and 11 the paper proves a generalized local classical algorithm beats QAOA; for D = 3 and 4 it uses Monte Carlo performance estimates.The paper notes that those numerical cases could likely also be proved rigorously.Source: §III · p. 8
- A single linear update from independent random spins followed by taking each updated entry's sign reproduces the threshold algorithm for suitable parameters.The threshold condition is c0(2m − D) > 1 when m neighbors agree with the initial spin.Source: §III · p. 8
A. D = 6, 11 Algorithm
For degrees 6 and 11, a soft-threshold generalization of the classical algorithm beats one-step QAOA. The reported rules were found by numerical search.
A. D = 6, 11 Algorithm
- For D = 11, the soft-threshold rule improves over random by 0.09868, exceeding QAOA's 0.0936; for D = 6, it improves by 0.13018, exceeding QAOA's 0.1294.At the boundary neighbor counts, the rule uses probabilistic flips: 0.55 for seven agreeing neighbors at D = 11 and 0.65 for four at D = 6.Source: A. D = 6, 11 Algorithm · p. 8
- The soft threshold generalizes hard thresholding by making the flip probability depend on the number of agreeing neighbors.For D = 11, spins do not flip with at most six agreeing neighbors and do flip with more than eight.Source: A. D = 6, 11 Algorithm · p. 8
- The algorithm remains a local tensor algorithm by choosing c0 to make the boundary case neutral, then adding weak biased random noise to set its output probability.For D = 11, the neutral boundary is seven agreeing neighbors; D = 6 uses a similar construction.Source: A. D = 6, 11 Algorithm · pp. 8–9
B. D = 3, 4 Algorithm
For D = 3 and 4, a one-step local tensor algorithm using uniformly distributed initial values outperforms one-step QAOA. The authors suggest that variable magnitudes and continuous tuning may explain its performance.
B. D = 3, 4 Algorithm
- For D = 3, improvement over random is 0.1980… for the local tensor algorithm versus 0.1925 for QAOA; for D = 4, it is 0.1693… versus 0.1624.The algorithm uses c = 0.6 for D = 3 and c = 0.54 for D = 4.Source: B. D = 3, 4 Algorithm · p. 9
- Unlike a threshold algorithm, the update’s flip likelihood depends on the initial magnitude, which also affects that spin’s influence on its neighbors.The authors offer this coupling as one possible explanation for the uniform distribution’s performance.Source: B. D = 3, 4 Algorithm · p. 9
- A continuous parameter c can be tuned, whereas the threshold algorithm has only a discrete threshold that may be poorly suited to some small degrees.The authors also suggest that threshold-performance oscillations may leave some small degrees “unlucky.”Source: B. D = 3, 4 Algorithm · p. 9
- The authors did not extensively search over initial-value distributions, so other distributions may improve performance.Source: B. D = 3, 4 Algorithm · p. 9
C. Numerical Implementation
The implementation evaluates one-step algorithms on triangle-free graphs by reducing edge correlations to a common local neighborhood. Discrete cases are enumerated, while the continuous cases use Monte Carlo sampling.
C. Numerical Implementation
- On a triangle-free graph, every neighboring pair and its neighbors form the same 2D-vertex subgraph, so edge expectations can be evaluated on that local structure.The one-step setting lets the pair’s distribution be computed from the initial distribution on its neighboring spins.Source: C. Numerical Implementation · p. 9
- For discrete initial assignments, the finite configurations can be enumerated, grouping configurations by neighbor sums because permutations of a spin’s neighbors do not change the edge expectation.For {−1, +1} initial values, the neighbor-sum probabilities follow a binomial distribution.Source: C. Numerical Implementation · p. 9
- The general update assigns an expected spin value q(j) times its initial value when j neighbors agree; threshold updates restrict q(j) to −1 or +1.The authors also consider more general q(j) choices for D = 6 and 11.Source: C. Numerical Implementation · p. 9
- For D = 3 and 4, Monte Carlo sampling of 10^8 configurations per case has statistical error of order 10^-4, over 50 times smaller than the performance gap from QAOA.A discrete approximation using {−1, −1/3, +1/3, +1} can be enumerated exactly and also outperforms QAOA, though by less.Source: C. Numerical Implementation · p. 10
D. Scaling
Numerical tests of the threshold algorithm up to degree 1000 show improvement over random scaling as c/√D. The authors explain this scaling through the probability that a neighboring spin can become the deciding vote.
D. Scaling
- Up to D = 1000, numerical tests show threshold-algorithm improvement over random approaching c/√D for some constant c.The optimal threshold approaches D/2 + c′√D for another constant c′.Source: D. Scaling · p. 10
- For large D, a neighbor-sum has width proportional to √D, making the probability that a spin can cast the deciding vote of order 1/√D.The probability that the other spin remains unchanged approaches a nonzero constant, so the joint event is Θ(1/√D).Source: D. Scaling · p. 10
IV. GENERALIZATIONS
The paper proposes speculative extensions of local tensor algorithms using multiple random vectors and tensor-network contractions. With enough such networks, a single step can solve MAX-K-LIN-2 to arbitrary accuracy.
IV. GENERALIZATIONS
- The proposed generalizations are explicitly speculative and have not been applied to any problem.Source: §IV · p. 10
- One extension keeps multiple independently initialized random vectors at each step and determines the next set from the current vectors.For MAX-K-LIN-2, contractions of J with K−1 vectors produce additional vectors that can enter linear combinations before applying an update function.Source: §IV · pp. 10–11
- FIG. 3 plots degree against D-scaled improvement over random; both algorithms tend to limits, with the threshold algorithm’s limit larger.The threshold curve has more degree-to-degree wiggles, possibly because its discrete optimum can jump as D changes.Source: Figure 3 · p. 11
- The multiple-vector algorithm reduces to the earlier algorithm when there is only one vector at each step.Source: §IV · p. 11
- A broader extension forms new tensors by contracting tensor networks containing J, then contracts all but one leg with vectors before combining the resulting vectors.The earlier algorithm is the special case using a network containing J once.Source: §IV · p. 11
- With a sufficient number of tensor networks, even a single step can solve any MAX-K-LIN-2 instance to arbitrary accuracy.Source: §IV · p. 11
- FIG. 4 plots (optimal threshold − D/2)/D against degree; the apparent two-valued pattern reflects an even–odd oscillation, with each parity forming a function.Source: Figure 4 · p. 12
- At low temperatures, small random fields generically select a unique minimum, whose spin expectations can be computed by tensor-network diagrams.Source: §IV · p. 12
V. LIMITATIONS
For MAX-3-LIN-2, the authors present strong evidence—not a proof—that fixed-depth QAOA and a simple local tensor algorithm cannot improve asymptotic scaling. Their perturbative analysis identifies uncontrolled-sign contributions and angle-dependent limits; some broader local tensor generalizations may evade the difficulty.
V. LIMITATIONS
- One-step QAOA and the local tensor algorithm have the same asymptotic MAX-3-LIN-2 performance, but a cubic uncontrolled-sign term limits the adjustable parameter to small values.At small performance values, improvement is linear in the parameter, while the cubic term's sign cannot be controlled.Source: §V · p. 12
- Strong evidence, not proof, suggests fixed-depth QAOA and a simple local tensor algorithm cannot improve MAX-3-LIN-2 asymptotic scaling; broader local tensor generalizations may evade this difficulty.The authors explicitly leave open whether some generalizations of local tensor algorithms can achieve greater asymptotic performance.Source: §V · p. 12
- For sufficiently large angles, the constructed perturbative objective has a dominant contribution of uncontrolled sign; with small angles, QAOA gains only O(D1/4N) over random.The uncontrolled sign means it can be changed arbitrarily by changing signs of objective terms, so the perturbative treatment gives no performance guarantee in that regime.Source: §V · p. 13
- The semiclassical update can make Zi much larger than Zi+1 while retaining φJi,i+1 Z²i+1 << 1 when Zi+1 << D; the approximation ⟨Z²⟩=⟨Z⟩² is not exact.After lower-order terms cancel the baseline |Si+1| contribution, a nontrivial second moment can produce an expectation value that grows exponentially at each step.Source: §V · p. 14
- For JΦ >> D^-3/4, the main trivalent diagrams grow with D; the Fig. 7 contribution is negligible when (JΦ)^3D^2 << 1.The authors give a regime D^-3/4 << JΦ << D^-2/3 in which this diagram can be made negligible.Source: §V · pp. 14, 16
- In the diagrammatic argument, the leading contribution has uncontrolled sign because its J0 term appears once; other diagrams at that order are lower order in Np.The authors identify Fig. 5 as the only diagram leading in both D^-1 and Np^-1 for the given order in D^-1.Source: §V · pp. 14, 16
VI. DISCUSSION
The discussion argues that QAOA’s bounded-depth performance resembles simple local classical updates, and that local classical algorithms can match or exceed it in many cases. It also cautions that broader local quantum or classical variants remain open, while nonlocal, size-dependent classical algorithms are expected to outperform local methods.
VI. DISCUSSION
- The authors see QAOA as performing updates similar to simple local classical algorithms, and report that local classical algorithms can outperform it in many cases.They say there is no general explanation for why the quantum circuit should outperform such a classical algorithm.Source: §VI · p. 16
- The argument that many steps approach an exact limiting algorithm is insufficient by itself to establish practical usefulness at a small number of steps.The discussion notes that local tensor algorithms can reproduce simulated annealing and diagrammatic sums, but emphasizes that practical usefulness depends on behavior at finite parameter values.Source: §VI · p. 16
- For large systems, the authors say current classical algorithms appear better than QAOA, while numerical extrapolation and growth in QAOA parameters complicate assessment.They recommend further investigation of local classical algorithms with adjustable parameters as likely at least as promising as QAOA.Source: §VI · p. 16
- The discussion leaves open whether more general local quantum algorithms could improve on local classical methods, but expects nonlocal, size-dependent classical algorithms to outperform both.It notes that continuous local variables improved results for D = 3, 4, while the broader local quantum possibility has not been ruled out.Source: §VI · p. 16
- One-step QAOA generally tunes one real parameter, while the threshold algorithm tunes one discrete parameter; communication needs also differ.For D = 6, 11 the threshold algorithm tunes one discrete and one real parameter, while for D = 3, 4 it tunes one real parameter; QAOA communicates quantum information, versus one bit or one real number for the classical methods.Source: §VI · pp. 16–17
VII. NUMERICAL RESULTS FOR TRIANGLE FREE MAX-CUT
The numerical-results section reports that the threshold algorithm generally exceeds one-step QAOA on triangle-free MAX-CUT, with four degree exceptions. QAOA performance is obtained from its exact optimal-parameter formula, and Table I compares improvements over random assignment by degree.
VII. NUMERICAL RESULTS FOR TRIANGLE FREE MAX-CUT
- QAOA performance values are obtained from the exact formula for the optimal parameter choices.The section directs readers to Table I for the comparison.Source: §VII · p. 17
- The threshold algorithm is better than one-step QAOA for all listed degrees except D = 3, 4, 6, and 11, and is reported numerically better for all D up to 1000.The table compares improvement over random assignment for triangle-free MAX-CUT.Source: Table I · p. 17
- Table I organizes the comparison by degree and reports threshold-algorithm improvement and threshold value alongside one-step QAOA performance.Its scope is improvement over random assignment on triangle-free MAX-CUT.Source: Table I · p. 17