#CF-QAOA

[govindhtech]

QAOA For Traffic Jams: A Hybrid Quantum Algorithm Approach

Recent research considers hybrid quantum algorithms, notably QAOA, to solve traffic congestion through optimised route planning.

In an arXiv post, Ford Motor Company and University of Melbourne researchers proved that a hybrid quantum algorithm may minimise traffic bottlenecks. Despite noisy hardware and limited circuit depth, their solution outperformed quantum methods on current real-world CPUs.

The paper examines the Quantum Approximate Optimisation Algorithm (QAOA), a potential quantum tool. In optimisation circumstances, QAOA is ideal for finding the best answer among numerous possibilities. It works effectively for city traffic management to reduce highway congestion.

Researchers created a mathematical Quadratic Unconstrained Binary Optimisation (QUBO) model to solve the traffic problem. They created variables that represent each vehicle's probable pathways and assigned a cost that climbs when more vehicles utilise the same road stretch. This model accommodates real-world constraints including the necessity for each car to travel exactly one route and penalises busy routes to prevent overlap. We get a cost function that QAOA can solve and map onto a quantum system.

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 offered each car a list of possible routes from its starting point to its goal. Routes are walkways with road-like borders. Every route begins and ends at the origin and destination nodes, which were always intersections for simplicity.

Using QAOA for Cheap Solutions

The group utilised QAOA to find cheap fixes after encoding. QAOA circuits use alternating layers of quantum gates and need precise parameter adjustments. Optimising these features is difficult, especially with noise. A major contribution of the work was evaluating precomputed values, random estimates, and quantum annealing-influenced approaches for initialising these parameters.

Trotterized Quantum Annealing (TQA) outperformed conventional initialisation approaches. Since it models the system's steady progression from basic to sophisticated, TQA often yields better results than random starting. The researchers also found that precalculated parameters from simulations of similar traffic circumstances often yielded results virtually as good as fully optimised trials at a far lower processing cost.

Make Noise

After verifying their technique in simulations, the researchers ran their QAOA circuits on IBM quantum hardware. Noise and hardware limits limited performance as expected. Standard QAOA circuits need two-qubit operations between qubits that may not be physically linked on the semiconductor. To fix this, devices utilise “SWAP” gates to shuffle data among qubits, but this adds overhead and inaccuracy.

To avoid SWAP operations in two-qubit gates, the researchers created Connectivity-Forced QAOA (CF-QAOA). Despite changing the quantum circuit and presumably diminishing its precision, eliminating these gates enhanced noisy device performance.

They added greater customisability to CF-maQAOA, a second version that compensates for missing gates. This strategy outperformed traditional optimisation in practice while being more sophisticated.

The researchers also examined how their strategy develops with the challenge. QAOA was compared against Gurobi, a commercial classical solver known for its optimisation performance. When there were more cars and variables, standard QAOA ran slower than Gurobi. The CF-QAOA technique showed comparable scaling patterns after noise correction.

Work to Come

Using quantum computers to minimise traffic congestion may lower the environmental impact of idle cars and help always-late people make their appointments.

Due to quantum gear constraints, the research acknowledges that these developments won't improve matters in the future. Deep circuits create too much noise, and even little qubit connection changes can affect findings. Further study is needed to establish if improved compression approaches may retain performance while reducing complexity and how circuit simplifications influence quantum properties like entanglement.

The study concludes that hybrid quantum optimisation is effective for traffic control. By adjusting algorithms to hardware restrictions and accepting approximate answers, the researchers demonstrate that quantum computing can develop even in the noisy, pre-error-corrected period.

The University of Melbourne established an IBM Quantum Network Hub to aid this effort.