Quantum Algorithm Solves Travelling Salesperson Problem With 1-Qubit

Quantum computing offers the hope of dramatic increases in computational capabilities. That’s the promise of quantum computers that can handle hundreds of thousands or millions of quantum bits or qubits.

But for the moment, the state-of-the-art machines barely manage a few dozen qubits and cannot yet outperform classical computers in any meaningful way. Part of the problem is that quantum algorithms generally require hundreds or thousands of qubits, even for simple problems. So mathematicians and computer scientists are desperately searching for more elegant algorithms that depend on fewer qubits.

Enter Kapil Goswami and colleagues at the University of Hamburg in Germany who have found a way to solve the travelling salesperson problem using a single qubit. They say the approach could be applied to other problems and has the potential to transform the way computer scientists think about quantum algorithms.

The Travelling Salesperson Problem a combinatorial optimization problem and one of the most intensively studied puzzles in mathematics. The challenge is to find the shortest route that visits every city on a given list. As far as mathematicians know, the only way to do this is to calculate the length of all the routes and then pick the shortest.

That’s straightforward when the number of cities is small. But as this number grows, the possible routes increase at a rate that depends on n!, the factorial of the number of cities. So 4! is 24 but 10! is 3,628,800 and 100! is 9 x 10^157. So this quickly becomes impossible for even the most powerful conventional computers.

Elegant Sphere

So instead of finding exact solutions, computer scientists have developed algorithms that calculate optimal routes, ones that may not be the shortest but are probably within a few percent of that. But even these are computationally intensive when the number of cities is large.

Quantum computing has long promised to speed up these algorithms. But Goswami and co say even the best quantum algorithms require a large number of qubits. “The quantum algorithm for encoding 9 and 10-city problems on a D-wave quantum architecture requires 73 logical qubits or 5436 physical qubits,” they say.

Shrinking this down to just 1 qubit is therefore a significant advance. Goswami and co exploit a way of representing the state space of a quantum system as a geometric globe, known as a Bloch sphere. They then represent the location of cities as quantum states on a Bloch sphere. So the process of travelling from one city to the next can be achieved through a series of rotations of the sphere.

In fact, it is possible for the sphere to represent the routes from each city to all the others by the process of superposition. “We use the superposition of states to travel through multiple paths at once,” they say. It is then possible to select the optimal route by through the appropriate measurement of the quantum state.

This method works with any quantum computer that has the capability to rotate a qubit in any fashion. So that includes superconducting machines, trapped ion platforms machines, nitrogen-vacancy centers in diamond and so on.

The results turn out to be significantly better than has previously been achieved with much larger devices. “We show that for four- to six-city Travelling Salesperson Problems, the algorithm finds the exact solution for most of the problem instances, which is much better than the current quantum schemes,” say Goswami and co.

For larger numbers of cities, the quantum states end must be packed more closely together on the surface of the sphere and this makes them more vulnerable to noise and errors. Nevertheless, the team have had success with up to 9-city problems.

Quantum Search

That’s fascinating work with significant potential. The team say that the process of visualizing problems mapped onto a geometric sphere is itself an important advance because it immediately opens the way to map other problems in the same way. “Our scheme will act as a template to further develop algorithms that utilize the superposition principle for resource efficiency,” say the researchers.

In particular, the team point out that the search through a superposition of states on a Bloch Sphere is mathematically similar to Grover’s quantum search algorithm, one of the simplest and most powerful quantum algorithms and one which is dramatically faster than classical algorithms. This suggests that however it is applied, this approach should achieve a similar speed up compared to classical algorithms.

While quantum computers continue to be noisy machines with limited numbers of qubits, this sets up Bloch Spheres as a promising new tool in the quantum armory.

Ref: Solving The Travelling Salesman Problem Using A Single Qubit : arxiv.org/abs/2407.17207