Universität zu Köln

Henze, Fabian (2025). Performance of Quantum SDP Methods for Quadratic Binary Optimization Problems. PhD thesis, Universität zu Köln.

PDF (Dissertation) Dissertation_Henze_Fabian.pdf Bereitstellung unter der CC-Lizenz: Creative Commons Attribution. Download (1MB)

Abstract

Quantum computing algorithms offer asymptotic speedups compared to classical approaches in many domains. However, it remains uncertain whether these advantages extend to problem instances that can be solved within a reasonable time. One challenge for quantum algorithms is their often high scaling cost with respect to precision. Consequently, applications that allow approximate solutions are more promising candidates for quantum speedups. One such example are semidefinite programming (SDP) relaxations of quadratic binary optimization problems, which incorporate a rounding procedure at the end. The Hamiltonian Updates (HU) SDP-solving algorithm introduced by Brandão et al. in 2019 was specifically designed for such problems. This thesis analyzes the performance of the HU algorithm and assesses whether it could provide a quantum advantage. To ensure a fair comparison, we develop heuristics that significantly improve the algorithm’s efficiency. Since large-scale quantum computers do not yet exist, direct benchmarking is not possible. Instead, we adopt a hybrid approach, estimating the running time of quantum subroutines by analyzing their required number of gate operations. Our findings suggest that even with these optimizations and under highly optimistic assumptions favoring the quantum approach, a quantum implementation of the Hamiltonian Updates algorithm is unlikely to outperform classical methods for realistic problem sizes. Moreover, when applying SDP relaxations to real-world datasets, we observe that approximate relaxation techniques can lead to highly suboptimal solutions for the original optimization problems.

Item Type:	Thesis (PhD thesis)
Creators:	Creators Email ORCID ORCID Put Code Henze, Fabian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-786389
Date:	26 July 2025
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 quantum algorithms English semidefinite programming English optimization English Goemans-Williamson algorithm English Hamiltonian Updates algorithm English
Date of oral exam:	24 June 2025
Referee:	Name Academic Title Gross, David Prof. Dr. Motzoi, Felix Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/78638