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

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 argued that quantum properties such as tunneling may give quantum algorithms advantage 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 instances that are considered classically hard. In this talk, I argue that the type of control strategy used by the optimization algorithm may be crucial to its success. Along with SA, QAO and QAOA, I will introduce a new, bang-bang version of simulated annealing, BBSA, and compare the performance of these algorithms on two well-studied problem instances from the literature. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the quasistatic analogues on the same instances. Lastly, I will show O(1)-depth QAOA protocols for a class of Hamming symmetric cost functions, and provide an accompanying physical picture.
 
Reference: https://arxiv.org/abs/1812.02746
 
Notes: Lunch served at 12:00 pm, talk at 12:10 pm.