Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
<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:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math>. We analyze QAOA<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi /><mml:mn>2</mml:mn></mml:msub></mml:math> for the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">maximum cut problem</mml:mtext></mml:mrow></mml:math> (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi></mml:math>-regular graph of girth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>></mml:mo><mml:mn>5</mml:mn></mml:math> (i.e. without triangles, squares, or pentagons).We show that for all degrees <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:math> and every <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>D</mml:mi></mml:math>-regular graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math> of girth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>></mml:mo><mml:mn>5</mml:mn></mml:math>, QAOA<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi /><mml:mn>2</mml:mn></mml:msub></mml:math> has a larger expected cut fraction than QAOA<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi /><mml:mn>1</mml:mn></mml:msub></mml:math> on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math>. However, we also show that there exists a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2</mml:mn></mml:math>-local randomized <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">classical</mml:mtext></mml:mrow></mml:math> algorithm <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi></mml:math> such that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>A</mml:mi></mml:math> has a larger expected cut fraction than QAOA<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi /><mml:mn>2</mml:mn></mml:msub></mml:math> on all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math>. This supports our conjecture that for every constant <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi></mml:math>, there exists a local classical MAX-CUT algorithm that performs as well as 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> on all graphs.</jats:p>