Benchmarking the qubit-efficient MaxCut algorithm against state-of-the-art classical heuristics

הרקע לפרויקט:

We have recently developed the qubit-efficient MaxCut (QEMC) algorithm for heuristically solving the MaxCut problem on quantum hardware using few qubits. By simulating this algorithm on classical machines, we derived a new quantum-inspired algorithm and demonstrated numerically that it outperforms the best approximation MaxCut algorithm, namely the Goemans-Williamson (GW) algorithm. While the GW algorithm guarantees the highest lower bound solutions, it is not always the best in practice, as several classical algorithms were shown to outperform it in specific graph instances. To establish the QEMC as a competitive heuristic it is therefore necessary to compare it also against these state-of-the-art heuristics and check if there exist graph families for which it performs the best. This is the essence of this project.

מטרת הפרויקט:

The goal of this project is to position the QEMC against state-of-the-art classical MaxCut heuristics in terms of solution quality. By the end of the project, a thorough benchmarking is expected.

תכולת הפרויקט:

The students will:

• Understand and implement the QEMC algorithm on classical simulations
• Check the performance of the following algorithms: the Two-rank relaxation, simulated annealing, and coherence Ising machines
• Test all algorithms on the Stanford Gset (71 graphs with up to 20,000 nodes).
• Test all algorithms on the following graph families: k-regular, Erdős–Rényi, toroidal, planar, and random graphs.
• Summarize results in a meaningful way and draw conclusions about the competitiveness of the QEMC algorithm.

Remark: while the QEMC is a quantum algorithm, in this project we will only consider classical simulations.

קורסי קדם:

• Quantum computing
• Quantum machine learning

דרישות נוספות:

Any knowledge on optimization methods will be a plus.

מקורות:

https://arxiv.org/abs/2308.10383