The quantum approximate optimization algorithm (QAOA) is a variational algorithm for binary optimization on quantum computers. This algorithm has emerged as one of the leading candidates for quantum advantage on near-term quantum computers, but the power of the algorithm is not fully understood. However, recent work exploring the ability of the QAOA to approximate the ground state of spin glass models has allowed a rigorous understanding of the average-case performance of the algorithm.
In this talk, I’ll provide an overview of the QAOA, discuss the current challenges associated with the algorithm, and provide an overview of some recent rigorous results on the QAOA applied to spin-glass Hamiltonians. Along the way, we’ll discuss adiabatic quantum computing, classical optimization, and the problems associated with optimizing variational algorithms.
This talk will be based on the papers:
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000). Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106.
Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
Brandao, F. G., Broughton, M., Farhi, E., Gutmann, S., & Neven, H. (2018). For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances. arXiv preprint arXiv:1812.04170.
Farhi, E., Goldstone, J., Gutmann, S., & Zhou, L. (2019). The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187.
Claes, J., & van Dam, W. (2021). Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size. arXiv preprint arXiv:2102.12043.
The Zoom link will be sent to the Graduate Student and PDRA mailing lists. If you are not on one of those lists and are interested in attending, please email Mark Hirsbrunner at hrsbrnn2@illinois.edu for the link.
