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

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

References in corpus (144)

• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• Shortcuts to adiabaticity: concepts, methods, and applications
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• Quantum algorithms for quantum chemistry and quantum materials science
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Computation by Adiabatic Evolution
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Continuous-variable quantum neural networks
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Layerwise learning for quantum neural networks
• 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
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Low-cost error mitigation by symmetry verification
• Error-mitigated digital quantum simulation
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Improving Variational Quantum Optimization using CVaR
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
• Correlating decoherence in transmon qubits: Low frequency noise by single fluctuators
• Stochastic gradient descent for hybrid quantum-classical optimization
• A different kind of quantum search
• Floquet-engineering counterdiabatic protocols in quantum many-body systems
• $XY$-mixers: analytical and numerical results for QAOA
• Noise Resilience of Variational Quantum Compiling
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Exponential Error Suppression for Near-Term Quantum Devices
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Benchmarking the Quantum Approximate Optimization Algorithm
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Performance comparison of optimization methods on variational quantum algorithms
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Extremal Cuts of Sparse Random Graphs
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Implementation of the XY interaction family with calibration of a single pulse
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• MAXCUT QAOA performance guarantees for p >1
• Hybrid quantum-classical algorithms for approximate graph coloring
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• A quantum-classical cloud platform optimized for variational hybrid algorithms
• Multistart Methods for Quantum Approximate Optimization
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Evaluating the noise resilience of variational quantum algorithms
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
• Non-Markovian qubit dynamics in the presence of 1/f noise
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Using models to improve optimizers for variational quantum algorithms
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Feedback-based quantum optimization
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Characterizing local noise in QAOA circuits
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Suboptimality of local algorithms for a class of max-cut problems
• 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
• Noise-Resilient Variational Hybrid Quantum-Classical Optimization
• Error propagation in NISQ devices for solving classical optimization problems
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Quantum annealing with longitudinal bias fields
• Quantum optimization via four-body Rydberg gates
• Low depth mechanisms for quantum optimization
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• 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
• Evaluation of QAOA based on the approximation ratio of individual samples
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
• 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
• Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• 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
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Fermionic Quantum Approximate Optimization Algorithm
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Reinforcement Learning with Quantum Variational Circuits
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Ability of error correlations to improve the performance of variational quantum algorithms
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit
• Optimizing Quantum Algorithms on Bipotent Architectures
• Investigating Quantum Approximate Optimization Algorithms under Bang-bang Protocols
• 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