Quantum traffic zone partitioning improves with smarter subproblem selection
Fewer Qubits, Better Choices: Coupling-Aware Sub-QUBO Selection for Quantum-Assisted Traffic Zone Partitioning
Emerging Technologies
Summary
Quantum computers that aim to solve traffic planning problems must break big problems into smaller pieces. The authors found that the usual way to pick parts of the problem to solve misses important connections between variables. They proposed a new method that looks at pairs of variables together, helping to choose better smaller problems to feed quantum computers. Their approach works better even with fewer quantum bits, showing selection matters more than just having bigger quantum devices.
What this means in practice
- •For transportation planners: Partition urban traffic zones more efficiently by selecting interacting road segments before quantum optimization.
- •For quantum software developers: Improve quantum-assisted optimization workflows by using pairwise interaction-based variable selection to reduce problem size without losing solution quality.
Authors
Qianwen Guo, Ruimin Ke
Abstract
Near-term quantum optimizers accommodate roughly a hundred binary variables, requiring large Quadratic Unconstrained Binary Optimization problems to be decomposed into hardware-sized subproblems while other variables remain fixed. Variables are typically selected by ranking the objective changes from individual flips. We show that this rule is uninformative once the incumbent is optimal under single-variable flips: every score represents a cost, while remaining improvements depend on overlooked pairwise interactions. A second-order expansion instead yields a prize-collecting densest-subgraph selection problem, solvable greedily in time linear in the number of variables, and two solver-free bounds bracketing the improvement achievable within a selected subset. On transportation networks from Chicago and Philadelphia, our rule with 16-variable subproblems outperforms random selection with 64, demonstrating that quadrupling device capacity cannot compensate for weaker selection. Replacing geometric adjacency with road-network connectivity widens the margin by a factor of 1.6-1.9. With the selection trace fixed, varying the fraction of subproblems solved on a 120-qubit device from zero to one leaves the final objective unchanged to six significant figures. At tested hardware-accessible sizes, gains therefore arise from selection rather than the backend. Hardware feasibility is limited by coupling terms: 120-variable problems fail to compile with 7,260 terms but succeed with 5,118. Compilation scales almost quadratically with term count and dominates execution cost, reaching 1,752 seconds versus 469 seconds of quantum processing.