2024/02/20 by Reuben Tate, Stephan Eidenbenz, Tate, Reuben +1
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Approximation and Integration #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2402.12631
openalex publication_date 2024/02/20 · openalex created_date 2024/02/22 · openalex updated_date 2026/07/28
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 classical algorithm used to create the warm-start. Additionally, we show that at θ=60^∘, 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.