Loading [MathJax]/extensions/tex2jax.js

Deep-Circuit QAOA

Research output: Working paper/PreprintPreprint

Details

Original languageEnglish
Publication statusE-pub ahead of print - 22 Oct 2022

Abstract

Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate optimization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. So far, those findings mostly account for a regime of few qubits and shallow circuits. We find clear evidence for a `no free lunch'-behavior of QAOA on a general optimization task with no further structure; individual cases have, however, to be analyzed more carefully. We propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely evaluating statistical properties of the classical objective function. We further discuss the various favorable properties a generic QAOA instance has in the asymptotic regime of infinitely many gates, and elaborate on the immanent drawbacks of finite circuits. We provide several numerical examples of a deep-circuit QAOA method based on local search strategies and find that - in alignment with our performance indicator - some special function classes, like QUBO, admit a favorable optimization landscape.

Keywords

    quant-ph, math-ph, math.MP

Cite this

Deep-Circuit QAOA. / Koßmann, Gereon; Binkowski, Lennart; van Luijk, Lauritz et al.
2022.

Research output: Working paper/PreprintPreprint

Koßmann G, Binkowski L, van Luijk L, Ziegler T, Schwonnek R. Deep-Circuit QAOA. 2022 Oct 22. Epub 2022 Oct 22.
Download
@techreport{9b38602bdea64c8d94a6a6d62c42afea,
title = "Deep-Circuit QAOA",
abstract = " Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate optimization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. So far, those findings mostly account for a regime of few qubits and shallow circuits. We find clear evidence for a `no free lunch'-behavior of QAOA on a general optimization task with no further structure; individual cases have, however, to be analyzed more carefully. We propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely evaluating statistical properties of the classical objective function. We further discuss the various favorable properties a generic QAOA instance has in the asymptotic regime of infinitely many gates, and elaborate on the immanent drawbacks of finite circuits. We provide several numerical examples of a deep-circuit QAOA method based on local search strategies and find that - in alignment with our performance indicator - some special function classes, like QUBO, admit a favorable optimization landscape. ",
keywords = "quant-ph, math-ph, math.MP",
author = "Gereon Ko{\ss}mann and Lennart Binkowski and {van Luijk}, Lauritz and Timo Ziegler and Ren{\'e} Schwonnek",
note = "19 pages, 13 figures",
year = "2022",
month = oct,
day = "22",
language = "English",
type = "WorkingPaper",

}

Download

TY - UNPB

T1 - Deep-Circuit QAOA

AU - Koßmann, Gereon

AU - Binkowski, Lennart

AU - van Luijk, Lauritz

AU - Ziegler, Timo

AU - Schwonnek, René

N1 - 19 pages, 13 figures

PY - 2022/10/22

Y1 - 2022/10/22

N2 - Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate optimization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. So far, those findings mostly account for a regime of few qubits and shallow circuits. We find clear evidence for a `no free lunch'-behavior of QAOA on a general optimization task with no further structure; individual cases have, however, to be analyzed more carefully. We propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely evaluating statistical properties of the classical objective function. We further discuss the various favorable properties a generic QAOA instance has in the asymptotic regime of infinitely many gates, and elaborate on the immanent drawbacks of finite circuits. We provide several numerical examples of a deep-circuit QAOA method based on local search strategies and find that - in alignment with our performance indicator - some special function classes, like QUBO, admit a favorable optimization landscape.

AB - Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate optimization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. So far, those findings mostly account for a regime of few qubits and shallow circuits. We find clear evidence for a `no free lunch'-behavior of QAOA on a general optimization task with no further structure; individual cases have, however, to be analyzed more carefully. We propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely evaluating statistical properties of the classical objective function. We further discuss the various favorable properties a generic QAOA instance has in the asymptotic regime of infinitely many gates, and elaborate on the immanent drawbacks of finite circuits. We provide several numerical examples of a deep-circuit QAOA method based on local search strategies and find that - in alignment with our performance indicator - some special function classes, like QUBO, admit a favorable optimization landscape.

KW - quant-ph

KW - math-ph

KW - math.MP

M3 - Preprint

BT - Deep-Circuit QAOA

ER -

By the same author(s)