A quantum k-NN based on the Euclidean distance estimation

This repository provides the code for the article "A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation".

1. Prerequisites

In order to run the code, you need to have Python 3 installed. In particular, Python 3.8.10 has been used for the experiments presented in the paper. If you do not have Python 3 on your machine, we suggest to install Anaconda Python.

You may also want to create a virtual environment before performing the setup step. If you are using Anaconda Python, the shell command is the following:

conda create -n "venv" python=3.8.10

Eventually, if you want to use the online (simulated or quantum) backends provided by IBM, you must create an IBM Quantum account.

2. Setup

Once you have met the prerequisites, download the repository and move inside the project root folder. From the command line, this is the sequence of commands:

git clone https://github.com/ZarHenry96/euclidean-quantum-k-nn.git
cd euclidean-quantum-k-nn

Then, activate the virtual environment, if you are using it (for Anaconda, the command is conda activate venv), and install the required modules by runnning the following command:

pip install -r requirements.txt

Finally, to exploit the online IBM backends, you have to run the following instructions inside a Python shell (the IBM API token can be retrieved from the IBM Quantum dashboard):

from qiskit import IBMQ
IBMQ.save_account('insert_your_IBM_API_TOKEN_here')

3. Execution

To make the execution of the experiments easier, the run_exps.sh bash script is provided. In particular, to reproduce the experiments presented in the paper, you have to run (from the project root folder) the commands specified in the files located inside the resources/execution_commands directory (n.b., the execution takes a lot of time).

Actually, in order to obtain exactly the results presented in the paper, you have to provide the run_exps.sh script with the proper simulation seeds. Specifically, the seeds used in the article experiments are available inside the resources/simulation_seeds directory, and the flag to be used is -i (in particular, the flag -i must be specified before each value in the list).

The .json files containing the collected results presented in the paper are available inside the resources/collected_results directory, while the raw results data are available here.

4. Visualization

After the execution of the experiments, to visualize the results obtained, you can use the generate_plots.sh bash script (the execution takes some time). In detail, the script is configured to use the collected results data contained in the resources/collected_results directory (you can change this behaviour and the plots generated by modifying the variables set in the first rows of the file).

Note: the plots contained in the paper have been generated using a slightly modified version of the generate_plots.sh script (not provided here).