Butterfly: Modular TSP Solver

A modular Python package for solving the Traveling Salesperson Problem (TSP) using both classical and quantum-inspired algorithms.

Features

• Christofides Algorithm: Classical polynomial-time approximation algorithm with 1.5-approximation guarantee
• QAOA Algorithm: Quantum Approximate Optimization Algorithm for potentially better solutions
• Modular Design: Clean separation of concerns with dedicated modules
• Visualization: Comprehensive plotting and comparison tools
• Testing: Built-in test functions with brute force verification
• Flexible Interface: Both command-line and programmatic interfaces

Installation

1. Clone the repository:

git clone https://github.com/computabeast/butterfly.git
cd butterfly

2. Create a virtual environment:

python3 -m venv venv
source venv/bin/activate  # On Windows: venv\Scripts\activate

3. Install dependencies:

pip install -r requirements.txt

Quick Start

Command Line Interface

Run both algorithms on a 6-city TSP instance:

python main_tsp_solver.py --cities 6 --algorithm both --seed 42 --visualize

Run only Christofides:

python main_tsp_solver.py --cities 8 --algorithm christofides --plot-steps

Run only QAOA with custom parameters:

python main_tsp_solver.py --cities 5 --algorithm qaoa --qaoa-depth 3 --qaoa-reps 2000

Python Interface

from butterfly import TSPGraph, tsp, qaoa_tsp

# Create a TSP instance
tsp_instance = TSPGraph(n=6, dim=2, seed=42)

# Run Christofides algorithm
christofides_length, christofides_tour = tsp(tsp_instance)

# Run QAOA algorithm
qaoa_length, qaoa_tour, history = qaoa_tsp(tsp_instance, p=2, reps=1000)

print(f"Christofides: {christofides_length:.4f}")
print(f"QAOA: {qaoa_length:.4f}")

Project Structure

butterfly/
├── __init__.py              # Package initialization and exports
├── tsp_graph.py             # TSPGraph class and graph utilities
├── christofides.py          # Christofides algorithm implementation
├── qaoa_utils.py            # QAOA encoding and utility functions
├── qaoa_tsp.py              # Main QAOA implementation
├── tests.py                 # Test functions and brute force verification
├── main_tsp_solver.py       # Command-line interface
├── main_tsp_solver.ipynb    # Jupyter notebook interface
├── requirements.txt         # Python dependencies
└── README.md               # This file

Module Documentation

tsp_graph.py

• TSPGraph: Main class for creating and managing TSP instances
• canonicalise_tour(): Utility function for tour normalization

christofides.py

• tsp(): Implementation of the Christofides algorithm
• plot_graph(): Visualization helper for algorithm steps

qaoa_utils.py

• ising_from_tsp(): Convert TSP to Ising model
• points_order_to_binary_state(): Convert tour to binary encoding
• binary_state_to_points_order(): Convert binary encoding to tour
• is_feasible(): Check if binary state represents valid tour
• bs_to_tour(): Convert binary state to tour with length calculation

qaoa_tsp.py

• qaoa_tsp(): Main QAOA implementation for TSP
• _create_cost_layer(): Build cost layer of QAOA circuit
• _create_mix_layer(): Build mixing layer of QAOA circuit

tests.py

• test_tsp_graph_metric(): Test Christofides algorithm
• test_tsp_graph_metric_with_qaoa(): Test both algorithms
• brute_force_tours(): Generate all possible tours for verification

Algorithm Details

Christofides Algorithm

1. Find minimum spanning tree (MST)
2. Identify vertices with odd degree
3. Find minimum-weight perfect matching on odd-degree vertices
4. Combine MST and matching to form multigraph
5. Find Eulerian circuit
6. Convert to Hamiltonian cycle by removing duplicates

Guarantee: 1.5-approximation ratio for metric TSP Complexity: O(n³) where n is the number of cities

QAOA Algorithm

1. Encode TSP as binary optimization problem
2. Construct parameterized quantum circuit
3. Apply cost and mixing layers alternately
4. Optimize parameters using classical optimization
5. Sample from optimized circuit to find solution

Advantage: Can find better solutions for some instances Complexity: Exponential in circuit depth, but polynomial in number of qubits

Command Line Options

--cities INT              Number of cities (default: 6, max 12 for brute force)
--dimension INT           Dimension of the space (default: 2)
--seed INT               Random seed (default: 42)
--algorithm CHOICE       Algorithm to run: christofides, qaoa, or both (default: both)
--qaoa-depth INT         QAOA depth parameter (default: 2)
--qaoa-reps INT          QAOA circuit repetitions (default: 1000)
--qaoa-maxiter INT       QAOA optimization iterations (default: 30)
--plot-steps             Plot Christofides algorithm steps
--no-convergence-plot    Disable QAOA convergence plot
--brute-force            Run brute force verification (for n ≤ 12)
--visualize              Show comparison visualization

Performance Guidelines

• Small instances (n ≤ 5): Both algorithms work well, QAOA often finds optimal solutions
• Medium instances (n = 6-8): Christofides is faster, QAOA may find better solutions
• Large instances (n > 8): Christofides recommended, QAOA becomes slow
• Brute force verification: Only practical for n ≤ 12

Examples

Example 1: Quick Comparison

python main_tsp_solver.py --cities 5 --algorithm both --visualize

Example 2: QAOA Parameter Tuning

python main_tsp_solver.py --cities 4 --algorithm qaoa --qaoa-depth 3 --qaoa-reps 2000

Example 3: Detailed Analysis

python main_tsp_solver.py --cities 6 --algorithm both --plot-steps --brute-force --visualize

Contributing

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Add tests if applicable
5. Submit a pull request

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

• Christofides algorithm implementation based on the original paper
• QAOA implementation inspired by various quantum computing resources
• Uses Cirq for quantum circuit construction and simulation