Could a quantum computer help future road trips?
—by Jacinta May
You may have heard of the problem of the Travelling Salesman. A travelling salesperson is given a list of cities and the distances between each pair of cities. They are then tasked with figuring out:
What is the shortest possible route that visits each city once (and only once) and then returns to the original city?
You can imagine that this dilemma chimes very closely with what our road-trippers were challenged with when mapping out our route. However, our road-trippers have an approach at their disposal that our poor salesperson does not—quantum computation.
Could a quantum computer really help our road-trippers out?
The quandary may appear a simple statement, but do not be deceived. The salesperson’s task is no mean feat; in fact, the problem is so complex that it has stumped even the most powerful classical supercomputers on the planet.
This is because the problem of the travelling salesman belongs to a particular class of problems in combinatorial optimisation—the NP-Hard problems. The solution to an NP-Hard problem can only be verified in polynomial time (this means that for a problem with n cities, the solution may be verified with fewer than nk tries at it), as opposed to a so-called P-problem, which can actually be solved in polynomial time. Naturally, P-problems are much less complicated and are easily handled by classical computers every day.
NP-problems are incredibly complex, but are also of vital importance in the field of computer science. Finding an algorithm that can solve NP-problems in polynomial time represents a Holy Grail for computing research, as solving one NP-problem will open the door to solving the thousands of other complex problems within the NP-family.
Why are quantum computers being used to attack these problems?
Well, the very nature of quantum computing allows for a very different approach to finding solutions. Using the strangeness of quantum mechanics, a quantum computer has ability to perform certain tasks at an exponentially faster rate than classical computers.
It is important to note that quantum computers may very well never be able to solve the Travelling Salesman Problem in polynomial time. But the possibilities of their problem-solving capabilities will have much further reach than the current threshold of what classical computers can achieve.
So, our road-trippers may be unable to delegate the logistical tangle of scheduling to a quantum computer just yet. Although, perhaps next year, they (paying due diligence to our quantum research) will be able to rely on the strangeness of quantum mechanics for enhanced precision GPS technology to ensure we don’t get lost as we implement our very own solution of the Travelling Salesman Problem!