Quantum Optimization: Potential, Challenges, and the Path Forward
- URL: http://arxiv.org/abs/2312.02279v1
- Date: Mon, 4 Dec 2023 19:00:44 GMT
- Title: Quantum Optimization: Potential, Challenges, and the Path Forward
- Authors: Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B\"artschi,
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, Thomas Kleinert, Thorsten Koch,
Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola,
Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O'Meara, Elena
Pe\~na Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre
Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner,
Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk,
Christa Zoufal
- Abstract summary: Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation.
Widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains.
- Score: 14.836100818054588
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational
Quantum Systems [65.268245109828]
We compare the performance of classicals across a series of partially-randomized tasks.
We focus on local zeroth-orders due to their generally favorable performance and query-efficiency on quantum systems.
arXiv Detail & Related papers (2023-10-14T02:13:26Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems via computational learning theory [5.907281242647458]
We prove that quantum computers feature an in-principle super-polynomial advantage over classical computers in approximating solutions to optimization problems.
The core of the quantum advantage is ultimately borrowed from Shor's quantum algorithm for factoring.
arXiv Detail & Related papers (2022-12-16T19:01:04Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device.
We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.
This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
arXiv Detail & Related papers (2022-09-07T18:01:01Z) - Quantum topology optimization of ground structures using noisy
intermediate-scale quantum devices [8.325359814939517]
We study the usage of quantum computers as a potential solution to topology optimization problems.
Several experiments, including a real device experiment, show that the proposed method successfully obtained the optimal configurations.
arXiv Detail & Related papers (2022-07-19T10:39:28Z) - Classically-Boosted Quantum Optimization Algorithm [0.0]
We explore a natural approach to leveraging existing classical techniques to enhance quantum optimization.
Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions.
We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
arXiv Detail & Related papers (2022-03-25T23:36:14Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Quantum variational optimization: The role of entanglement and problem
hardness [0.0]
We study the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem.
Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology.
We find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions.
arXiv Detail & Related papers (2021-03-26T14:06:54Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.