Comparison of QAOA with Quantum and Simulated Annealing

Abstract

We present a comparison between the Quantum Approximate Optimization Algorithm (QAOA) and two widely studied competing methods, Quantum Annealing (QA) and Simulated Annealing (SA). To achieve this, we define a class of optimization problems with respect to their spectral properties which are exactly solvable with QAOA. In this class, we identify instances for which QA and SA have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, Simulated Annealing and Quantum Annealing, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively.

arXiv comment6 pages, 1 figure

References in corpus (13)

• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Demonstration of a small programmable quantum computer with atomic qubits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Practical optimization for hybrid quantum-classical algorithms
• A quantum algorithm to train neural networks using low-depth circuits
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Cited by in corpus (12)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Parameter Concentration in Quantum Approximate Optimization
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Low depth mechanisms for quantum optimization
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Optimal Control for Closed and Open System Quantum Optimization
• Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems
• Progress towards analytically optimal angles in quantum approximate optimisation
• Quantum mean value approximator for hard integer value problems
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation