A practitioner’s guide to quantum algorithms for optimisation problems

DOI10.1088/1751-8121/AD00F0MaRDI QIDQ6063352zbMATH OpenFDO

Authors

Publication date 7 November 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2305.07323

zbMATH Keywords

combinatorial optimisationgate-based quantum computingquantum alternating operator ansatzquantum approximate optimisation algorithmquantum optimisation

Mathematics Subject Classification ID

Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Regularization by noise (60H50) Generalized linear models (logistic models) (62J12) Quantum algorithms and complexity in the theory of computing (68Q12) Mathematical modeling or simulation for problems pertaining to quantum theory (81-10) Quantum gates (81P65) Quantum computation (81P68)

Abstract: Quantum computing is gaining popularity across a wide range of scientific disciplines due to its potential to solve long-standing computational problems that are considered intractable with classical computers. One promising area where quantum computing has potential is in the speed-up of NP-hard optimisation problems that are common in industrial areas such as logistics and finance. Newcomers to the field of quantum computing who are interested in using this technology to solve optimisation problems do not have an easily accessible source of information on the current capabilities of quantum computers and algorithms. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques and their practical application, focusing on their near-term potential for noisy intermediate scale quantum devices. Two main paradigms for quantum hardware are then discussed: quantum annealing and gate-based quantum computing. While quantum annealers are effective for some optimisation problems, they have limitations and cannot be used for universal quantum computation. In contrast, gate-based quantum computers offer the potential for universal quantum computation, but they face challenges with hardware limitations and accurate gate implementation. The paper provides a detailed mathematical discussion with references to key works in the field, as well as a more practical discussion with relevant examples. The most popular techniques for quantum optimisation on gate-based quantum computers, the quantum approximate optimisation (QAO) algorithm and the quantum alternating operator ansatz (QAOA) framework, are discussed in detail. The paper concludes with a discussion of the challenges facing quantum optimisation techniques and the need for further research and development to identify new, effective methods for achieving quantum advantage.

Recommendations

• QUANTUM ALGORITHMS FOR OPTIMIZATION USING ASYMPTOTIC QUANTUM SEARCH
• An introduction to variational quantum algorithms for combinatorial optimization problems
• scientific article; zbMATH DE number 2013817
• Quantum optimization
• A panoply of quantum algorithms
• The parallel quantum algorithm for the class of optimization
• An Introduction to Quantum Algorithms: A Physicist’s Perspective
• Concise Guide to Quantum Computing
• Solving a class of continuous global optimization problems using quantum algorithms
• Quantum algorithm design: techniques and applications

Cites work

• Beating the random assignment on constraint satisfaction problems of bounded degree
• Benchmarking the quantum approximate optimization algorithm
• Classical symmetries and the quantum approximate optimization algorithm
• Colloquium: Quantum annealing and analog quantum computation
• Combinatorial optimization. Theory and algorithms
• Complexity of stoquastic frustration-free Hamiltonians
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• scientific article; zbMATH DE number 4002053 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimization using quantum mechanics: quantum annealing through adiabatic evolution
• Ottimizzazione Combinatoria
• Quantum computations: algorithms and error correction
• The multiplicative weights update method: a meta-algorithm and applications
• The theory of variational hybrid quantum-classical algorithms
• The variational quantum eigensolver: a review of methods and best practices
• The vehicle routing problem

Cited in

(3)

• Book review of: R. J. Lipton and K. W. Regan, Quantum algorithms via linear algebra. A primer
• On post-processing the results of quantum optimizers
• Loss-aware state space geometry for quantum variational algorithms

This page was built for publication: A practitioner’s guide to quantum algorithms for optimisation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063352)