QAOA Mixing Hamiltonians for MinVertexCover

Master thesis (2023)

Authors

T.C.P. Driebergen Electrical Engineering, Mathematics and Computer Science

Contributors

M. Möller Numerical Analysis - EEMCS (supervisor 1)
D. de Laat Discrete Mathematics and Optimization - EEMCS (supervisor 1)
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Tim Driebergen
More Info
expand_more

Published Date

24-01-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The minimum vertex cover problem (MinVertexCover) is an important optimization problem in graph theory, with applications in numerous fields outside of mathematics. As MinVertexCover is an NP-hard problem, there currently exists no efficient algorithm to find an optimal solution on arbitrary graphs. We consider quantum optimization algorithms, such as the Quantum Alternating Operator Ansatz (QAOA+), to find good minimum vertex covers.

This thesis presents new 'second degree' mixing Hamiltonians for MinVertexCover in the QAOA+ framework, which allow mixing between solutions Hamming distance 2 apart. The performance of these new Hamiltonians is evaluated on a small graph. Methods to extend this idea by constructing Hamiltonians which allow mixing between solutions at Hamming distance n are also presented, along with a generalization of second degree mixing Hamiltonians to other optimization problems.