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.
|
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: |
| ||||||||||||||||||||||||||||
| 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