QSearch: Quantum Powered Search and Rescue
Note: This write-up accompanies team Carls’ response to the 2023 Quantinuum Challenge at MIT’s iQuHACK.
Introduction
Search and rescue is a notoriously time-dependent endeavor. In order to locate missing individuals, rescue teams often divide up an area, then search each portion in succession to find the missing individuals. Movement times between these areas can mean life or death for the missing party. Therefore, we propose a proof of concept solution utilizing quantum computers to optimize the route taken by search and rescue teams.
Solution
We designed an app that enables search and rescue teams to easily enter their desired search locations. Our app then queries a quantum computer backend to solve the Traveling Salesman Problem (TSP) defined by these search locations. Finally, our app returns the TSP solutions and displays the optimal route.
Methodology
The Traveling Salesman Problem (TSP) is an NP-Hard optimization problem. Therefore, we decided to solve it using a quantum approximation algorithm. More specifically, we implemented a variation of the Quantum Approximate Optimization Algorithm (QAOA) and converted TSP into a Quadratic Unconstrained Binary Optimization (QUBO) to solve with QAOA.
Quantum Approximate Optimization Algorithm
QAOA (Quantum Approximate Optimization Algorithm) is an excellent case study in the use of quantum hardware for solving approximation algorithms. In principle, QAOA is able to solve all Quadratic Unconstrained Binary Optimization (QUBO) problems, however, encoding the Hamiltonian may be challenging depending upon the QUBO parameters.
QUBO Overview
As the name suggests, Quadratic Unconstrained Binary Optimization (QUBO) problems are a specific case of quadratic optimization problem. Specifically, these problems have no constraints on the optimization solution (Unconstrained) and the problems optimize a binary vector (Binary).
The Traveling Salesman Problem: Build the Cost Function
For a graph G=(V, E) with n=|V| vertices and weights w_{u, v} for edge (u,v), the Traveling Salesman Problem attempts to find a path that traverses each vertex exactly once, returns to the starting vertex, and minimizes the cumulative weights of edges traversed.
To convert this to a QUBO, we must frame our constraints as part of a cost function.
First, we create a cost function to ensure that each node can only appear once in the final solution. This can be written as:
Next, we add a cost function to ensure that all nodes are present in the solution:
We next add a third cost function whose purpose was beyond us :(
Finally, we construct a fourth weight cost function to consider our weights w_{i, j}.
We group c_a, c_b, and c_c together to serve as our constraints. We can use a weighting term, A and B to specify the relative importance of the constraint terms (c_a, c_b, c_c) and the weight term c_d to arrive at the final cost function:
We must specify A and B such that Bis is sufficiently smaller than A. If it is not, the constraints encoded by c_a, c_b, and c_c may be unsatisfied.
The Traveling Salesman Problem: Run on a Quantum Computer
We can now encode this cost function as a Hamiltonian. Recall the following identity:
Rearranging, we get:
If we map each instance of x_{i, j}to a value x_k′, we can apply the above identity for all k∈{1,…,n²} to eliminate the x_i’s from our expression. Finally, we can rearrange and take the matrix exponential to produce our final quantum circuit.
Results
Given the brief timeframe of iQuHACK, we were unable to fully implement the TSP solver. However, we were able to implement a version of QAOA using COBAYLA as the classical optimizer. We ran this QAOA implementation and solved the Max-Cut Problem using Quantinuum’s official quantum simulator. We also incorporated Quantinuum’s quantum compiler, tket, and tested how different input graphs and different numbers of QAOA layers impact performance.
Benchmarking our algorithm for different parameters
