Solving The Travelling Salesman Problem Using A Single Qubit
ORAL
Abstract
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.
–
Presenters
-
Rick Mukherjee
Department of Physics and Chemistry and UTC Quantum Center, University of Tennessee at Chattanooga, Chattanooga, TN 37403, USA, University of Tennessee at Chattanooga, University of Tennessee Chattanooga
Authors
-
Rick Mukherjee
Department of Physics and Chemistry and UTC Quantum Center, University of Tennessee at Chattanooga, Chattanooga, TN 37403, USA, University of Tennessee at Chattanooga, University of Tennessee Chattanooga
-
KAPIL GOSWAMI
Zentrum für Optische Quantentechnologien, University of Hamburg, Hamburg, Germany, University of Hamburg, Hamburg University
-
Gagan A Veereshi
Hamburg University
-
Peter Schmelcher
Zentrum für Optische Quantentechnologien, University of Hamburg, Hamburg, Germany, University of Hamburg