Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
<|reference_start|>Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$: 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 $\theta$, we consider warm-starts where the initial state is a product state where each qubit position is angle $\theta$ 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 $\theta$ 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 classical algorithm used to create the warm-start.   Additionally, we show that at $\theta=60^\circ$, warm-started QAOA is able to (effectively) recover the cut used to generate the warm-start, thus suggesting that in practice, this value could be a promising starting angle to explore alternate solutions in a heuristic fashion.<|reference_end|>
@article{tate2024theoretical,
    title={Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular
  Max-Cut Instances at Depth $p=1$},
    author={Reuben Tate and Stephan Eidenbenz},
    journal={arXiv preprint arXiv:2402.12631},
    year={2024},
    number={LA-UR-24-21477},
    archivePrefix={arXiv},
    eprint={2402.12631},
    primaryClass={quant-ph cs.DS cs.ET math.CO math.OC}
}