Challenges and opportunities in quantum optimization

Abbas, A.; Ambainis, A.; Augustino, B.; Bartschi, A.; Buhrman, H.; Coffrin, C.; Cortiana, G.; Dunjko, V.; Egger, D. J.; Elmegreen, B. G.; Franco, N.; Fratini, F.; Fuller, B.; Gacon, J.; Gonciulea, C.; Gribling, S.; Gupta, S.; Hadfield, S.; Heese, R.; Kircher, G.; Kleinert, T.; Koch, T.; Korpas, G.; Lenk, S.; Marecek, J.; Markov, V.; Mazzola, G.; Mensa, S.; Mohseni, N.; Nannicini, G.; O'Meara, C.; Tapia, E. P.; Pokutta, S.; Proissl, M.; Rebentrost, P.; Sahin, E.; Symons, B. C. B.; Tornow, S.; Valls, V.; Woerner, S.; Wolf-Bauwens, M. L.; Yard, J.; Yarkoni, S.; Zechiel, D.; Zhuk, S.; Zoufal, C.

doi:10.1038/s42254-024-00770-9

This Review discusses quantum optimization, focusing on the potential of exact, approximate and heuristic methods, core algorithmic building blocks, problem classes and benchmarking metrics. The challenges for quantum optimization are considered, and next steps are suggested for progress towards achieving quantum advantage.

Challenges and opportunities in quantum optimization / Abbas, A.; Ambainis, A.; Augustino, B.; Bartschi, A.; Buhrman, H.; Coffrin, C.; Cortiana, G.; Dunjko, V.; Egger, D. J.; Elmegreen, B. G.; Franco, N.; Fratini, F.; Fuller, B.; Gacon, J.; Gonciulea, C.; Gribling, S.; Gupta, S.; Hadfield, S.; Heese, R.; Kircher, G.; Kleinert, T.; Koch, T.; Korpas, G.; Lenk, S.; Marecek, J.; Markov, V.; Mazzola, G.; Mensa, S.; Mohseni, N.; Nannicini, G.; O'Meara, C.; Tapia, E. P.; Pokutta, S.; Proissl, M.; Rebentrost, P.; Sahin, E.; Symons, B. C. B.; Tornow, S.; Valls, V.; Woerner, S.; Wolf-Bauwens, M. L.; Yard, J.; Yarkoni, S.; Zechiel, D.; Zhuk, S.; Zoufal, C.. - In: NATURE REVIEWS PHYSICS. - ISSN 2522-5820. - 6:12(2024), pp. 718-735. [10.1038/s42254-024-00770-9]