ADAPT-QAOA: an adaptive quantum algorithm for optimization

In today’s quantum devices, decoherence sets limits on the circuit depth. Quantum-classical hybrid variational algorithms, which bypass the need for long quantum circuits by alternating between quantum computation and classical optimization, show promise for providing advantage over purely classical computing. In these algorithms, we need a suitably chosen ansatz to ensure the correct solution is reached or well approximated. To that end, an Adaptive Derivative-Assembled Problem-Tailored (ADAPT) protocol has been developed to tailor an ansatz to the problem. First proposed in the context of the variational quantum eigensolver [1], the ADAPT protocol constructs the ansatz iteratively, leading to a shallow quantum circuit and fast convergence [1,2]. One can apply the same approach to the quantum approximate optimization algorithm (QAOA), which was shown to significantly improve convergence of QAOA [3]. In this talk I will review the ADAPT approach, emphasizing its application to QAOA. Specifically, I will discuss the performance of ADAPT-QAOA in solving the Max-Cut problem, and I will examine the intermediate steps of ADAPT-QAOA and explore the role entanglement plays in this algorithm. [1] H. R. Grimsley, S. E. Economou, E. Barnes, N. J. Mayhall. Nat Commun 10, 3007 (2019). [2] H. L. Tang, V.O. Shkolnikov, G. S. Barron, H. R. Grimsley, N. J. Mayhall, E. Barnes, S. E. Economou. PRX QUANTUM 2, 020310 (2021). [3] L. Zhu, H. L. Tang, G. S. Barron, F. A. Calderon-Vargas, N. J. Mayhall, E. Barnes, S. E. Economou. arXiv:2005.10258.