Source-linked AI summary
A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann
TL;DR
The paper studies how to exceed random guessing on bounded-occurrence Max E3LIN2, where each constraint contains three variables and each variable has bounded occurrence. It applies level-one QAOA and reports improved satisfaction guarantees, including a separate typical-instance result.
Problem
Max E3LIN2 seeks a bit string satisfying as many inconsistent three-variable parity equations as possible under a bounded-occurrence restriction.
Method
The paper applies the p = 1 Quantum Approximate Optimization Algorithm, using objective and mixing operators before measuring a quantum state.
Results
The analysis gives a general-case improvement and a separate satisfaction guarantee for typically selected instances.
Takeaways & Limitations
The paper shows that level-one QAOA can improve on random guessing for bounded-occurrence Max E3LIN2.
Abstract
from arXiv · showhide
We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of linear equations each of which contains exactly three boolean variables and each equation says that the sum of the variables mod 2 is 0 or is 1. Every variable is in no more than D equations. A random string will satisfy 1/2 of the equations. We show that the level one QAOA will efficiently produce a string that satisfies $\left(\frac{1}{2} + \frac{1}{101 D^{1/2}\, l n\, D}\right)$ times the number of equations. A recent classical algorithm achieved $\left(\frac{1}{2} + \frac{constant}{D^{1/2}}\right)$. We also show that in the typical case the quantum computer will output a string that satisfies $\left(\frac{1}{2}+ \frac{1}{2\sqrt{3e}\, D^{1/2}}\right)$ times the number of equations.
I. INTRODUCTION
The paper applies level-one QAOA to bounded-occurrence Max E3LIN2, seeking strings that satisfy more equations than random guessing. It introduces the problem, its occurrence restriction, and the algorithmic and performance context for the quantum approach.
- Algorithm: The p = 1 QAOA constructs a quantum state from the objective operator C and the mixing operator B, then measures it to produce a bit string.The implementation uses local constraint unitaries and one-qubit mixing operations.
- Prior quantum result: Nonzero QAOA parameters can outperform random guessing, extending the earlier MaxCut result from 1/2 to .6924 on 3-regular graphs.The paper uses this prior improvement to motivate another application of QAOA.
- Problem: Max E3LIN2 asks for a bit string maximizing satisfied three-variable linear equations modulo 2 when the system may be inconsistent.Each constraint has exactly three variables and specifies parity 0 or 1.
- Motivation: Random guessing satisfies 1/2 of the equations, while general instances lack an efficient algorithm unless P=NP.The paper therefore studies a bounded-occurrence setting.
- Bounded occurrence: Each bit is restricted to occur in no more than D + 1 equations, enabling comparison with prior classical approximation results.The paper cites earlier classical algorithms and hardness results for this setting.
II. THE GENERAL CASE
The level-one QAOA analysis evaluates clause contributions under bounded occurrence and selects parameters so the positive contribution dominates error terms. It then shows an efficiently searchable parameter choice and repeated sampling procedure that yields a string outperforming random guessing.
- Sampling guarantee: Repeated quantum sampling has expected satisfied-equation count given by m/2 plus the objective value, and a sample of size m log m contains a comparably good string.The baseline at γ = β = 0 is random guessing, corresponding to an expected m/2 satisfied equations.
- Expectation analysis: β = π/4 simplifies the expectation, whose clause contribution is expressed through trigonometric terms involving d_123 and neighboring variables.The X_1X_2X_3 and Y_1Y_2Y_3 contributions are combined before Taylor expansion.
- Expectation analysis: Bounded occurrence limits each bit to at most D + 1 clauses, constraining the neighboring terms contributing to a clause’s expectation.For a central clause, the surrounding analysis counts at most 3D neighboring clauses and up to 6D additional qubits.
- Parameter choice: The linear Taylor coefficient is 1/2 regardless of the equation, while higher-order terms are bounded using degree-2 polynomial estimates.The bounded occurrence assumption is used together with Cauchy–Schwarz in controlling the remainder.
- Parameter choice: k = 5 ln D is chosen so the positive term dominates, producing a suitable γ among at most 5 ln D tested values.The analysis uses the oddness of the objective in γ to select a sign yielding a positive value, and γ can be found efficiently.
III. THE TYPICAL CASE
For fixed triples with independently random equation choices, the level-one quantum algorithm has an average performance that concentrates on typical instances as the number of equations grows.
- Instance distribution: For each fixed collection of m triples, the 2^m E3LIN2 instances are obtained by independently choosing equation signs ±1 with probability 1/2.
- Average performance: The expected performance is evaluated at β = π/4 while γ is selected to optimize the resulting lower bound.
- Concentration: The variance is bounded by 1/4m(6D + 3)(D + 1), using the fact that only linked clause pairs contribute.
- Concentration: The mean number of satisfied equations is of order m, while the standard deviation is of lower order when D is fixed and m grows.
- Typical-case guarantee: Thus, with high probability, a typical instance receives at least the stated typical-case lower bound from the average analysis.
IV. CONCLUSIONS
The paper applies level-one QAOA with predetermined parameters to bounded-occurrence Max E3LIN2 and identifies typical random-sign instances where it achieves its stated guarantee.
- Conclusions: Level-one QAOA uses predetermined β and γ parameters for Max E3LIN2 instances in which each bit appears in at most D + 1 equations.
- Conclusions: For a fixed triple collection, random 50/50 equation choices yield the algorithm's stated satisfaction guarantee with high probability.
- Conclusions: If 51% of equation choices are 1, the all-1 string satisfies 51% of equations independently of D, so hard cases require nearly balanced choices.
- Possible improvements: The authors state that quantum performance can be improved by searching for optimal β and γ values at p = 1 or by expanding the parameter space.
- Possible improvements: Higher p may yield a better dependence of the approximation ratio on D than a constant dependence.