  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 methods of solving TSPs on quantum systems are either gate-based or
binary variable-based encoding. Both approaches are resource-expensive in terms
of the number of qubits while performing worse compared to existing classical
algorithms 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 cities are represented as quantum states on the Bloch sphere
while the preparation of superposition states allows us to traverse multiple
paths at once. 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. For the TSP problem sizes considered in this
work, our algorithm is more resource-efficient and accurate than existing
quantum algorithms with the potential for scalability. A potential speed-up of
polynomial time over classical algorithms is discussed.
