Evaluation of QAOA based on the approximation ratio of individual samples

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors, it is one of the promising candidates likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, for exact, approximate and heuristic solution. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.

References in corpus (16)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Warm-starting quantum optimization
• Detecting bit-flip errors in a logical qubit using stabilizer measurements
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Parameter Concentration in Quantum Approximate Optimization
• Practical optimization for hybrid quantum-classical algorithms
• Quantum Algorithms for Fixed Qubit Architectures
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Characterizing local noise in QAOA circuits
• Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Scheduler of quantum circuits based on dynamical pattern improvement and its application to hardware design

Cited by in corpus (13)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Biology and medicine in the landscape of quantum advantages
• Quantum approximate optimization via learning-based adaptive optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• ORQVIZ: Visualizing High-Dimensional Landscapes in Variational Quantum Algorithms
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization