Quantum Traveling Salesman Solver

Welcome to the Quantum Traveling Salesman Solver repository! This project contains a collection of algorithms designed to solve the Traveling Salesman Problem (TSP) using both quantum annealing and classical approaches. The repository also includes comparisons of the performance and accuracy of these methods.

Table of Contents

• Installation
• Usage
• Solvers
  • Global1A1 Solvers
  • Jain Solvers
• Data
• Results Visualization
• License

Installation

To set up the project, you need Poetry for dependency management and the D-Wave Ocean SDK to interact with quantum annealing solvers. Follow the steps below to get started:

1. Clone the repository:

   git clone https://github.com/your-username/quantum-traveling-salesman-solver.git
   cd quantum-traveling-salesman-solver

2. Install dependencies with Poetry:

   poetry install

   This command will install all the necessary Python dependencies, including the appropriate version of Python if not already installed.

3. Install and configure D-Wave Ocean SDK:

   • If you installed the D-Wave Ocean SDK and have already set up the token before, skip this step. You can verify your setup by running:

     dwave config inspect

   • If the D-Wave Ocean SDK was installed using Poetry in the previous step, you need to configure your D-Wave API token:

     poetry run dwave config create

     During this setup, you'll be prompted to enter your API token, which you can obtain from your D-Wave account.

Once these steps are completed, you can start running the solvers and experimenting with quantum and classical approaches to solving the Traveling Salesman Problem.

Usage

• To start solving TSP problems, you can use the solvers provided in the code directory. Additionally, the Utils directory contains useful scripts for generating tests, plotting results, and other utilities.

Note: Always use Poetry to run the scripts to ensure the correct environment is used.

• All solvers follow the same usage pattern:

  poetry run python <solver path> <input file path> <output file path>

• For example, to run the eqats_solver.py solver on a problem file, use the following command:

  poetry run python code/Global1A1_Solvers/eqats_solver.py data/n8/problems/problem1.txt sol.txt

This command will run the specified solver on the given problem file and output the solution to sol.txt.

Solvers

Global1A1 Solvers

The Global1A1 Solvers directory contains the following algorithms, developed as part of this project:

• backtrack.py: A classical backtracking solver for TSP.
• dwave_solver.py: A quantum annealing-based solver using a QUBO matrix provided by D-Wave's API.
• eqats_solver.py: Our enhanced quantum annealing TSP solver.
• plot.py: Utility for plotting solution paths and results.

Jain Solvers

The Jain Solvers directory contains algorithms contributed by Siddharth Jain, in his prior work:

• 2opt-solver.py: A classical optimization algorithm for TSP.
• brute-force-solver.py: A brute-force approach to finding the optimal TSP solution.
• my-quantum-solver.py: A quantum annealing TSP solver provided by Siddharth Jain.

Data

The data directory contains problem instances and corresponding solutions for various TSP problem sizes:

• n8, n9, n10, n20: Directories containing problem definitions and solutions generated by different solvers.

Results Visualization

The results of the various solvers can be visualized using scripts in the Utils directory:

Visualizations of the results for different problem sizes are stored in the images directory.

License

This project is licensed under the MIT License. See the LICENSE.txt file for details.