A Review on Quantum Approximate Optimization Algorithm and its Variants
- URL: http://arxiv.org/abs/2306.09198v2
- Date: Mon, 26 Jun 2023 19:41:01 GMT
- Title: A Review on Quantum Approximate Optimization Algorithm and its Variants
- Authors: Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao
Li, Komal Pandya, and Alessandro Summer
- Abstract summary: 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.
- Score: 47.89542334125886
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising
variational quantum algorithm that aims to solve combinatorial optimization
problems that are classically intractable. This comprehensive review offers an
overview of the current state of QAOA, encompassing its performance analysis in
diverse scenarios, its applicability across various problem instances, and
considerations of hardware-specific challenges such as error susceptibility and
noise resilience. Additionally, we conduct a comparative study of selected QAOA
extensions and variants, while exploring future prospects and directions for
the algorithm. We aim to provide insights into key questions about the
algorithm, such as whether it can outperform classical algorithms and under
what circumstances it should be used. Towards this goal, we offer specific
practical points in a form of a short guide. Keywords: Quantum Approximate
Optimization Algorithm (QAOA), Variational Quantum Algorithms (VQAs), Quantum
Optimization, Combinatorial Optimization Problems, NISQ Algorithms
Related papers
- Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Benchmarking Metaheuristic-Integrated QAOA against Quantum Annealing [0.0]
The study provides insights into the strengths and limitations of both Quantum Annealing and metaheuristic-integrated QAOA across different problem domains.
The findings suggest that the hybrid approach can leverage classical optimization strategies to enhance the solution quality and convergence speed of QAOA.
arXiv Detail & Related papers (2023-09-28T18:55:22Z) - Benchmarking Adaptative Variational Quantum Algorithms on QUBO Instances [0.0]
Adaptative VQAs dynamically modify the circuit structure by adding and removing, and optimize their parameters during the training.
We analyze three Adaptative VQAs: Variational Quantum Eigensolver (EVQE), Variable Ansatz (VAns), and Random Adapt-VQE (RA-VQE), a random approach we introduce as a baseline.
Our analysis sets benchmarks for Adaptative VQAs designed for near-term quantum devices.
arXiv Detail & Related papers (2023-08-03T14:39:02Z) - A Comparative Study On Solving Optimization Problems With Exponentially
Fewer Qubits [0.0]
We evaluate and improve an algorithm based on Variational Quantum Eigensolver (VQE)
We highlight the numerical instabilities generated by encoding the problem into the variational ansatz.
We propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better objective.
arXiv Detail & Related papers (2022-10-21T08:54:12Z) - Iteration Complexity of Variational Quantum Algorithms [5.684122393859336]
We argue that noise makes evaluations of the objective function via quantum circuits biased.
We derive the missing guarantees and find that the rate of convergence is unaffected.
arXiv Detail & Related papers (2022-09-21T19:18:41Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework.
A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
arXiv Detail & Related papers (2022-05-03T07:54:56Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - 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) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms.
We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
arXiv Detail & Related papers (2020-01-29T09:40:58Z) - To quantum or not to quantum: towards algorithm selection in near-term
quantum optimization [0.0]
We study the problem of detecting problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm.
We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage.
arXiv Detail & Related papers (2020-01-22T20:42:02Z)
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.