Universität zu Köln

Goh, Mark Xin Hong ORCID: 0009-0005-5505-2590 (2026). The overlap gap property and its implication for the quantum approximate optimisation algorithm. PhD thesis, Universität zu Köln.

PDF Dissertation_Publish_MG.pdf - Published Version Bereitstellung unter der CC-Lizenz: Creative Commons Attribution. Download (2MB)

Abstract

The main focus of this thesis can be framed in the following question: How does the presence and absence of the overlap gap property (OGP) affect quantum algorithms such as the quantum approximate optimization algorithm (QAOA)? The OGP, a topological property that occurs when the set of near optimal solutions exhibits a form of strong clustering, is known to inhibit the performance of various classes of algorithms. In classical algorithms, the OGP acts a tight upper bound on many different classes of algorithms including online algorithms and ‘stable’ algorithms such as Lipschitz algorithms. For quantum algorithms, the OGP is known to inhibit the algorithmic performance at shallow depth such as logarithmic depth quantum annealing. This thesis focuses on how the OGP affects the QAOA and advances the understanding of the run-time required for quantum advantage. Improving upon previous results, I prove that at logarithmic depth, the OGP acts as a strict upper bound for the QAOA thus proving that there is indeed no quantum advantage at logarithmic depth. Complementing the analytic result above, I similarly proved that the performance of the mean-field approximate optimization algorithm (MF-AOA), a classical algorithm inspired by the QAOA, is likewise strictly upper-bounded by the OGP. Thus, for the QAOA to exhibit quantum advantage over its classical counterpart, one requires sufficiently high depth such that the QAOA is able to give an output that is greater than the OGP value. Together with my collaborator, we also provide numerical evidence that the depth required for quantum advantage in the QAOA is super-polynomial if one requires the approximation ratio to be higher than the OGP value. While this thesis adds onto the growing body of literature of how the OGP acts as a signal of algorithmic hardness for many classes of algorithms, this work also provides the first instance of how the OGP can inform algorithmic design. This thesis provides evidence that in the presence of the OGP, the variational parameters used to optimize the QAOA’s output at polynomial depth differ depending on whether one wishes to maximize the approximation ratio or to minimize the time to find the optimal solution.Understanding the right schedule is important for designing an optimal quantum control to steer a quantum state into its desired form. Our results also indicate that problems that do not exhibit the OGP are likely to be solved efficiently by quantum annealing or adiabatic quantum computing since the optimal schedule found in the QAOA follows an adiabatic schedule. Lastly, this thesis provides a novel use of the QAOA, that of identifying use cases where efficient classical algorithms exists but are yet to be discovered. Specifically,by applying logarithmic depth QAOA to the binary paint shop problem (BPSP), we show that the performance of the QAOA surpasses that of all known polynomial time classical algorithms. However, given the failure of logarithmic depth QAOA to outperform classical algorithms on sparse optimization problems such as the BPSP, this implies that there must be an efficient classical algorithm that beats all currently known heuristic methods. Applying the MF-AOA to the BPSP, we find that it significantly outperforms all known classical heuristics and applications of the QAOA (and its variants) on the BPSP.

Item Type:	Thesis (PhD thesis)
Creators:	Creators Email ORCID ORCID Put Code Goh, Mark Xin Hong goh_xinhong@hotmail.com https://orcid.org/0009-0005-5505-2590 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-805107
Date:	2026
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Physics > Institute for Theoretical Physics
Subjects:	Physics
Uncontrolled Keywords:	Keywords Language QAOA UNSPECIFIED Quantum Computing English optimization English
Date of oral exam:	9 June 2026
Referee:	Name Academic Title Sperl, Matthias Prof. Dr. Gross, David Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/80510