Optimal Protocols in Quantum Annealing and Quantum Approximate Optimization Algorithm Problems

Quantum computers seek to use the power of quantum mechanics to solve computational tasks in ways fundamentally different from those of classical computers. Quantum advantage has already been demonstrated experimentally, but it remains to be seen what useful applications are possible on small, noisy near-term quantum computers. Analog quantum algorithms provide one possible route to such near-term utility since they have some inherent noise-resistance and are workable on small devices. Quantum Annealing (QA), Quantum Adiabatic Optimization (QAO), and the Quantum Approximate Optimization Algorithm (QAOA) all form a class of analog quantum algorithms where the system is switched between two configurations or Hamiltonians in order to steer the state of the system into a desired target. Which algorithm is more effective has remained unclear. We apply the framework of optimal control theory to derive the form of the optimal annealing procedure. Furthermore, we connect the form of this optimal procedure back to QAO and QAOA, showing that in the limit of short times, the optimal procedure is well approximated by QAOA. In the long time limit, this optimal procedure begins to look locally adiabatic, with a form similar to an optimized annealing schedule.