Quantum Optimization From a Computer Science Perspective

Optimization problems are ubiquitous in but not limited to the sciences, engineering, and applied mathematics. Examples range from the fastest way USPS can route packages through a delivery network to the best way an autonomous vehicle can navigate through a given traffic environment. Classical optimization algorithms dominate the way we solve these problems. However, with the rapid advance of quantum computers, we are looking at novel, quantum-inspired ways of solving old problems to achieve some speedup over classical algorithms. Specifically, we are looking at the Quantum Approximate Optimization Algorithm (QAOA). We show that QAOA provides a tunable, optimization algorithm whose quantum circuit grows linearly with the number of constraints for MAXSAT, an NP-complete problem