University of Twente Student Theses


Solving Correlation Clustering with the Quantum Approximate Optimisation Algorithm

Weggemans, J.R. (2020) Solving Correlation Clustering with the Quantum Approximate Optimisation Algorithm.

[img] PDF
Abstract:The quantum approximation optimisation algorithm (QAOA) is one of the leading candidates for testing the applicability of gate-model quantum resources at solving optimisation problems on small-sized quantum hardware. A combinatorial problem that has been understudied with QAOA is correlation clustering: given a weighted (+1,-1) graph, where the edge weights indicate whether two nodes are similar (positive edge weight) or different (negative edge weight), the task in correlation clustering is to find a clustering that either maximises agreements, minimises disagreements or a combination of both. In this thesis, we design Hamiltonian formulations that encode correlation clustering problems such that they can be solved with QAOA. For all Hamiltonian formulations we propose circuit implementations and study their complexities. To benchmark the performances of a basic QAOA algorithm using these formulations, we use numerical simulations on complete graph data sets. For one of the formulations, which uses a multi-level approach naturally suitable to qudit systems, we investigate the performances of several optimisers and introduce heuristic strategies to further improve its performance. On all instances in our data-sets, which include complete as well as Erdős–Rényi graphs, the improved algorithm shows competitive performances for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists such that it has a performance guarantee of 0.670 on 3-regular graphs.
Item Type:Essay (Master)
QuSoft (CWI), Amsterdam, Netherlands
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 33 physics, 54 computer science
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page