An introduction to variational quantum algorithms for combinatorial optimization problems
- URL: http://arxiv.org/abs/2212.11734v2
- Date: Sun, 11 Aug 2024 10:45:08 GMT
- Title: An introduction to variational quantum algorithms for combinatorial optimization problems
- Authors: Camille Grange, Michael Poss, Eric Bourreau,
- Abstract summary: This tutorial provides a mathematical description of the class of Variational Quantum Algorithms.
We introduce precisely the key aspects of these hybrid algorithms on the quantum side and the classical side.
We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Noisy intermediate-scale quantum computers (NISQ computers) are now readily available, motivating many researchers to experiment with Variational Quantum Algorithms (VQAs). Among them, the Quantum Approximate Optimization Algorithm (QAOA) is one of the most popular one studied by the combinatorial optimization community. In this tutorial, we provide a mathematical description of the class of Variational Quantum Algorithms, assuming no previous knowledge of quantum physics from the readers. We introduce precisely the key aspects of these hybrid algorithms on the quantum side (parametrized quantum circuit) and the classical side (guiding function, optimizer). We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions. Finally, we discuss the recent literature on QAOA, highlighting several research trends.
Related papers
- Hybrid quantum-classical approach for combinatorial problems at hadron colliders [7.2572969510173655]
We explore the potential of quantum algorithms to resolve the problems in particle physics experiments.
We consider top quark pair production in the fully hadronic channel at the Large Hadron Collider.
We show that the efficiency for selecting the correct pairing is greatly improved by utilizing quantum algorithms.
arXiv Detail & Related papers (2024-10-29T18:00:07Z) - Quantum Approximate Optimization: A Computational Intelligence Perspective [1.756184965281354]
We introduce quantum computing and variational quantum algorithms (VQAs)
We explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA)
We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms.
arXiv Detail & Related papers (2024-07-09T19:40:23Z) - 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) - 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks.
Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture.
We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
arXiv Detail & Related papers (2023-04-14T08:03:20Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers.
We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z) - A brief introduction to quantum algorithms [3.454865774480229]
We start from elucidating quantum parallelism, the basic framework of quantum algorithms and the difficulty of quantum algorithm design.
We then focus on a historical overview of progress in quantum algorithm research over the past three to four decades.
Finally, we clarify two common questions about the study of quantum algorithms, hoping to stimulate readers for further exploration.
arXiv Detail & Related papers (2022-12-21T03:00:25Z) - Parametrized Complexity of Quantum Inspired Algorithms [0.0]
Two promising areas of quantum algorithms are quantum machine learning and quantum optimization.
Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
arXiv Detail & Related papers (2021-12-22T06:19:36Z)
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.