elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Accessibility | Contact | Deutsch
Fontsize: [-] Text [+]

Mean-Field Approximate Optimization Algorithm

Misra-Spieldenner, Aditi and Bode, Tim and Schuhmacher, Peter Ken and Stollenwerk, Tobias and Bagrets, Dmitry and Wilhelm, Frank K. (2023) Mean-Field Approximate Optimization Algorithm. PRX Quantum, 4 (030335). American Physical Society. doi: 10.1103/PRXQuantum.4.030335. ISSN 2691-3399.

[img] PDF - Published version
1MB

Official URL: https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.4.030335

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 replacement of the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Because of 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 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.

Item URL in elib:https://elib.dlr.de/200170/
Document Type:Article
Title:Mean-Field Approximate Optimization Algorithm
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Misra-Spieldenner, Aditia.misra-spieldenner (at) fz-juelich.deUNSPECIFIEDUNSPECIFIED
Bode, Timt.bode (at) fz-juelich.deUNSPECIFIEDUNSPECIFIED
Schuhmacher, Peter KenPeter.Schuhmacher (at) dlr.dehttps://orcid.org/0000-0003-1232-4363148466484
Stollenwerk, Tobiast.stollenwerk (at) fz-juelich.deUNSPECIFIEDUNSPECIFIED
Bagrets, Dmitryd.bagrets (at) fz-juelich.deUNSPECIFIEDUNSPECIFIED
Wilhelm, Frank K.f.wilhelm-mauch (at) fz-juelich.deUNSPECIFIEDUNSPECIFIED
Date:12 September 2023
Journal or Publication Title:PRX Quantum
Refereed publication:Yes
Open Access:Yes
Gold Open Access:Yes
In SCOPUS:Yes
In ISI Web of Science:Yes
Volume:4
DOI:10.1103/PRXQuantum.4.030335
Publisher:American Physical Society
ISSN:2691-3399
Status:Published
Keywords:QAOA Quantum Optimization Mean-Field Theory
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Quantum computing
Location: Köln-Porz
Institutes and Institutions:Institute of Software Technology > High-Performance Computing
Institute of Software Technology
Deposited By: Schuhmacher, Peter Ken
Deposited On:11 Dec 2023 09:45
Last Modified:15 Dec 2023 12:31

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
OpenAIRE Validator logo electronic library is running on EPrints
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.