Solving Max-Cut with Quantum Computers: A Case Study on the Practicality and Limits of NISQ-Devices

Master’s Thesis
of
Lucas Berger

at the Department of Informatics
Institute of Information Security and Dependability
Test, Validation and Analysis (TVA)

---

Reviewer: Prof. Dr. Ina Schaefer
Second Reviewer: Prof. Dr. Ralf Reussner
Advisors: M.Sc. Joshua Ammermann, M.Sc. Domenik Eichhorn

Completion period: 2. October 2025 – 2. April 2026

Karlsruhe Institute of Technology

---

This repository contains the code for the master's thesis.

Structure

The repository uses the VSCode Workspace format to manage the different projects. To open the workspace, run the following command:

code master.code-workspace

Setup

Technologies needed

• Python 3.11
• uv
• Make
• git
• MADAM (optional if the same graphs are used)

Basic Setup

The main_project folder contains the main project which can be used as a entry point for the benchmark.

1. Run the main_project/setup.sh script to clone all needed external repositories, apply patches to them and install dependencies using uv.

cd main_project && ./setup.sh

2. (Optional) Go back to the root directory, clone the MADAM repository, built it and reference the path to the binary in the main_project/.env file.

git clone https://github.com/HrgaT/MADAM.git ./paper_implementations/MADAM
cd ./paper_implementations/MADAM
make

The local python libraries are installed as editable installs so changes in the source code are reflected immediately in the main project.

Guide for Reproducing the Results

Go to the main_project folder and run the benchmark script:

cd main_project
python src/main_project/benchmark.py --sample-size 5 --max-nodes 30 --seed 67 --simulator-method=statevector --max-ram 98304 --timeout 3600

This randomly selects 5 graphs from each subcategory of the HamLib and benchmarks the quantum algorithms with them. For this example the MADAM binary is needed as it will be used to find the exact solution for the Max-Cut instances. Alternatively we provide a thesis_runs/graphs.pkl with the pre-selected graphs from the master thesis. It can be used like so:

cd main_project
python src/main_project/benchmark.py --load-graphs ../thesis_runs/graphs.pkl --simulator-method=statevector --max-ram 98304 --timeout 3600

In the actual master thesis benchmarking run we have used parallel workers, GPU-acceleration and separate runs for each algorithm. The following command was used to run the benchmark:

python src/main_project/benchmark.py --load-graphs ../thesis_runs/graphs.pkl --only [qite|rqaoa|ctqw|nss|ordinary_qaoa] --workers 8 --tag custom_tag --gpu --simulator-method=statevector --max-ram 98304 --timeout 3600

Once the benchmark is done and 5 runs per algorithm are completed (you will need to restart the script for each run as only one run is executed per script call), the results are stored in benchmark_runs/.

By copying and correctly setting up the config file main_project/benchmark_monitoring_config.yaml you will be able to run the plot generation script:

cd main_project
python src/main_project/run_all_plots.py

This will generate all plots in the main_project/plots/ folder and save selected plots from the evaluation in the main_project/latex_plots/ folder.

Reproducing from Master Thesis Runs

Copy the thesis_runs/ folder to the main_project/ folder and rename it to benchmark_runs. Then copy the benchmark_monitoring_config.yaml file from the thesis_runs/ folder to the main_project/ folder and run the plot generation script:

source main_project/.venv/bin/activate
cd thesis_runs
python ../main_project/src/main_project/run_all_plots.py