It’s hot and you’re sweating. You’ve been in a traffic jam for hours. Guesses are you’ve moved over sixty thousand inches, at most (that’s a mile). Now you’re getting nervous. The air con’s not working and making it all the worse. You feel like shooting someone, just like Michael Douglas in Falling Down.
‘I’m the worst person to be stuck with in a traffic jam.’
— Larry King
You could blame the city planners. Your own goddamn impatience for not checking the GPS or map beforehand to seek out a better route.
But it’s too late now. You’re going to miss your daughter’s birthday party.
We’ve all been there, more than once, I bet. Traffic. The scourge of the big city. Moscow. Ciudad de México. Paris and Rome. They’ve all got the problem of too many cars and not enough roads to hold them.
Yet there could be a solution.
Reports out of German auto-manufacturer, Volkswagen AG, claim they have managed to demonstrate — for the first time ever— the optimization of traffic routing using a quantum computer. The achievement happened in Lisbon, Portugal, during a WebSummit technology conference. In the demonstration, nine public transit buses, covering 26 stops, four bus links and thousands of passengers, employed a traffic management system designed by scientists at Volkswagen AG which can determine, via quantum calculations, the quickest, most efficient route to take in almost real-time. The system itself utilized D-Wave’s quantum computer.
‘Volkswagen is forging ahead with practically-oriented research on quantum computers and is gaining essential specialist knowledge. We want to gain an in-depth understanding of applications of this technology which could be beneficial to the company, including traffic optimization. Public transport organizations and taxi companies in large cities are highly interested in managing their fleets efficiently. Our quantum-optimized traffic management system could help make that a reality.’
— Florian Neukart, Principal Scientist at Volkswagen’s CODE Lab in San Francisco
The Travelling Salesman
The travelling salesman problem (TSP) has had many smart men scratching their heads for over two hundred years, ever since it was formulated by mathematicians W.R. Hamilton and Thomas Kirkman, though the math to the solution at the time was rudimentary at best. It was not until the 1930s that American mathematician Merrill M. Flood thought serious mathematical solutions could solve the conundrum.
Decades passed. Many great people in the fields of physics, mathematics, computer science, and chemistry offered solutions.
Some of them were better than others:
The Miller-Tucker-Zemlin formulation.
The Dantzig-Fulkerson-Johnson formulation.
The Christofides algorithm.
Euclidean and asymmetric blah blah blah.
And my personal favourite:
Ant colony optimization.
The computational complexity of these NP-hardness solutions has never lacked intellectual integrity. Nor effort.
The human brain, with a pencil and paper as accoutrements, has done a lot over the last six thousand years (okay, animal hides and charcoal, notwithstanding). The bits of a classical computer more recently, as well, have worked their asses off to achieve an intellectual apotheosis.
But we have quantum computers now. Electrons and photons doing the donkey work. The way advanced computing has progressed over, let’s say the past twenty years, has brought us to a point where traffic — and the problems it can bring to businesses and governments — can be a thing of the past.
Global Positioning System (GPS), the modern navigation system that first came on the market for mass consumption in the early 2000s, was revolutionary when it appeared. Gone were the clumsy, gigantic fold-out maps for finding one’s way from street to street or town to town. Things became, at last, considerably easier to locate. You didn’t have to have a degree in geography or the genes of Vasco Da Gama to get from A to B.
Hatchechubbee, Alabama was as easy to locate as Manhattan.
Now we could all be explorers.
Modern navigation systems can find anywhere on the planet, or almost, creating a virtual map that considers the quickest way to get from point to point.
Yet for all its advantages, the modern GPS can’t do one thing: take the calculations and routes of other drivers into consideration.
This, in turn, can create a situation where individual GPSs choose the same route. What happens is too much traffic gets directed to that one said route, causing — you guessed it — a traffic jam.
Bottlenecks No More
The system devised by Volkswagen AG, which uses a data management system and an algorithm on D-Wave’s quantum annealer hardware, can potentially shorten calculation times in regard to traffic optimization across all vehicles and their routes at the same time. This would generate a situation where traffic flow would not be directed in one ‘optimally’ calculated route, which only considers the individual driver’s location, but spread out the logistical situation, taking the whole traffic flow into consideration using many routes to avoid bottleneck scenarios to keep the traffic flowing as fluidly as possible.
So, in the words of the late, great crooner Leonard Cohen:
‘A sip of wine, a cigarette, and then it’s time to go. I tidied up the kitchenette; I tuned the old banjo. I’m wanted at the traffic-jam. They’re saving me a seat’
It could be that with a QC system devised by Volkswagen AG in collaboration with D-Wave — along with another automotive giant, Ford, which recently announced to the press about their own project in traffic flow optimization using QC — the era of the traffic jam, using quantum hardware and software as a solution, could well be a thing of the past.