Deep-Circuit QAOA

arXiv2210.12406MaRDI QIDQ6414767FDOQ6414767

Authors: Gereon Koßmann, Lennart Binkowski, Lauritz van Luijk, Timo Ziegler, René Schwonnek 

Publication date: 22 October 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.

This page was built for publication: Deep-Circuit QAOA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414767)