Fewer Qubits, Better Choices: Coupling-Aware Sub-QUBO Selection for Quantum-Assisted Traffic Zone Partitioning

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.