arXiv preprint ·
Fewer Qubits, Better Choices: Coupling-Aware Sub-QUBO Selection for Quantum-Assisted Traffic Zone Partitioning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
VehDyn: A Driving World Model Benchmark for Vehicle Dynamics
Phenomenon-Graph JEPA: Label-Efficient Representation Learning for Contactless Cardiorespiratory Sensing
Who Gets a Token, and What Does It Carry? Unequal Name Support and Concept Access in Large Language Models
Modeling quantum neural network gradient with reinforcement learning
DPS: Dual-Mode Precision LLM Serving with Semi-Unified Memory
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.