  Recent advances in quantum computers are demonstrating the ability to solve
problems at a scale beyond brute force classical simulation. As such, a
widespread interest in quantum algorithms has developed in many areas, with
optimization being one of the most pronounced domains. Across computer science
and physics, there are a number of algorithmic approaches, often with little
linkage. This is further complicated by the fragmented nature of the field of
mathematical optimization, where major classes of optimization problems, such
as combinatorial optimization, convex optimization, non-convex optimization,
and stochastic extensions, have devoted communities. With these aspects in
mind, this work draws on multiple approaches to study quantum optimization.
Provably exact versus heuristic settings are first explained using
computational complexity theory - highlighting where quantum advantage is
possible in each context. Then, the core building blocks for quantum
optimization algorithms are outlined to subsequently define prominent problem
classes and identify key open questions that, if answered, will advance the
field. The effects of scaling relevant problems on noisy quantum devices are
also outlined in detail, alongside meaningful benchmarking problems. We
underscore the importance of benchmarking by proposing clear metrics to conduct
appropriate comparisons with classical optimization techniques. Lastly, we
highlight two domains - finance and sustainability - as rich sources of
optimization problems that could be used to benchmark, and eventually validate,
the potential real-world impact of quantum optimization.
