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 (40)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• A Quantum Approximate Optimization Algorithm
• Characterizing Quantum Supremacy in Near-Term Devices
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• 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
• Detecting bit-flip errors in a logical qubit using stabilizer measurements
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Parameter Concentration in Quantum Approximate Optimization
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Intel Quantum Simulator: A cloud-ready high-performance simulator of quantum circuits
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• 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
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
• Characterizing local noise in QAOA circuits
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Random MAX SAT, Random MAX CUT, and Their Phase Transitions
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• Community Detection Across Emerging Quantum Architectures
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Effects of Quantum Noise on Quantum Approximate Optimization Algorithm
• 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