⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

This paper presents a resource-efficient quantum algorithm that solves the Travelling Salesman Problem for up to nine cities using a single qubit by leveraging quantum parallelism and optimal control methods based on a quantum Brachistochrone approach, demonstrating superior accuracy and potential polynomial speed-up over existing quantum and classical methods.

Original authors: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The Tired Traveler

Imagine you are a traveling salesman with a map of cities. Your job is to visit every city exactly once and return home, but you want to do it using the shortest possible distance.

This is the famous Traveling Salesman Problem (TSP). It's a classic puzzle that gets incredibly hard very quickly. If you have 4 cities, it's easy. If you have 10, it's manageable. But if you have 20, the number of possible routes is so huge that even the world's fastest supercomputers would take longer than the age of the universe to check them all one by one.

The Old Quantum Way: The "Too Many Keys" Approach

Usually, when scientists try to solve this on a quantum computer, they treat the problem like a giant lock with many tumblers. They need a separate "tumbler" (a qubit) for every city and every possible connection.

The Problem: To solve a problem with just 9 or 10 cities, existing quantum methods need hundreds or even thousands of qubits.
The Reality: Current quantum computers are noisy and fragile. They struggle to keep that many qubits working together, and they often fail to find the perfect answer, even for small maps.

The New Idea: The "One-Wonder" Qubit

This paper proposes a radical new way to solve the TSP using only a single qubit (the basic unit of quantum information). Think of this single qubit not as a tiny switch, but as a magic spinning top that can point in any direction in 3D space.

Here is how they make it work, step-by-step:

1. The Map is a Globe (The Bloch Sphere)

Instead of drawing cities on a flat piece of paper, the authors map them onto the surface of a sphere (like a globe).

The Cities: The "real" cities are placed along the equator of this globe.
The Distances: The distance between two cities isn't measured in miles, but by how far you have to spin the top to get from one city-point to another.
The Goal: The salesman needs to spin the top from city to city, visiting every equator point once, and returning home, while minimizing the total "spinning effort."

2. The Superposition Super-Highway

In the old way, you check Route A, then Route B, then Route C, one by one.
In this new method, the authors use quantum superposition. Imagine the spinning top is a magical traveler who can be in multiple places at once.

Instead of walking one path, the "top" simultaneously explores every possible route at the same time.
It's like sending a thousand explorers down a thousand different roads simultaneously, but they are all the same explorer, just existing in a "superposition" of all paths.

3. The "Brachistochrone" Shortcut

The paper uses a concept from physics called the Brachistochrone problem. Historically, this asks: "What is the fastest path for a ball to roll between two points?"

The authors turned the TSP into a version of this problem. They treat the route-finding as a race against time.
They use a technique called Optimal Control (think of it as a very smart autopilot) to gently nudge and rotate the single qubit.
The autopilot adjusts the "spin" so that the paths that are too long cancel each other out (like noise cancelling headphones), while the shortest path gets amplified and stands out.

4. The Final Check

After the qubit has "traveled" all the routes at once, the scientists measure the final position of the spinning top.

They don't look at every single path. They look at the very end of the journey.
By analyzing the final state, they can work backward to reconstruct the winning route.
It's like watching a magician perform a trick where they shuffle a deck of cards, and by looking at the final card, they can tell you the exact order the whole deck was in.

The Results: What Did They Find?

The team ran computer simulations to test this "One-Qubit" method.

The Test: They solved TSP puzzles with 4 to 9 cities.
The Success: For more than 90% of the problems, their method found the perfect, shortest route.
The Fail-Safe: In the rare cases where they didn't get the perfect answer, they still got a very good approximation (about 90% as good as the best possible).
The Efficiency: They did all this using just one qubit, whereas other methods would have needed dozens or hundreds.

The Bottom Line

This paper doesn't claim to solve the TSP for a million cities tomorrow. Instead, it proves a powerful concept: You don't need a massive quantum computer to solve complex routing problems.

By treating the problem as a geometry puzzle on a single spinning sphere and using the power of "being in many places at once," they showed that a single qubit can efficiently navigate complex mazes. It's a new, resource-light way to think about quantum optimization that could eventually be built on any quantum platform that can spin a qubit accurately.

Technical Summary: Solving The Travelling Salesman Problem Using A Single Qubit

Problem Statement
The Travelling Salesman Problem (TSP) is a fundamental NP-hard combinatorial optimization problem requiring the identification of the shortest possible route that visits a set of cities exactly once and returns to the origin. While classical algorithms exist, exact solutions scale exponentially with the number of cities, and heuristic methods do not guarantee optimality. Existing quantum approaches, such as those utilizing Quadratic Unconstrained Binary Optimization (QUBO) mapped to Ising Hamiltonians or phase-estimation circuits, are resource-intensive. They typically require a large number of qubits (e.g., thousands of physical qubits for a 10-city problem) and often suffer from low success probabilities on current noisy hardware.

Methodology
The authors propose an algorithm that maps an arbitrary TSP onto a single qubit, leveraging the principle of quantum parallelism rather than entanglement. The core methodology involves three main stages:

Mapping to a Discrete Brachistochrone Problem:
The TSP is first reformulated as a finite discrete Brachistochrone problem. In this classical analogy, cities are represented as points on a 2D plane, and routes are linear piece-wise functions. The objective is to minimize a time functional $Q$ , which corresponds to the total travel distance. The problem is constrained such that the path must return to the initial city, encoded by an additional linear segment to a final point $F$ .
Encoding on the Bloch Sphere:
The discrete Brachistochrone problem is mapped onto the geometry of a single qubit's Bloch sphere.
- State Representation: Cities ( $c_i$ ) are represented by quantum states $|P_{ii}\rangle$ located on the equator of the Bloch sphere.
- Distance Encoding: The relative distances between cities are encoded as geometric distances (geodesics) on the sphere. Intermediate states $|P_{ij}\rangle$ are placed on geodesic curves connecting equatorial states to a pole $P_0$ . The angular distance between states corresponds to the Euclidean distance between cities.
- Traversal: Moving between cities is achieved via rotation operators ( $U^u$ and $U^d$ ). A "step" from city $i$ to city $j$ involves an "up" rotation from the equator to an intermediate state $|P_{ij}\rangle$ (closer to the pole) followed by a "down" rotation to the equatorial state $|P_{jj}\rangle$ .
Quantum Optimization via Superposition:
Unlike a brute-force approach that traverses paths sequentially, the proposed algorithm utilizes quantum superposition to traverse multiple paths simultaneously.
- Superposition Creation: The system is initialized in a state corresponding to the starting city. A series of tunable rotation operators creates a superposition state at each layer of the routing chart, effectively exploring all valid and invalid paths at once.
- Optimization: The algorithm employs optimal control methods, specifically the Simultaneous Perturbation Stochastic Approximation (SPSA), to tune the rotation operators.
- Objective Function: While a brute-force quantum approach could minimize a time functional $T$ , the superposition-based approach minimizes the classical cost function $D$ (total distance). This is necessary because the superposition includes "classically forbidden" paths that do not form valid Hamiltonian cycles. The optimization seeks to maximize the population of the valid Hamiltonian cycle in the final state.
- Measurement and Post-Processing: The algorithm concludes with a projective measurement of the penultimate state. Through quantum state tomography, the population distribution is analyzed to identify the dominant path, which corresponds to the optimal TSP route.

Key Results
The authors present numerical simulations solving TSP instances with 4 to 9 cities using a single qubit.

Accuracy: For the tested problem sizes, the algorithm obtained exact solutions (approximation ratio $\sim 1$ ) for more than 90% of the problem instances.
Approximation: In cases where exact solutions were not found, the algorithm achieved high approximation ratios ( $\sim 0.90$ ).
Resource Efficiency: The method requires only a single qubit, a stark contrast to existing quantum algorithms that require hundreds or thousands of qubits for similar problem sizes.
Platform Agnosticism: The algorithm is designed to be implementable on any quantum platform capable of high-fidelity arbitrary qubit rotations and state tomography, including superconducting qubits, trapped ions, nitrogen-vacancy centers, and Rydberg atoms.

Significance and Claims
The paper claims that this approach offers a more resource-efficient and accurate alternative to existing quantum algorithms for small-to-medium TSP instances. By utilizing the superposition principle on a single qubit, the method bypasses the need for large-scale entanglement and extensive qubit counts, addressing a primary bottleneck in current quantum hardware.

The authors discuss a potential polynomial time speed-up over classical algorithms, suggesting that the quantum parallelism inherent in the superposition of paths could provide a practical advantage in both time and accuracy. The work positions the TSP not just as a routing problem but as a specific instance of a constrained Brachistochrone problem solvable via quantum control, opening a pathway for scalable quantum optimization on near-term devices.