A Review on Quantum Approximate Optimization Algorithm and its Variants

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

67 pages, 9 figures, 9 tables; version 2 -- added more discussions and practical guides

References in corpus (76)

• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• The Variational Quantum Eigensolver: a review of methods and best practices
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Warm-starting quantum optimization
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Exponential Error Suppression for Near-Term Quantum Devices
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Performance comparison of optimization methods on variational quantum algorithms
• MAXCUT QAOA performance guarantees for p >1
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Hybrid quantum-classical algorithms for approximate graph coloring
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Evaluating the noise resilience of variational quantum algorithms
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Feedback-based quantum optimization
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Constrained mixers for the quantum approximate optimization algorithm
• Crosstalk analysis for single-qubit and two-qubit gates in spin qubit arrays
• Graph neural network initialisation of quantum approximate optimisation
• Error propagation in NISQ devices for solving classical optimization problems
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Quantum optimization via four-body Rydberg gates
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Experimental benchmarking of an automated deterministic error suppression workflow for quantum algorithms
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Quantum Image Segmentation Based on Grayscale Morphology
• Quantum Computing Techniques for Multi-Knapsack Problems
• Warm-Starting and Quantum Computing: A Systematic Mapping Study
• Analytical Framework for Quantum Alternating Operator Ansätze
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
• Shortcuts to Quantum Approximate Optimization Algorithm
• Optimizing Ansatz Design in QAOA for Max-cut
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Fermionic Quantum Approximate Optimization Algorithm
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• Reinforcement Learning with Quantum Variational Circuits
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Ability of error correlations to improve the performance of variational quantum algorithms
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Investigating Quantum Approximate Optimization Algorithms under Bang-bang Protocols
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit
• Optimizing Quantum Algorithms on Bipotent Architectures
• The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings
• QPack Scores: Quantitative performance metrics for application-oriented quantum computer benchmarking
• Limitations of variational quantum algorithms: a quantum optimal transport approach
• Quantum Approximate Optimization Algorithm with Cat Qubits
• Relating the multi-angle quantum approximate optimization algorithm and continuous-time quantum walks on dynamic graphs

Cited by in corpus (98)

• Introduction to Theoretical and Experimental aspects of Quantum Optimal Control
• Cyclic solid-state quantum battery: Thermodynamic characterization and quantum hardware simulation
• Quantum algorithms for scientific computing
• Quantum Optimization Methods for Satellite Mission Planning
• Pauli path simulations of noisy quantum circuits beyond average case
• Blockchain Security Risk Assessment in Quantum Era, Migration Strategies and Proactive Defense
• Quantum Approximate Optimization Algorithm for Test Case Optimization
• Quantum computing through the lens of control: A tutorial introduction
• Performance Analysis of Multi-Angle QAOA for p > 1
• Combinatorial Optimization with Quantum Computers
• Variational Quantum Multi-Objective Optimization
• Low-depth Clifford circuits approximately solve MaxCut
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Synergistic Dynamical Decoupling and Circuit Design for Enhanced Algorithm Performance on Near-Term Quantum Devices
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Photonic counterdiabatic quantum optimization algorithm
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Symmetric quantum states: a review of recent progress
• Scalable circuit depth reduction in feedback-based quantum optimization with a quadratic approximation
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Quantum circuit compilation with quantum computers
• Quantum Dynamics Simulation of the Advection-Diffusion Equation
• On the Baltimore Light RailLink into the quantum future
• Optimal depth and a novel approach to variational quantum process tomography
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• SWAP-less Implementation of Quantum Algorithms
• Demonstration of Hardware Efficient Photonic Variational Quantum Algorithm
• Noise-aware variational eigensolvers: a dissipative route for lattice gauge theories
• Hardware-level Interfaces for Hybrid Quantum-Classical Computing Systems
• Extending the Q-score to an Application-level Quantum Metric Framework
• Introduction to Quantum Error Correction with Stabilizer Codes
• Optimization via Quantum Preconditioning
• Quantum ergodicity and scrambling in quantum annealers
• Inequality constraints in variational quantum circuits with qudits
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Path Matters: Industrial Data Meet Quantum Optimization
• Q-gen: A Parameterized Quantum Circuit Generator
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• QSteed: A Resource-Virtualized and Hardware-Aware Quantum Compilation Framework for Real Quantum Computing Processors
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• On the Differential Topology of Expressivity of Parameterized Quantum Circuits
• Atom Cavity Encoding for NP-Complete Problems
• Subsampling Factorization Machine Annealing
• Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
• Transpiling quantum assembly language circuits to a qudit form
• Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Validity condition for high-fidelity Digitized Quantum Annealing
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Protected quantum gates using qubit doublons in dynamical optical lattices
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• A Quantum Approach for Optimal Transient Control in Network-Based Epidemic Models
• Improving Parameter Training for VQEs by Sequential Hamiltonian Assembly
• The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions
• QTIS: A QAOA-Based Quantum Time Interval Scheduler
• Efficient quantum algorithm for weighted partial sums and numerical integration
• Symmetry-enhanced Counterdiabatic Quantum Algorithm for Qudits
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Hamiltonian Expressibility for Ansatz Selection in Variational Quantum Algorithms
• Large-scale portfolio optimization with variational neural annealing
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Expediting quantum state transfer through the long-range extended XY model
• Interference and Measurement: Changing amplitude phase information to amplitude magnitude information
• Extended parameter shift rules with minimal derivative variance for parameterized quantum circuits
• Pangenome-guided sequence assembly via binary optimisation
• Noise-Aware Circuit Compilations for a Continuously Parameterized Two-Qubit Gateset
• Standardization of Multi-Objective QUBOs
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Qubit-efficient quantum combinatorial optimization solver
• Electric Power Demand Portfolio Optimization by Fermionic QAOA with Self-Consistent Local Field Modulation
• Performance evaluation of variational quantum eigensolver and quantum dynamics algorithms on the advection-diffusion equation
• Interpolation-based coordinate descent method for parameterized quantum circuits
• Quantum Algorithms for Causal Estimands
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
• Quantum Alternating Operator Ansatz for the Preparation and Detection of Long-Lived Singlet States in NMR
• Classical Neural Networks on Quantum Devices via Tensor Network Disentanglers: A Case Study in Image Classification
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• A Quantum Genetic Algorithm with application to Cosmological Parameters Estimation