QAOA Mixing Hamiltonians for MinVertexCover

QAOA Mixing Hamiltonians for MinVertexCover

Driebergen, Tim (TU Delft Electrical Engineering, Mathematics and Computer Science)

Möller, M. (mentor)
de Laat, D. (mentor)
van Iersel, L.J.J. (graduation committee)

Delft University of Technology

Applied Mathematics

2023-01-24

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.

Quantum Computing
Optimization
Quantum Algorithms
QAOA
Quantum
Minimum Vertex Cover
Combinatorial Optimization
Approximation Algorithms
Hamiltonians
Graph Theory

http://resolver.tudelft.nl/uuid:40b61c43-67c1-4673-b6c1-941505bf9ca8

Student theses

master thesis

© 2023 Tim Driebergen