According to recent research, it explores the application of hybrid quantum algorithms, specifically QAOA, to tackle the complex problem of traffic congestion through optimized route planning.
Researchers from Ford Motor Company and the University of Melbourne showed that a hybrid quantum algorithm may be used to reduce traffic bottlenecks in an article published on the pre-print service arXiv. Their methodology demonstrated promising results, even surpassing traditional quantum methods on modern real-world processors, despite noisy hardware and restricted circuit depth.
One of the most promising instruments in the present quantum toolbox, the Quantum Approximate Optimisation Algorithm, or QAOA, is the focus of the study. For optimization situations, where the objective is to identify the optimal solution among several options, QAOA is especially well-suited. In this instance, it is well adapted to the problem of arranging automobile traffic in a city so as to minimise congestion on public highways.
In order to accomplish this, the researchers transformed the traffic issue into a Quadratic Unconstrained Binary Optimisation (QUBO) model, a mathematical framework. They allocated a cost that rises when more than one vehicle uses the same road section, and they constructed variables that reflect potential paths for every automobile. This model is adaptable enough to take into account real-world limitations, such as the need that each automobile travel exactly one route, and discourages overlap by penalising routes with significant traffic. The end product is a cost function that can be solved with QAOA and mapped onto a quantum system.
The team writes: “By defining decision variables that correspond to each car’s route, the problem of reducing road congestion can be modelled as a binary combinatorial optimisation problem.” We gave each automobile a list of potential paths to take from its starting point to its final destination. A route is a walkway with edges that match sections of a road. The origin and destination nodes, which were always selected to be at intersections for simplicity, are where each route starts and finishes, respectively.
Using QAOA For Low-Cost Solutions
After encoding, the group used QAOA to identify affordable fixes. Alternating layers of quantum gates make up QAOA circuits, which rely significantly on a set of parameters that need to be precisely adjusted. It is challenging to optimise these characteristics, particularly when noise is present. Evaluating several methods for initialising these parameters, such as precomputed values, random guesses, and methods influenced by quantum annealing, was one of the study’s main contributions.
A approach known as Trotterized Quantum Annealing (TQA) fared better than the other initialization methods that were examined. TQA can frequently come closer to the correct answer than a totally random start since it simulates the system’s slow transition from a basic to a complex state. Additionally, the researchers discovered that employing precalculated parameters identified through simulations of comparable traffic situations frequently produced results that were almost as excellent as completely optimised runs, but at a far reduced computing cost.
Bring on The Noise
The researchers used IBM’s quantum hardware to run its QAOA circuits after confirming their methodology in simulations. As anticipated, performance was hampered by hardware constraints and noise. Two-qubit operations between qubits that might not be physically coupled on the semiconductor are necessary for standard QAOA circuits. Devices use “SWAP” gates, which shuffle data across qubits, to get around issue, although this method adds a lot of overhead and increases inaccuracy.
The researchers developed a variation known as Connectivity-Forced QAOA (CF-QAOA) to counteract this, removing the need for SWAP operations in two-qubit gates. It’s interesting to note that, although altering the quantum circuit and theoretically decreasing its accuracy, deleting these gates significantly improved performance on noisy devices.
They went one step further with CF-maQAOA, a second variation that compensates for the lost gates by adding more customisable settings. Despite making the conventional optimisation more complicated, this method produced even better outcomes in practical settings.
Additionally, the researchers looked into how their approach grows in size as the problem does. Gurobi, a commercial classical solver renowned for its superior performance on optimisation problems, was contrasted with QAOA. Standard QAOA performed worse than Gurobi in terms of runtime, particularly when there were more vehicles and variables. However, CF-QAOA approached, displaying comparable scaling patterns even after accounting for noise.
Future Work
Using quantum computers to reduce traffic congestion might lessen the environmental effect of idle automobiles, in addition to making it more likely that those who are always late will reach their appointments on time.
The report does concede, though, that these advancements won’t make things better in the future because current quantum gear is still a constraint. Too much noise is introduced by deep circuits, and even little variations in qubit connection can have a big impact on results. Further research is required to determine whether improved compression techniques can maintain performance while lowering complexity, as well as how circuit simplifications affect quantum characteristics like entanglement.
In the end, the study makes a strong argument for hybrid quantum optimisation as a useful technique for real-world issues like traffic control. The researchers show that significant advancements may be achieved even in the noisy, pre-error-corrected period of quantum computing by adapting algorithms to the limitations of existing hardware and acknowledging that approximate solutions are sometimes enough.
The University of Melbourne provided assistance for this endeavour by setting up an IBM Quantum Network Hub on campus.
