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.

6 pages, 1 figure

References in corpus (4)

• A Quantum Approximate Optimization Algorithm
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Practical optimization for hybrid quantum-classical algorithms

Cited by in corpus (4)

• Training Saturation in Layerwise Quantum Approximate Optimisation
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Progress towards analytically optimal angles in quantum approximate optimisation
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation