Traffic congestion in Seattle can get so bad that it seems as if you need a next-generation quantum computer to make sense of it — and that’s exactly what Microsoft and Ford are aiming to do.
The quantum frontier hasn’t yet reached the point at which a general-purpose computer can solve the mother of all traffic jams. But the two companies are using quantum-inspired simulations to address the optimization problem that arises when all the drivers are following the same app-generated driving directions.
“While we’re still in the early stages of quantum computing development, encouraging progress has been made that can help us take what we’ve learned in the field and start to apply it to problems we want to solve today, while scaling to more complex problems tomorrow,” Ken Washington, chief technology officer at Ford Motor Company, wrote today in a Medium post.
Washington said researchers at Ford and Microsoft teamed up last year to develop new quantum-style approaches to help reduce Seattle’s traffic congestion.
One of the big problems is that traffic apps tend to send individual drivers along the same routes. Even when congestion on one route triggers the app to suggest an alternate, that alternate route soon becomes jammed up as well. “Simply put, it’s not feasible to have traditional computers find the optimal solution from a huge number of possible route assignments in a timely manner,” Washington said.
That sort of optimization problem is tailor-made for quantum computers. Instead of processing bits of data as a succession of ones and zeroes, quantum computers work with quantum bits — or qubits — that can represent multiple values until the computation’s results are read out. Such an approach can sift through a multitude of possibilities that would bog down the quickest classical computer.
For their optimization experiment, the experts at Ford and Microsoft used algorithms that simulate the quantum approach on classical computers.
“We don’t have to wait until quantum computers are deployed on a wide scale to take advantage of the technology,” Julie Love, Microsoft’s senior director for quantum computing, explained in the Medium post. “Using world-class quantum algorithms customized for specific problems, we can bring measurable improvements and drive change that can impact people’s lives.”
The team tested several different scenarios, including one that involved as many as 5,000 vehicles simultaneously requesting routes that spanned the Seattle area. Each simulated driver had 10 different routes available to them.
“In 20 seconds, balanced routing suggestions were delivered to the vehicles that resulted in a 73 percent improvement in total congestion when compared with ‘selfish’ routing,” Washington said. “The average commuting time, meanwhile, was also reduced by 8 percent — an annual reduction of more than 55,000 hours saved in congestion across this simulated fleet.”
Washington said the results were promising enough to lead Ford to expand its partnership with Microsoft. The next phase of the traffic study will look at scenarios that come closer to real-world situations.
“For example, will this method still deliver similar results when some streets are known to be closed, if route options aren’t equal for all drivers, or if some drivers decide to not follow suggested routes? These and more are all variables we’ll need to test for to ensure balanced routing can truly deliver tangible improvements for cities,” Washington said.
The results could be used to improve navigation apps, and could also be applied to optimization problems in fields ranging from robotics to aerodynamics.
Microsoft isn’t Ford’s only partner when it comes to traffic optimization: The automaker has also been working with NASA’s Quantum Artificial Intelligence Laboratory at Ames Research Center, where Burnaby, B.C.-based D-Wave Systems’ quantum annealing hardware comes into play. The NASA-Ford partnership focuses on using quantum-inspired algorithms to optimize energy consumption by commercial vehicle fleets.
Separately, Ford has set up a City Insights Platform to study urban mobility issues in depth. It’s all part of Ford’s drive to think of itself as a mobility company rather than strictly a car company, particularly as it closes in on fielding fully autonomous vehicles in 2021.
On the flip side, Ford is far from being Microsoft’s only partner when it comes to real-world applications of quantum computing: Just last month, the Redmond, Wash.-based tech titan rolled out its cloud-based Azure Quantum computing platform. It’s also working with Willis Towers Watson on financial risk management, and with Case Western Reserve University on medical applications.