Prerequisites

• Python 3.9.16
• QLM 1.9.1
• R 4.4.3
• Make

Install

1. Clone this repository
2. Pull Subrepositories (for search_backends.py)

git submodule update --init --recursive

3. Create virtual environment

python3 -m venv .venv

4. Install Python dependencies

make install-python

5. Install R dependencies

make install-r

Usage

Evaluation results, plot data and plots are stored in results, csvs and img-pdf/img-tikz. We describe how the data shown in the paper (or similar results) can be reproduced using this repository.

Run QAOA simulations

Important: Simulations are executed using the proprietary QLM library. We refer to this website for more details.

Raw QAOA simulation results are generated by *.bash in the results directory and stored as results/*.out files with the same name as the corrsponding Bash script. Each benchmark result file can be created with make results/FILENAME.txt. Alternatively, you can run all benchmarks using make results.

The degree of parallelism used for the benchmarks can be selected with the environment variable N_THREADS. For instance, N_THREADS=10 make results runs all benchmarks using 10 threads. The default value is N_THREADS=1. Be aware that executing all benchmarks takes a very long time, potentially several weeks, depending on the degree of parallelism.

Generate plot data

Plot data, which is generated from the benchmark results, is stored as CSV files in the csvs/ directory. The CSV files needed for the plots are already part of the repository. CSV file csvs/FILENAME.csv can be generated with make csvs/FILENAME.csv. Be aware that this automatically generates the benchmark results required for the plot if they do not already exist. Alternatively, one can create all csvs files with make csvs.

Generate plots

To generate the plots, run make plots. This creates two directories img-pdf and img-tikz and builds and runs a Docker container, which generates the plots, both as PDF and as Tikz graphics.

Test algorithm selection framework

Running make test tests the algorithm selection framework using results from our evaluations without the need of a available quantum device.

Project structure

Python scripts

• main.py: test script for the algorithm selection framework
• run_simulations.py: script to run the noisy QAOA benchmarks
• ideal_model_fitting.py, noisy_model_fitting.py: solution quality models
• runtime_fit.py: runtime models
• search_backends.py: Search noise parameters of the Qiskit fake backends
• get_result_statistics.py: takes a .out-file as input and prints a summary of the results in that file

Other Python files

• algorithm_selection_framework.py: defines the code annotations and dynamic automatic algorithm selection
• create_optimized_qaoa_circuit.py: Reduce problem Hamiltonian circuit depth using Misra-Gries edge coloring
• filter_results.py: Filter benchmark results using a simple query language
• generate_param_sets.py: generates multiple parameter sets from a JSON document using Cartesian product
• parse_params.py: Specification of benchmark parameters
• rqaoa.py: Implementation of Recursive QAOA for QLM
• terms.py: QUBO/Ising conversion logic and variable substitution for Recursive QAOA
• transpile_to_sx_rz.py: Circuit transpilation for QAOA circuits into the IMB-Q native gate set

Other

• results/: Stores benchmark results and Bash scripts to run the respective benchmarks
• csvs/: Stores plot data, obtained from the results/, as CSV files as well as Python scripts to create these files.
• img-pdf, img-tikz: plots
• r/: R scripts to generate the plots from the csv/ files