arXiv:2609.32627
Fewer Qubits, Better Choices: Coupling-Aware Sub-QUBO Selection for Quantum-Assisted Traffic Zone Partitioning
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.
AI Summary
The paper studies how to select hardware-sized variable subsets when decomposing a large QUBO, using traffic-zone partitioning as the application. It focuses on a limitation of selection based on individual-flip objective changes: at a single-flip local optimum, all such changes are non-improving, while improvements involving multiple variables depend on pairwise couplings. A second-order expansion formulates subset selection as a prize-collecting densest-subgraph problem. The proposed greedy selection procedure is reported to run in time linear in the number of variables. The paper also derives two solver-free bounds bracketing the improvement achievable within a selected subset; their explicit forms are not provided in the abstract. Tests on Chicago and Philadelphia transportation networks find that coupling-aware selection with 16-variable subproblems outperforms random selection with 64-variable subproblems. Using road-network connectivity rather than geometric adjacency increases the reported margin by a factor of 1.6–1.9. With the selection trace held fixed, varying the fraction of subproblems assigned to a 120-qubit device from zero to one leaves the final objective unchanged to six significant figures, attributing the observed gains at tested sizes to selection rather than the backend. Hardware feasibility depends on coupling count: 120-variable instances fail compilation with 7,260 terms but succeed with 5,118. Compilation scales almost quadratically with term count and reaches 1,752 seconds, compared with 469 seconds of quantum processing. The reported evidence is limited to the tested networks and hardware-accessible sizes.
Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.