Final doctoral examination and defense of dissertation of Reuben Tate, April 12, 2023
Thesis Title: Classical Optimization to Improve Variational Quantum Algorithms
Link to Thesis draft: https://www.dropbox.com/sh/wgmap44k1tmkcna/AABEFKfPU7Yv8ejNqnHk1_vDa?dl=0
Date: April 12, 2023
Time: 12:00PM (EST)
Location: TBD
Committee:
Dr. Gregory Mohler, Cybersecurity, Information Protection, and Hardware Evaluation Research, Georgia Tech Research Institute
Dr. Grigoriy Blekherman, School of Mathematics, Georgia Institute of Technology
Dr. Stuart Hadfield, Quantum Artificial Intelligence Laboratory, National Aeronautics and Space Administration
Dr. David Gamarnik, Operations Research, Massachusetts Institute of Technology
Advisor: Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology
Reader: Dr. Gregory Mohler, Cybersecurity, Information Protection, and Hardware Evaluation Research, Georgia Tech Research Institute
Abstract:
There is growing interest in utilizing near-term quantum technology to solve challenging problems in combinatorial optimization. Recently, in 2014, Farhi et. al proposed a general Quantum Approximate Optimization Algorithm (QAOA) to obtain solutions to NP-hard problems, and showed that this algorithm converges to the optimal solutions under the adiabatic limit, or in other words, when the circuit depth of QAOA goes to infinity. One way to demonstrate quantum advantage on near-term quantum devices is then to show that QAOA can significantly outperform classical algorithms even when parameterized for finite circuit depth. This thesis makes progress towards this challenging goal by bridging the theories of classical and quantum optimization to develop fast hybrid QAOA solvers for the Max-Cut problem.
First, we study graph instances that are "challenging" to solve classically, to better understand where quantum algorithms might have an advantage over classical methods. Next, we introduce the notion of "warm-starting" in quantum optimization by using the SDP relaxation for Max-Cut to initialize the starting state for QAOA. We show that this variant "QAOA-warm" outperforms the standard QAOA on lower circuit depths in solution quality and training time, and has an approximation ratio of 0.658 and 0.585 for rank-2 and rank-3 SDP-based warm-starts for graphs with non-negative edge weights at p=0. However, unlike the standard QAOA, we find that the performance of QAOA-warm plateaus and does not converge to the Max-Cut with increased circuit depth.
Next, we introduce a variant “QAOA-warmest” that combines warm-starting with a modification of the circuit of QAOA so that convergence to Max-Cut under the adiabatic limit is retained. Our numerical simulations and hardware experiments with QAOA-warmest yield higher quality cuts (compared to standard QAOA, QAOA-warm, and GW), and fast convergence to Max-Cut at low circuit depths. Finally, we discuss extensions of QAOA to handle constrained optimization problems using another way of warm-starting, where ancillary qubits are used to generate initial quantum states whose bitstring distributions match those obtained by classical local-search algorithms.
