Session: Quantum Computing and Optimization
Chair: Reuben Tate
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: Advances in Warm-Started QAOA
Speaker: Reuben Tate
Abstract: Over a decade ago, the Quantum Approximate Optimization Algorithm (QAOA) was developed by Farhi et al. for solving certain problems in combinatorial optimization; the algorithm is a variational algorithm that involves the tuning of continuous circuit parameters. Five years ago, Tate et al. and Egger et al. independently developed a warm-start variant that involves using classically-obtained information to construct a warm-started initial quantum state. In this talk, we will go over recent developments in regards to Warm-Started QAOA from both a theoretical, empirical, and algorithmic-design perspective.
Talk 2: Investigating Alternative Metrics of Performance for QAOA
Speaker: Sean Feeney
Abstract: In modern optimization tasks, combinatorial optimization problems (COPs) are paramount in fields such as logistics, power systems, and circuit design. Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising quantum-classical variational approach for tackling these challenges, yet it often offers limited worst-case approximation guarantees. This work focuses on a recently introduced variant, Warm-Start QAOA, which leverages classical solutions as biased initial states in hopes of boosting the odds of finding high-quality solutions. We conduct an extensive numerical study of Warm-Start QAOA on 3-regular Max-Cut instances. Compared to theoretical lower bounds established by Tate et al. for single-round QAOA, our empirical results consistently indicate better performance across a range of tilt angles. However, this apparent advantage does not extend beyond the classical warm-start solution itself when the QAOA parameters are optimized solely by maximizing the expected objective value. This outcome highlights a pressing need to look beyond standard expectation-value metrics, as they may not capture the subtle elements required for surpassing strong classical baselines in practical settings. To address this gap, we introduce the Better Solution Probability (BSP) metric, which shifts the optimization target from maximizing expectation value performance to maximizing the probability of exceeding a given classical warm-start cut. Our simulations show that BSP-optimized Warm-Start QAOA frequently locates better solutions at non-trivial tilt angles, positions that outperform both the purely classical approach at zero tilt and standard QAOA at 90°, and does so with a non-vanishing probability. Notably, the BSP objective remains feasible to optimize in real-world conditions because it does not rely on a priori knowledge of the optimal solution. By exploring objective functions beyond expectation value, this study offers new insights into how hybrid quantum-classical methods can be enhanced for complex optimization tasks, paving the way for more robust algorithm design and a clearer path toward quantum advantage.
Talk 3: Quantum Hamiltonian Descent Algorithms for Nonlinear Optimization
Speaker: Yufan Zheng
Abstract: Nonlinear optimization is a vibrant field of research with wide-ranging applications in engineering and science. However, classical algorithms often struggle with local minima, limiting their effectiveness in tackling nonconvex problems. In this talk, we explore how quantum dynamics can be exploited to develop novel quantum optimization algorithms. Specifically, we introduce Quantum Hamiltonian Descent (QHD), a quantum optimization algorithm inspired by the connection between accelerated gradient descent and Hamiltonian mechanics. We will discuss the theoretical properties of QHD, including its global convergence in nonlinear and nonconvex optimization, along with strong empirical and theoretical evidence of its advantage over classical algorithms. Additionally, we will present an open-source implementation of the algorithm (named QHDOPT) and demonstrate its real-world applications.
