Solving The Travelling Salesman Problem Using A Single Qubit*

The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing quantum algorithms of solving TSPs on quantum systems are either gate-based or binary variable-based encoding which are resource expensive in terms of the number of qubits and provide approximate results even for  small size problems. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements.