# Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs

@article{Marwaha2021LocalCM, title={Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs}, author={Kunal Marwaha}, journal={Quantum}, year={2021}, volume={5}, pages={437} }

<jats:p>The <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi></mml:math>-stage Quantum Approximate Optimization Algorithm (QAOA<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi /><mml:mi>p</mml:mi></mml:msub></mml:math>) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml…

#### 8 Citations

An explicit vector algorithm for high-girth MaxCut

- Computer Science, PhysicsArXiv
- 2021

An approximation algorithm is given and guarantees on the average fraction of edges cut on d-regular graphs of girth ≥ 2k are provided, which are better than those of all other classical and quantum algorithms known to the authors.

Analytical Framework for Quantum Alternating Operator Ans\"atze

- Physics
- 2021

We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze. In the context of combinatorial optimization, our framework relates quantum cost gradient…

Bounds on approximating Max kXOR with quantum and classical local algorithms

- Computer Science, PhysicsArXiv
- 2021

A tight upper bound on the maximum satisfying fraction of nearly all large random regular Max kXOR instances is computed by numerically calculating the ground state energy density P (k) of a mean-field k-spin glass and grows with k much faster than the performance of both one-local algorithms.

Classical algorithms and quantum limitations for maximum cut on high-girth graphs

- Computer Science, PhysicsArXiv
- 2021

It is proved that every (quantum or classical) one-local algorithm achieves on D-regular graphs of girth > 5 a maximum cut of at most 1/2+C/√ D for C = 1/ √ 2 ≈ 0.7071, the first such result showing that one- local algorithms achieve a value that is bounded away from the true optimum for random graphs.

Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond

- Physics, Computer ScienceArXiv
- 2021

This work shows that there exists e > 0, such that e log(n) depth QAOA cannot arbitrarily-well approximate the ground state energy of random diluted k-spin glasses when k ≥ 4 is even, and extends the limitation to other boolean constraint satisfaction problems as long as the problem satisfies a combinatorial property called the coupled overlap-gap property (OGP).

Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach

- Physics
- 2021

Jordi R. Weggemans, 2 Alexander Urech, 2 Alexander Rausch, Robert Spreeuw, 2 Richard Boucherie, Florian Schreck, 2 Kareljan Schoutens, 2 Jǐŕı Minář, 2 and Florian Speelman 2 CWI, Science Park 123,…

The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

- Computer Science, PhysicsArXiv
- 2021

This work gives an iterative formula to evaluate performance for any D at any depth p, and finds that the p = 11 QAOA beats all classical algorithms that are free of unproven conjectures.

Warm-starting quantum optimization

- Computer Science, PhysicsQuantum
- 2021

Results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth, and it is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

#### References

SHOWING 1-10 OF 21 REFERENCES

Classical and quantum bounded depth approximation algorithms

- Computer Science, PhysicsQuantum Inf. Comput.
- 2019

The QAOA is considered and strong evidence is provided 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.

What do QAOA energies reveal about graphs

- Mathematics, Physics
- 2019

Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm to approximately solve NP optimization problems such as MAX-CUT. We describe a new application area of QAOA…

A Quantum Approximate Optimization Algorithm

- Mathematics, Physics
- 2014

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…

Bounds on MAXCUT QAOA performance for p>1

- Physics, Mathematics
- 2020

We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of $0.692$…

Large Cuts with Local Algorithms on Triangle-Free Graphs

- Mathematics, Computer ScienceElectron. J. Comb.
- 2017

This algorithm was designed by a computer program that searched for optimal algorithms for small values of $d by means of a randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round.

Beating the random assignment on constraint satisfaction problems of bounded degree

- Computer Science, MathematicsElectron. Colloquium Comput. Complex.
- 2015

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D))…

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

- Mathematics, Physics
- 2014

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…

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

- Computer Science, Physics
- 2018

An in-depth study of the performance of QAOA on MaxCut problems is provided by developing an efficient parameter-optimization procedure and revealing its ability to exploit non-adiabatic operations, illustrating that optimization will be important only for problem sizes beyond numerical simulations, but accessible on near-term devices.

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

- Mathematics, Computer ScienceJACM
- 1995

This algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of semidefinite programming in the design of approximation algorithms.

The theory of variational hybrid quantum-classical algorithms

- 2016

Many quantumalgorithms have daunting resource requirements when compared towhat is available today. To address this discrepancy, a quantum-classical hybrid optimization scheme known as ‘the…