Coupling Aware Subqubo Selection

---
name: coupling-aware-subqubo-selection
description: Use when splitting a large QUBO into sub-problems for hybrid solvers.
category: ai_collection
---

# Coupling-Aware Sub-QUBO Selection (DkS Selector)

Source: "Fewer Qubits, Better Choices: Coupling-Aware Sub-QUBO Selection for Quantum-Assisted Traffic Zone Partitioning" (arXiv:2609.32627, Guo & Ke, Sep 2026). Tested on Chicago-Sketch (387 zones) and Philadelphia (1,525 zones), IBM ibm_rensselaer via Kipu Iskay DCO optimizer.

## When to Use

- A QUBO/Ising problem has more binary variables than the device (or exact classical solver) can handle, so you decompose it into an outer loop of q-variable sub-problems (qbsolv-style sub-QUBO).
- The incumbent is already 1-opt optimal (no single flip improves) and progress has stalled.
- Any hybrid classical/quantum optimization where "which variables to release this round" is a free design choice.

## Core Insight

**Single-variable impact ranking is blind at a local optimum.** The outer loop spends nearly all its time at 1-opt optima, where every individual flip is a cost (`a_i >= 0` for all i). All remaining improvement lives in the pairwise coupling matrix K, which impact indexing never reads. Selection must be driven by couplings, not by per-variable scores.

## The Method

### 1. Flip-space expansion (compute once per round, no solver calls)

At incumbent x, with `s = 1 - 2x` (flip direction), gradient `g = h + Jx`:

```
H(x') - H(x) = a^T z + (1/2) z^T K z
a_i = s_i * g_i            # individual flip cost/gain
K_ij = s_i * s_j * J_ij    # pairwise correction when i, j flip together
```

z in {0,1}^N indicates flipped variables. K inherits J's zero diagonal. Both a and K are free to compute — this is the key that makes selection tractable.

### 2. Field folding (do NOT skip when clamping)

Fixed variables still act on free ones through a folded field:

```
d_i = sum_{j not in S} (Q_ij + Q_ji) * x_j
```

Omitting this term silently solves a different problem.

### 3. DkS selector (prize-collecting densest-k-subgraph, greedy)

Sub-QUBO objective value F(S) is monotone but NOT submodular (variables can be purely complementary: F({x1})=F({x2})=0 but F({x1,x2})=2.9). Relax to negative-part couplings `[K_ij]^- = max(0, -K_ij)` and maximize the lower bound:

```
max_{|T| <= q}  sum_{i<j in T} [K_ij]^-  -  sum_{i in T} a_i
```

Find q nodes densely connected by strong negative couplings while individually cheap. Greedy: seed with best pair, add one variable at a time by incremental score. Cost O(qn) per round.

**Seed score must be (the easy-to-get-wrong detail):**

```
M_ij = max(-a_i - a_j - K_ij, -a_i, -a_j)
```

Take all three terms — "flip both" AND both "flip just one" options. Using only the first term stalls the greedy whenever no pair is jointly profitable.

### 4. Selection-quality certificate (bounds, O(q^2), no solver call)

```
L(S) = max(0, max_i(-a_i), max_{i<j}(-a_i - a_j - K_ij))
U(S) = sum_i [a_i]^- + sum_{i<j} [K_ij]^-
```

L(S) <= F(S) <= U(S). **Use L for stopping rules, never U** — U keeps spiking long after convergence because it sums every locally favorable term without checking joint attainability.

### 5. Diversification (tabu penalty)

```
tau(t+1) = 0.8 * tau(t) + 1_{S(t)}
a~(t) = a(t) + eps * tau(t)
```

Geometric decay rho=0.8 gives memory of ~1/(1-rho)=5 rounds. Without this, deterministic rules propose near-identical subsets every round; impact indexing depends on it by a measured factor of 4-6x, DkS much less.

## Key Empirical Results

| Finding | Number |
|---|---|
| DkS @ q=16 beats random @ q=64 (Philadelphia) | 4x device capacity does NOT close the gap |
| Road-network vs geometric adjacency | advantage widens 1.6-1.9x; changes 62% of edges |
| Quantum vs classical sub-solver (0-100% hardware fraction, same trace) | final objective identical to every digit — gain is ALL classical selection |
| q=120 dense coupling (7,260 terms) | fails 3/3 as compiler rejection at 282s, not timeout |
| q=120 at 70% sparsification (5,118 terms) | succeeds, ratio 0.9981, compile 1752s vs QPU 469s |
| Compilation scaling | ~1.5e-4 * terms^1.89 s (R2=0.999), crosses QPU cost at ~2,500 terms |
| Wall-clock vs QPU time | queueing dominates: QPU share 5.7%, 39x spread on identical jobs |

## Practical Guidance (Section 6 of paper — transferable)

1. **Diagnose before applying**: compute CV (coefficient of variation) of off-diagonal |K| entries. Real instances: 2.92 and 6.05, rule wins comfortably. Synthetic near-uniform instance CV=0.58, indistinguishable from random. A near-uniform coupling matrix carries no exploitable information.
2. **Never rank by single-flip scores at a local optimum** — all flips are costs there; if forced to use one, it needs external diversification (4-6x dependence).
3. **Stopping rule: lower bound L, 5 consecutive empty rounds** (runs recovered gain at round 15 after empty rounds 13-14; tabu needs ~5 rounds to redirect selection).
4. **Size sub-problems by coupling TERM count, not qubit count** — compilation is the binding constraint and grows ~quadratically in terms; qubit-count planning produces mysterious compilation errors, not capacity errors.
5. **Report QPU time from provider usage records, never wall-clock** — queueing dominated every experiment (39x spread), so wall-clock comparisons are not reproducible even by the same authors a day later.

## Scope & Honest Boundaries

- Evidence is zone-bipartition-only (two real US city networks); the derivation is problem-family-agnostic but cross-family transfer is untested.
- Deliberate negative result: the quantum sub-solver (Kipu Iskay on ibm_rensselaer) contributed nothing over classical — this is a classical selection framework with optional quantum backend, NOT a quantum-advantage demonstration.
- Question reopens only when sub-problems exceed exact classical solvability, which on current hardware means confronting compilation cost (term count), not qubit count.

## Relationship to Other Methods

- qbsolv / impact indexing (Booth et al. 2017): the baseline this replaces; reads only |a_i|.
- Atobe et al. 2022: reads disagreement across a solution pool — empirical, needs population maintenance.
- Zhao & Tang 2025: clusters an empirical correlation matrix — closest in spirit; DkS instead derives closed-form from exact second-order expansion and provides bounds.
- SVM working-set selection (SMO, Fan et al. 2004): same "choose a small subset to re-optimize" problem — this paper imports that lens into quantum decomposition.
- Companion techniques: compressed adiabatic evolution (Azfar et al. 2026) and ramp-scheduled QAOA reduce term count — natural pairings with a selector that keeps sub-problems small.