TSP_VQC

This note book provides the code to solve the Travelling Salesman problem (TSP) with a Variational Quantum Circuit, and a quantum inspired classical machine learning model. Full documentation can be found in the Read_the_Docs

The work is described in more detail in an article

Note: Circuit 6 in this repo is re-numbered as Circuit 5 in the article.

Getting started

Install the repository locally

Clone the repository to a suitable location on your computer using the following command:

git clone https://github.com/goldsmdn/TSP_VQC

Install uv

Please see the installation instructions

Set up dependencies using uv

Use the following command run from the TSP_VQC directory

uv venv
source .venv/Scripts/activate
uv pip install numpy pytest graycode qiskit qiskit_aer torch
uv pip install sphinx sphinx_rtd_theme sphinx-autodoc-typehints matplotlib
uv pip install qiskit_ibm_runtime pandas seaborn
uv pip install ipykernel notebook pylatexenc
uv pip install torchviz graphviz

Running the notebooks

To run one of the notebooks, for example manual_runs_ML.ipynb enter

jupyter notebook manual_runs_ML.ipynb

Alternatively you can run in the VS code development environment, setting the Python interpreter to Base.

Process overview

An overview of the process is shown below. In summary:

• TSP networks are stored in the networks folder, either loaded from external sources, or created automatically by make_data.ipynb.
• runs can be executed manually by manual_runs_ML.ipynb for classical ML and manual_runs_VQC.ipynb for quantum. These allow an interactive environment for simple experiments. In manual executions the control parameters are read from the a configuration data in modules/config.py
• most runs are executed automatically by auto_runs.ipynb
• in any cases results data is updated to the results.csv file, and to sub-run specific results files and graphs
• each execution of data causes a run-id to be created, and each different set of configuration data causes a sub-id to be created.
• data is analysed by show_results.ipynb
• bespoke graphs are plotted in plot_data.ipynb

Notebooks provided

Data execution

The following Jupyter notebooks are provided for data execution:

• auto_runs.ipynb: responsible for executing automatic runs, reading configuration data from control_parameters.csv
• manual_runs_ML.ipynb: responsible for executing manual runs of the classical ML model, reading configuration data from modules/config.py
• manual_runs_VQC.ipynb: responsible for executing manual runs of the quantum machine learning model, reading configuration data from modules/config.py

Network creation

The following Jupyter notebooks are provided for create networks for testing. The networks are stored in the networks folder.

• make_data.ipynb: responsible for setting up new networks

Data analysis

The following Jupyter notebooks are provided for data analysis:

• show_results.ipynb: responsible for analysing the results stored in the result/results.csv file
• plot_data.ipynb: resonsible for creating bespoke graphs of individual runs and plots anomolous network with 42 locations
• resource_requirements.ipynb: calculates the number of qubits needed for each formulation
• hot_start_analysis.ipynb: compares the Hamming distance of the hot start binary string to the binary string of the optimum solution
• monte_carlo.ipynb: carries out Monte Carlo simulations by finding the best distance over a range of bit strings
• bit_strings_ranked_by_distance.ipynb: Plots a graph of the solution quality by ordered bit string

Python modules

The following modules are provided in the modules folder:

Helper functions

• helper_functions_tsp.py: general helper functions
• graph_functions.py: plots graphs
• helper_ML_functions.py: specific to classical machine learning model

Test functions

A full suite of over 70 test Unit Test cases is provided and executed automatically using PyTest on each push to the repository

• test_ML_functions.py: unit test cases for classical machine learning
• test_quantum_functions.py: unit test cases for quantum machine learning
• test_tsp_helper.py: general unit test cases

Python classes

The following object orientated code is provided:

• LRUCacheUnhashable.py: handles caches of bit string evaluations
• MyDataLogger.py: handles logging of data results including updating results.txt, and sub-run specific data summaries and graphs. This module is object orientated, with objects for a parent run-id and child sub-id.
• MyModel.py: responsbile for classical machine learing PyTorch modules

Contributing

Contributions to the repository are very welcome. Please raise an issue if you have any problems, and feel free to contact me.

Key coding points

Optimisers

The optimiser is chosen setting the constant GRADIENT_TYPE. For quantum two optimisers bespoke coding is provided:

• parameter_shift which uses the fact that qubit rotations are trigonometric functions to find an analytical expression for the gradient. Please see Pennylane documentation for a full description of parameter shift.
• SPSA is an algorithm of optimisation invented by James C. Spall specially useful for noisy cost functions and the ones which the exact gradient is not available. Please see a blog for a description of SPSA code that was modified.