1 of 16

Local Classical Competitors to QAOA on MAXCUT

https://arxiv.org/abs/2101.05513

​

Kunal Marwaha

February 3, 2021 and May 11, 2021

2 of 16

Does QAOA have quantum speedup* on MAXCUT?

Prior work: NO (p=1) (all D-regular, triangle-free graphs)

This work: NO (p=2) (all D-regular, girth>5 graphs)

​

(*compared to local algorithms)

2

3 of 16

What does “local” mean?

Let’s call an algorithm k-local if:

  • The solution is a label for every vertex
  • Each vertex’s label is computed only knowing�the vertex’s radius-k neighborhood

Local algorithms at small k cannot “see” the entire graph

3

4 of 16

Overview

  1. The MAXCUT problem
  2. Brief review of QAOA
  3. Local classical alternatives
  4. Open questions

4

5 of 16

1. The MAXCUT problem

Consider a graph G(V, E).

Split G into S and T, maximizing �the number of edges between partitions.

NP-Hard in exact case!

Best approx. algorithm: SDP (classical but NOT local)

​

5

Image Credit: The TRACER Project

6 of 16

2. Brief review of QAOA

​

​

“Quantum Approximate Optimization Algorithm”

Start with , evolve times , then measure qubits

Choose evolution times (“angles”) to maximize

“Trotterized” Adiabatic: finds optimal as

6

7 of 16

2. Brief review of QAOA (cont.)

​

​

Expected value for :

​

Hard to analyze for general !

​

For MAXCUT: ( -local)

​

​

7

8 of 16

3. Local classical alternatives

“Threshold Algorithm”

  • Randomly assign each vertex a spin
  • If any vertex shares spin w/ neighbors, flip spin
  • Choose to maximize cut edges

1-local!

8

9 of 16

3. Local classical alternatives (cont.)

Threshold algorithm on D-regular, triangle-free graphs:

(vs QAOA1’s )

​

Hastings 2019: Lower bound not tight, wins vs QAOA1

​

9

10 of 16

​

​

10

11 of 16

3. Local classical alternatives (cont.)

​

“k-step Threshold Algorithm” (k-local!)

  • Randomly assign each vertex a spin
  • for :
  • If any vertex shares spin w/ neighbors, flip spin
  • Choose to maximize cut edges

11

12 of 16

3. Local classical alternatives (cont.)

​

​

On D-regular, girth > 5 graphs (i.e. no cycles of length < 6):

  • Simplified QAOA2 expression → found optimal “angles”
  • 2-step threshold algorithm wins vs QAOA2

​

2-step threshold , vs QAOA2

12

13 of 16

​

​

13

14 of 16

4. Open questions

When does QAOAp win vs all p-local classical algorithms?

What about on graphs with triangles?

Forthcoming work (for large-degree graphs):� threshold wins vs QAOA1 when triangles per edge

14

15 of 16

Thank you!

Kunal Marwaha

personal website: https://kunalmarwaha.com/about

marwahaha@berkeley.edu

16 of 16

Corner cases: Local classical wins for every D

​

“k-step Local Tensor Algorithm” (by Hastings; k-local)

Generic transformation; nonzero when

Update step:

  • For a few D, QAOA{1,2} wins vs {1,2}-step threshold
  • Instances of Local Tensor win vs QAOA in these cases

​

16