Constrained combinatorial optimization is a ubiquitous problem with applications across finance, medicine, machine learning, etc. Our ability to solve these problems with quantum algorithms is constrained by the limited number of qubits that are available in current NISQ processors. The quantum local search algorithm addresses this issue by finding solutions to smaller subproblems that can be recombined into a global solution. The code in this repository gives an implementation of quantum local search algorithm for finding approximate solutions to the Maximum Independent Set problem on large graphs. A paper describing our work is available online: https://arxiv.org/abs/2107.04109.
The code in this repo requires the qcopt package which can be found here. Follow the instructions below to install the qcopt package.
git clone https://github.com/teaguetomesh/quantum-constrained-optimization.git
python3 -m venv your_new_venv # create a new Python virtual environment
source your_new_venv/bin/activate # activate that virtual environment
cd quantum-constrained-optimization
pip install -r requirements.txt # install the package dependecies
pip install -e . # install the qcopt packageThe code which implements the QLS algorithm is contained in solve_mis.py. This file makes calls to the functions defined in qls_ansatz.py to construct the quantum circuits. The two notebooks plotting.ipynb and plotting-revision.ipynb use the data found in benchmark_results.tar to generate the plots found in the published paper. The tar file should be decompressed before running these notebooks:
tar -xzvf benchmark_results.tarThe file QLS_benchmark.py can be used to perform additional simulations of the QLS algorithm for the benchmark graphs found in benchmark_graphs or any other graphs of interest.
If you use this code, please cite our work:
Teague Tomesh, Zain H. Saleem, and Martin Suchara. "Quantum Local Search with the Quantum Alternating Operator Ansatz." Quantum 6 (2022): 781.