Mean-Field Approximate Optimization Algorithm

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is suggested as a promising application on early quantum computers. Here, a quantum-inspired classical algorithm, the mean-field Approximate Optimization Algorithm (mean-field AOA), is developed by replacing the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Due to the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e. we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA. To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents. These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.

arXiv comment17 pages, 8 figures

References in corpus (26)

• Quantum Computing in the NISQ era and beyond
• Random-Matrix Theory of Quantum Transport
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Localization of interacting fermions at high temperature
• Adiabatic Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Many-body localization: an introduction and selected topics
• Novel Circuit Theory of Andreev Reflection
• Anderson localization casts clouds over adiabatic quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
• Non-equilibrium Functional Renormalization for Driven-Dissipative Bose-Einstein Condensation
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Benchmarking the Quantum Approximate Optimization Algorithm
• Optimal Protocols in Quantum Annealing and QAOA Problems
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• The Semiclassical Propagator for Spin Coherent States
• Quasiclassical theory of disordered multi-channel Majorana quantum wires
• Many body localization-delocalization transition in quantum Sherrington-Kirkpatrick model
• Many-body localization enables iterative quantum optimization
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Localization transition induced by programmable disorder
• Magnon Localization in Mattis Glass

Cited by in corpus (11)

• Low-depth Clifford circuits approximately solve MaxCut
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Synergistic Dynamical Decoupling and Circuit Design for Enhanced Algorithm Performance on Near-Term Quantum Devices
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Deep Unfolded Local Quantum Annealing
• Quantum Software Ecosystem Design
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems