Even with the recent decrease in cars on the road, we’ve all had the experience of being stopped at a traffic signal, waiting for the light to turn green, only to be stopped by another red light one block later. Besides being a frustrating driving experience, this inefficient idling time contributes considerably to carbon emissions. If we can optimize the timing of traffic signals to reduce this waiting time, we could improve the flow of traffic and ultimately lessen our impact on the environment.
The challenge with optimization problems like this one is that when the number of variables increases (e.g., volume of vehicles, number of signals, time of day), the computational requirements to calculate the best solution (e.g., efficient signaling time) grows quickly with today’s classical computers.
In nature, we find efficient solutions to complex optimization problems that can be a great source of inspiration when designing new algorithms. Nature speaks the language of quantum mechanics and emulating these unique quantum properties can lead to powerful new optimization techniques. For example, by emulating quantum tunneling on classical hardware we can efficiently find solutions to instances of hard combinatorial problems. Similarly, by using tempering techniques like those used in metallurgy when hardening steel, we can efficiently solve hard optimization problems.
In Azure Quantum, we have developed optimization techniques inspired by natural processes for binary optimization problems. This approach allows for the native encoding of higher-order interactions on an all-to-all graph, meaning that no mapping or embedding is needed, ultimately unlocking applications that are seemingly intractable.
Jij Inc. and Toyota Tsusho are working together to begin tackling mobility and traffic challenges using quantum-inspired optimization (QIO) in Azure Quantum. Founded in 2018 by theoretical physicists, Japanese startup Jij helps businesses like Toyota Tsusho experiment with new computing techniques and apply quantum research to solve real-world problems.
Traditional methods for traffic signal optimization treat each vehicle independently in large-scale simulations that are computationally expensive and slow. Those methods are unable to factor in higher-cost variables, such as the correlation of traffic flow between signals.
To help Toyota Tsusho find a better solution, Jij proposed a Polynomial Unconstrained Binary Optimization (PUBO) formulation, requiring higher-order terms. Solving this PUBO representation of the problem using QIO in Azure Quantum, Jij and Toyota Tsusho were able to reduce car waiting times by 20% when compared to traditional methods with large-scale simulation.
We previously had to simulate traffic for each individual light to find an improved sequence, but that approach was limited because we couldn’t factor in the time correlation of traffic flow between lights. Now with Azure Quantum, we can address this problem from a more systems-level approach. Collaborating with Toyota Tsusho, we seek to improve the timing of large-scale traffic networks, resulting in potential economic and environmental benefits for many cities.
– Kohji Nishimura, CTO, Jij
By building on the same foundational principles as nature, we are moving towards a vision of optimizing entire holistic environments in a way that is not possible with today’s classical systems—fundamentally changing the way people, goods, and services move through cities, countries, and around the world.
Microsoft is partnering with Microsoft Quantum Network members like Jij to realize this vision by supporting their development of practical solutions and accelerating customer impact through Azure Quantum.
Jij and their early work on traffic signal optimization with Toyota Tsusho is a first step toward preparing for a world where scaled quantum computers are more readily available.
We are looking forward to seeing the progress toward a changing transportation landscape—where economic and environmental benefits are increased in cities around the world, ultimately improving the quality of life for all.
For a third-party perspective on our work with Jij and Toyota Tsusho, check out this recent article from The Wall Street Journal. If you would like to learn more about quantum-inspired optimization or ways you can get involved with Microsoft Quantum and Azure Quantum, please reference the links below.