Guarantees on Warm-Started QAOA: Single-Round Approximation Ratios for 3-Regular MAXCUT and Higher-Round Scaling Limits ...

We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts wh...

Full description

Bibliographic Details
Main Authors: Tate, Reuben, Eidenbenz, Stephan
Format: Report
Language:unknown
Published: arXiv 2024
Subjects:
Quantum Physics quant-ph
Data Structures and Algorithms cs.DS
Emerging Technologies cs.ET
Combinatorics math.CO
Optimization and Control math.OC
FOS Physical sciences
FOS Computer and information sciences
FOS Mathematics
South Pole
South pole
Online Access:https://dx.doi.org/10.48550/arxiv.2402.12631
https://arxiv.org/abs/2402.12631
Description
Summary:We generalize Farhi et al.'s 0.6924-approximation result technique of the Max-Cut Quantum Approximate Optimization Algorithm (QAOA) on 3-regular graphs to obtain provable lower bounds on the approximation ratio for warm-started QAOA. Given an initialization angle $θ$, we consider warm-starts where the initial state is a product state where each qubit position is angle $θ$ away from either the north or south pole of the Bloch sphere; of the two possible qubit positions the position of each qubit is decided by some classically obtained cut encoded as a bitstring $b$. We illustrate through plots how the properties of $b$ and the initialization angle $θ$ influence the bound on the approximation ratios of warm-started QAOA. We consider various classical algorithms (and the cuts they produce which we use to generate the warm-start). Our results strongly suggest that there does not exist any choice of initialization angle that yields a (worst-case) approximation ratio that simultaneously beats standard QAOA and the ...

Similar Items