Quantum physicists have created an algorithm that utilizes just one qubit to solve a problem that previously required thousands. Quantum computing promises significant advancements in computational capabilities, with the potential to manage hundreds of thousands or even millions of quantum bits, or qubits. However, current state-of-the-art machines are limited to just a few dozen qubits and have not yet demonstrated superior performance compared to classical computers. One challenge is that many quantum algorithms require hundreds or thousands of qubits, even for relatively simple problems. As a result, mathematicians and computer scientists are actively seeking more efficient algorithms that can operate with fewer qubits.

Kapil Goswami and colleagues at the University of Hamburg in Germany have developed a method to solve the Travelling Salesperson Problem using just a single qubit.[1] They believe this approach could be extended to other problems and may significantly influence how computer scientists conceptualize quantum algorithms.

Figure 1. 1-Qubit Quantum Algorithm Solves Traveling Salesperson Problem

The Travelling Salesperson Problem is a combinatorial optimization problem and one of the most extensively studied challenges in mathematics. The goal is to find the shortest route that visits every city on a given list exactly once. Mathematically, the only known method to solve this problem is to calculate the lengths of all possible routes and select the shortest one. Figure 1 shows 1-Qubit Quantum Algorithm Solves Traveling Salesperson Problem.

This task is manageable when the number of cities is small. However, as the number of cities increases, the number of possible routes grows at a factorial rate, denoted by n!. For example, with 4 cities, there are 24 possible routes (4!), but with 10 cities, there are 3,628,800 possible routes (10!), and with 100 cities, the number jumps to an astronomical 9 x 10^157 (100!). This exponential growth quickly renders the problem unsolvable for even the most powerful conventional computers.

Graceful Sphere

Instead of finding exact solutions, computer scientists have developed algorithms that calculate optimal routes, which may not be the absolute shortest but are likely within a few percent of it. However, these algorithms also become computationally intensive as the number of cities increases.Quantum computing has been expected to accelerate these algorithms. However, according to Goswami and colleagues, even the best quantum algorithms require a large number of qubits. They note, "The quantum algorithm for encoding 9 and 10-city problems on a D-wave quantum architecture requires 73 logical qubits or 5436 physical qubits."

Reducing the problem to just one qubit is a significant breakthrough. Goswami and colleagues utilize a method of representing the state space of a quantum system as a geometric globe known as a Bloch sphere. They map the locations of cities as quantum states on this sphere, with the process of traveling from one city to another represented by a series of rotations of the sphere.The sphere can actually represent the routes between all cities simultaneously through the concept of superposition. "We use the superposition of states to travel through multiple paths at once," they explain. By making the appropriate measurement of the quantum state, it becomes possible to select the optimal route.

This method is compatible with any quantum computer capable of rotating a qubit in various ways, including superconducting machines, trapped ion platforms, and nitrogen-vacancy centers in diamond, among others.The results have proven to be significantly better than those 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 colleagues.

For larger numbers of cities, the quantum states must be packed more closely together on the surface of the sphere, making them more susceptible to noise and errors. Despite this, the team has successfully applied their method to problems involving up to nine cities.

Quantum Query

This work is indeed fascinating with considerable potential. The team notes that visualizing problems mapped onto a geometric sphere represents a significant advancement, as it paves the way for mapping other problems similarly. "Our scheme will serve as a template for developing algorithms that leverage the superposition principle for resource efficiency," the researchers state.

They highlight that searching through a superposition of states on a Bloch Sphere is mathematically akin to Grover’s quantum search algorithm, one of the simplest and most powerful quantum algorithms known for its dramatic speedup over classical algorithms. [2] This suggests that this approach should achieve a comparable enhancement in performance. Although quantum computers currently face challenges such as noise and limited qubit counts, the Bloch Sphere concept emerges as a promising new tool in the quantum toolkit.

References:

1. http://arxiv.org/abs/2407.17207
2. https://www.discovermagazine.com/technology/quantum-algorithm-solves-travelling-salesperson-problem-with-1-qubit

Cite this article:

Janani R (2024), A Quantum Algorithm Solves the Travelling Salesperson Problem Using Only 1 Qubit, AnaTechMaz, pp.146