Solving the travelling salesman problem using Bloch sphere encoding

5 January 2026

Photo: AG Schmelcher

Solving the TSP using a quantum-inspired algorithm based on the superposition principle on a Bloch sphere.

The travelling salesman problem (TSP) is a combinatorial optimization problem and perhaps one of the most popular as well. Traditionally, the problem is defined for a person visiting multiple cities with the goal of determining the shortest possible route that visits all the cities exactly once and returns to the initial one. This formulation, along with slight modifications, generally suffices to encode a variety of optimization problems ranging from logistics and scheduling to network design and DNA sequencing. Despite its simple structure, the problem is computationally challenging for large problem sizes and lies in the NP-hard complexity class. Hence, it serves as an important benchmark for both classical and quantum optimization algorithms. Existing quantum approaches to solving the TSP rely on encoding the problem into large numbers of qubits, leading to significant overhead and sensitivity to noise. In the current era of quantum computing, where resources are scarce, efficient algorithms and novel ideas are needed to potentially overcome these limitations.

In this work, a fundamentally different approach is introduced to solving the TSP, which exploits the geometry of a single qubit by placing the cities onto a Bloch sphere. The rotations on the Bloch sphere encode different routes of the problem, which are accessed in parallel using the quantum superposition principle. The key idea is to pick the shortest route by engineering the time-dependent control fields that optimally create a selective superposition of quantum states and steer the system towards the solution. In our simulations, optimal solutions to prototypical TSP instances (four to nine cities) are obtained with higher accuracy compared to existing quantum algorithms that use hundreds to thousands of qubits for similarly sized problems. Our framework demonstrates that difficult combinatorial optimization problems can be addressed without large-scale qubit encodings by utilizing the geometry of the system. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements.

Publication
K. Goswami, G.A. Veereshi, P. Schmelcher, and R. Mukherjee
Solving the travelling salesman problem using Bloch sphere encoding
Quantum Science and Technology 11, 015007 (2026)