Quantum Optimization From a Computer Science Perspective
MetadataShow full item record
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.
Jacob, Darryl Cherian (2020). Quantum Optimization From a Computer Science Perspective. Undergraduate Research Scholars Program. Available electronically from