# Quantum Optimization: Potential, Challenges, and the Path Forward

**Authors:** Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher  
**arXiv:** [2312.02279](https://arxiv.org/abs/2312.02279)  
**Date:** 2023-12-04  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2312.02279v1/

## Key points

- Recent advances in quantum computers have demonstrated their potential to solve complex problems beyond classical computers
- Quantum algorithms, particularly in optimization, have gained widespread interest
- This work draws on multiple approaches from computer science and physics to explore quantum optimization
- Difference between provably exact and heuristic settings is explained using computational complexity theory
- Core building blocks for quantum optimization algorithms are outlined
- Effects of scaling relevant problems on noisy quantum devices are discussed
- Clear metrics are proposed for benchmarking the performance of quantum optimization algorithms compared to classical techniques
- Finance and sustainability domains are highlighted as sources of real-world optimization problems for benchmarking and validation purposes
- Provides a comprehensive overview of quantum optimization by integrating various algorithmic approaches and addressing key challenges

## Summary

Recent advances in quantum computers have demonstrated their potential to solve complex problems that are beyond the capabilities of classical computers. This has sparked widespread interest in quantum algorithms, particularly in the field of optimization. To address this fragmentation and explore the potential of quantum optimization, this work draws on multiple approaches from computer science and physics. It begins by explaining the difference between provably exact and heuristic settings using computational complexity theory. This highlights where quantum advantage is possible in each context. The core building blocks for quantum optimization algorithms are then outlined, providing a foundation for defining prominent problem classes and identifying key open questions that can advance the field. Additionally, the effects of scaling relevant problems on noisy quantum devices are discussed in detail. Benchmarking plays a crucial role in evaluating the performance of quantum optimization algorithms compared to classical techniques. To facilitate appropriate comparisons, clear metrics are proposed for benchmarking purposes. Furthermore, two domains - finance and sustainability - are highlighted as rich sources of real-world optimization problems that can be used to benchmark and validate the potential impact of quantum optimization. Overall, this work provides a comprehensive overview of quantum optimization by integrating various algorithmic approaches and addressing key challenges. By exploring different problem classes and proposing benchmarking metrics, it paves the way for further advancements in this rapidly evolving field.