Southwest Quantum Information and Technology

Bang-bang control as a design principle for classical and quantum optimization algorithms

Presenting Author: Aniruddha Bapat, University of Maryland Joint Quantum Institute
Contributing Author(s): Stephen Jordan

Physically motivated classical heuristic optimization algorithms such as simulated annealing (SA) treat the objective function as an energy landscape, and allow walkers to escape local minima. It has been speculated that quantum properties such as tunneling may give quantum algorithms the upper hand in finding ground states of vast, rugged cost landscapes. Indeed, the Quantum Adiabatic Algorithm (QAO) and the recent Quantum Approximate Optimization Algorithm (QAOA) have shown promising results on various problem instance that are considered classically hard. Here, we argue that the type of \emph{control} strategy used by the optimization algorithm may be crucial to its success, both classically and quantumly. Along with SA, QAO and QAOA, we define a new, bang-bang version of simulated annealing, BBSA, and study the performance of these algorithms on two well-studied problem instances from the literature. Rather than a quantum advantage, we find evidence for a design advantage. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the annealing analogues on the same instances. Lastly, we construct O(1) time QAOA protocols for a large class of symmetric cost functions, and provide an accompanying physical picture.

Read this article online: https://arxiv.org/abs/1812.02746

(Session 9c : Monday from 4:45pm - 5:15pm)