Bridging Classical and Quantum Optimization: New Directions for QAOA and Max-Cut

Instructor : Jai Moondra
Affiliation : Georgia Institute of Technology, USA
Abstract : The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for realizing quantum advantage in combinatorial optimization problems such as Max-Cut. While its theoretical promise is exciting, practical challenges such as noise, circuit complexity, and hardware constraints currently limit its utility on Noisy Intermediate-Scale Quantum (NISQ) devices. In this talk, I will present recent advances in addressing these challenges using classical algorithmic tools.
In the first half of the talk, I will briefly review standard QAOA for Max-Cut before introducing custom mixers — modified circuits designed to warm-start QAOA by exploiting the underlying graph structure. Using warm-starts based on the Goemans-Williamson SDP, we establish approximation guarantees for these mixers and demonstrate their convergence to optimal solutions. In the second half, I will address the challenge of physically implementing QAOA circuits and present the Union-of-Stars algorithm for their construction on trapped-ion quantum hardware. This algorithm, combined with classical tools like graph sparsification and decomposition, reduces overall circuit noise and represents the first non-trivial construction in this setting. Throughout the talk, I will highlight both theoretical and empirical results. Based on joint work with Bryan Gard, Swati Gupta, Creston D. Herold, Philip C. Lotshaw, Greg Mohler, Joel Rajakumar, and Reuben Tate.

Short bio : Jai Moondra is a fourth-year PhD student at the School of Computer Science at Georgia Tech, advised by Dr. Swati Gupta (MIT) and Dr. Mohit Singh (Georgia Tech). He finished his BTech in Computer Science and Engineering from IIT Delhi in 2019. His research broadly focuses on discrete optimization and its applications to algorithmic fairness, quantum computing, and machine learning.