Challenges and Opportunities in Quantum Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917839568371712 |
|---|---|
| author | Abbas, Amira Ambainis, Andris Augustino, Brandon Bärtschi, Andreas Buhrman, Harry Coffrin, Carleton Cortiana, Giorgio Dunjko, Vedran Egger, Daniel J. Elmegreen, Bruce G. Franco, Nicola Fratini, Filippo Fuller, Bryce Gacon, Julien Gonciulea, Constantin Gribling, Sander Gupta, Swati Hadfield, Stuart Heese, Raoul Kircher, Gerhard Kleinert, Thomas Koch, Thorsten Korpas, Georgios Lenk, Steve Marecek, Jakub Markov, Vanio Mazzola, Guglielmo Mensa, Stefano Mohseni, Naeimeh Nannicini, Giacomo O'Meara, Corey Tapia, Elena Peña Pokutta, Sebastian Proissl, Manuel Rebentrost, Patrick Sahin, Emre Symons, Benjamin C. B. Tornow, Sabine Valls, Victor Woerner, Stefan Wolf-Bauwens, Mira L. Yard, Jon Yarkoni, Sheir Zechiel, Dirk Zhuk, Sergiy Zoufal, Christa |
| author_facet | Abbas, Amira Ambainis, Andris Augustino, Brandon Bärtschi, Andreas Buhrman, Harry Coffrin, Carleton Cortiana, Giorgio Dunjko, Vedran Egger, Daniel J. Elmegreen, Bruce G. Franco, Nicola Fratini, Filippo Fuller, Bryce Gacon, Julien Gonciulea, Constantin Gribling, Sander Gupta, Swati Hadfield, Stuart Heese, Raoul Kircher, Gerhard Kleinert, Thomas Koch, Thorsten Korpas, Georgios Lenk, Steve Marecek, Jakub Markov, Vanio Mazzola, Guglielmo Mensa, Stefano Mohseni, Naeimeh Nannicini, Giacomo O'Meara, Corey Tapia, Elena Peña Pokutta, Sebastian Proissl, Manuel Rebentrost, Patrick Sahin, Emre Symons, Benjamin C. B. Tornow, Sabine Valls, Victor Woerner, Stefan Wolf-Bauwens, Mira L. Yard, Jon Yarkoni, Sheir Zechiel, Dirk Zhuk, Sergiy Zoufal, Christa |
| contents | 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 different approaches for major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_02279 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Challenges and Opportunities in Quantum Optimization Abbas, Amira Ambainis, Andris Augustino, Brandon Bärtschi, Andreas Buhrman, Harry Coffrin, Carleton Cortiana, Giorgio Dunjko, Vedran Egger, Daniel J. Elmegreen, Bruce G. Franco, Nicola Fratini, Filippo Fuller, Bryce Gacon, Julien Gonciulea, Constantin Gribling, Sander Gupta, Swati Hadfield, Stuart Heese, Raoul Kircher, Gerhard Kleinert, Thomas Koch, Thorsten Korpas, Georgios Lenk, Steve Marecek, Jakub Markov, Vanio Mazzola, Guglielmo Mensa, Stefano Mohseni, Naeimeh Nannicini, Giacomo O'Meara, Corey Tapia, Elena Peña Pokutta, Sebastian Proissl, Manuel Rebentrost, Patrick Sahin, Emre Symons, Benjamin C. B. Tornow, Sabine Valls, Victor Woerner, Stefan Wolf-Bauwens, Mira L. Yard, Jon Yarkoni, Sheir Zechiel, Dirk Zhuk, Sergiy Zoufal, Christa Quantum Physics Optimization and Control 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 different approaches for major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions. 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. |
| title | Challenges and Opportunities in Quantum Optimization |
| topic | Quantum Physics Optimization and Control |
| url | https://arxiv.org/abs/2312.02279 |