TravelingSalesperson.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving TSP with Quantum\n",
    "In this notebook, we use D-Wave's Advantage System 1.1 quantum annealer to solve the Traveling Salesperson Problem.\n",
    "\n",
    "\n",
    "*you will need a D-Wave Leap account to run this notebook without errors*\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.optimization import QuadraticProgram\n",
    "from qiskit.optimization.algorithms import MinimumEigenOptimizer\n",
    "from dwave.plugins.qiskit import DWaveMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising import tsp\n",
    "from qiskit.optimization.applications.ising.common import sample_most_likely\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define Functions\n",
    "We're already operating at a high level of abstraction because we're using Qiskit to solve the TSP. Defining these functions adds another layer of abstraction to keep this notebook tidy and readable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 1: Generate n Cities\n",
    "This effectively defines n random points in 2D space, then converts these points into a TSP that can be solved by our D-Wave quantum computer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_op(ncity):\n",
    "    #Seed is set to 123 for reproducibility\n",
    "    print(f'Generating {ncity} cities...')\n",
    "    ncities_tsp = tsp.random_tsp(ncity, seed=123)\n",
    "    print(f'Converting TSP with {ncity} cities into an operator...')\n",
    "    operator, offset = tsp.get_operator(ncities_tsp)\n",
    "    print(f'Returning operator with {ncity} cities, requiring {operator.num_qubits} qubits with a total of {np.power(2, operator.num_qubits)} states.')\n",
    "    return operator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 2: Send Operator to QC\n",
    "This function creates an Eigenvalue solver to calculate the solution to our TSP. This quantum Eigensolver is then run on real quantum hardware by D-Wave."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qpu_run(op, nread):\n",
    "    dwave_mes = DWaveMinimumEigensolver(num_reads=nread)\n",
    "    result = dwave_mes.compute_minimum_eigenvalue(op)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 3: Check Feasibility\n",
    "The \"best\" solution our QC generates won't necessarily be a valid solution. This function produces a warning should it detect the solution determined by the QC is not a valid one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_feasible(tspx):\n",
    "    tspf = tsp.tsp_feasible(tspx)\n",
    "    if tspf == True:\n",
    "        print('TSP is feasible.')\n",
    "    elif tspf == False:\n",
    "        print('ERROR: TSP is not feasible.')\n",
    "    else:\n",
    "        print('Something weird is happening, TSP does not seem to be feasible or not-feasible.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 4: Process Result from QC\n",
    "In order to find the solution to our problem, we need to aggregate our readings from each shot. Basically we're just looking for the lowest energy readings over all of the shots, which we translate to a sequence of cities. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_solution(result):\n",
    "    tspx = sample_most_likely(result.eigenstate)\n",
    "    is_feasible(tspx)\n",
    "    tsp_solution = tsp.get_tsp_solution(tspx)\n",
    "    print(tspx)\n",
    "    return tsp_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 5: Attempt Solving as a Classic Computer function\n",
    "To compare the processing advantage of our quantum computer to a classical computer, we give the classical computer running this notebook (hosted on an AWS t3.medium instance) the same problem we gave the quantum computer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def try_solve_classic():\n",
    "    print('WARNING: This function will almost certainly break!!!!!!!!!!!!!!')\n",
    "    classic_result = NumPyMinimumEigensolver().compute_minimum_eigenvalue(operator)\n",
    "    return classic_result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function 6: Solve a TSP for n Cities\n",
    "Now, to put all the pieces of this together. We generate random points on a 2D plane, turn that data into an equation to find the shortest total path through each of the points, solve that equation with a quantum computer, and convert the amplitude measurements from the QC back into results that we can easily interpret."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_ncity(ncity, nread):\n",
    "    print(f'-> Cities: {ncity} \\n-> Shots: {nread}')\n",
    "    print('[1/3] Getting operator...')\n",
    "    op = get_op(ncity)\n",
    "    print('[2/3] Running on QPU...')\n",
    "    result = qpu_run(op, nread)\n",
    "    print('[3/3] Getting solution...')\n",
    "    solution = get_solution(result)\n",
    "    print(f'--> Best solution to TSP: {solution}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finally, the results!\n",
    "We generate 7 cities and take 10k shots to find our solution out of a pool of 562,949,953,421,312 possible solutions. All of this is done in just a few hundred milliseconds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-> Cities: 7 \n",
      "-> Shots: 10000\n",
      "[1/3] Getting operator...\n",
      "Generating 7 cities...\n",
      "Converting TSP with 7 cities into an operator...\n",
      "Returning operator with 7 cities, requiring 49 qubits with a total of 562949953421312 states.\n",
      "[2/3] Running on QPU...\n",
      "[3/3] Getting solution...\n",
      "TSP is feasible.\n",
      "[1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0\n",
      " 0 1 0 0 0 0 1 0 0 0 0 0]\n",
      "--> Best solution to TSP: [0, 6, 1, 5, 4, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "solve_ncity(7, 10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Notebook by Brian Lechthaler\n",
    "\n",
    "GPL v3 | 2020-12-11 | please do not redistribute without attribution\n",
    "\n",
    "* https://twitter.com/brianlechthaler\n",
    "* https://github.com/brianlechthaler\n",
    "* This notebook belongs to this repository: https://github.com/brianlechthaler/QuantumSolutions"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "conda_braket",
   "language": "python",
   "name": "conda_braket"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}