An introduction to variational quantum algorithms for combinatorial optimization problems

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.

References in corpus (23)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Improving Variational Quantum Optimization using CVaR
• Geometry of entangled states, Bloch spheres and Hopf fibrations
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Filtering variational quantum algorithms for combinatorial optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Hybrid quantum-classical algorithms for approximate graph coloring
• Empirical performance bounds for quantum approximate optimization
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles

Cited by in corpus (5)

• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Pulse family optimization for parametrized quantum gates using spectral clustering
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Weighted Approximate Quantum Natural Gradient for Variational Quantum Eigensolver
• Interpolation-based coordinate descent method for parameterized quantum circuits