Quantum Optimization From a Computer Science Perspective
Abstract
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.
Citation
Jacob, Darryl Cherian (2020). Quantum Optimization From a Computer Science Perspective. Undergraduate Research Scholars Program. Available electronically from https : / /hdl .handle .net /1969 .1 /188484.