Georgia Institute of Technology College of Sciences

In recent years, there has been increased interest in using quantum computing for the purposes of solving problems in combinatorial optimization. No prior knowledge of quantum computing is necessary for this talk; in particular, the talk will be divided into three parts: (1) a gentle high-level introduction to the basics of quantum computing, (2) a general framework for solving combinatorial optimization problems with quantum computing (the Quantum Approximate Optimization Algorithm introduced by Farhi et al.), (3) and some recent results that my colleagues and I have found. Our group has looked at the Max-Cut problem and have developed a new quantum algorithm that utilizes classically-obtained warm-starts in order to improve upon already-existing quantum algorithms; this talk will discuss both theoretical and experimental results associated with our approach with our main results being that we obtain a 0.658-approximation for Max-Cut, our approach provably converges to the Max-Cut as a parameter (called the quantum circuit depth) increases, and (on small graphs) are approach is able to empirically beat the (classical) Goemans-Williamson algorithm at a relatively low quantum circuit-depth (i.e. using a small amount of quantum resources). This work is joint with Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta.