QAOA Mixing Hamiltonians for MinVertexCover
T.C.P. Driebergen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Matthias Möller – Mentor (TU Delft - Numerical Analysis)
D. de Laat – Mentor (TU Delft - Discrete Mathematics and Optimization)
Leo Iersel – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
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.
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.