Quantum Optimization

The rapid development of quantum computing technology is opening up possibilities for solving problems at a scale beyond brute force classical simulation. As a result, widespread interest in quantum algorithms has emerged across many areas, with optimization being one of the most prominent domains. Here, we focus on the application of quantum algorithms to various optimization problems. We explore provably exact, provably approximate, and heuristic approaches to quantum optimization, leveraging insights from computational complexity theory to clarify where quantum advantage is most likely to be realized. Key algorithmic building blocks are identified, and core problem classes are defined. Additionally, benchmarking of optimization algorithms is a central focus, with the goal of establishing clear metrics for comparing quantum and classical optimization approaches and ultimately demonstrating a quantum advantage in optimization.