Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

Zaborniak, Angara, Mulligan, Müller, Stege · arXiv:2604.21123 · submitted 2026-04-24 · score 9/10

Abstract

We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum k-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each k-valued vertex variable using ⌈log₂ k⌉ bits and employs a novel lexicographic penalty system that implicitly minimizes partition count without requiring dedicated indicator variables. We derive provably sufficient conditions on all penalty coefficients, including those arising from Rosenberg quadratization, guaranteeing feasibility and optimality of the lowest-energy solution. Analogous conditions are derived for a one-hot encoding to enable controlled comparison. We also show that our encoding reduces two-qubit gate count per QAOA layer from Θ(|V||k|² + |E||k|) for one-hot to Θ(|E|·|k|⌈log₂|k|⌉). Benchmarking on a quantum annealer demonstrates that our logarithmic encoding significantly improves solution quality and time-to-solution for minimum graph coloring relative to one-hot encoding, with greater advantage as problem size increases.

Executive summary

The paper introduces a HUBO encoding for a broad class of label-symmetric, pairwise-decomposable graph partitioning problems with partition-count minimization (minimum graph coloring, minimum k-cut, community detection) that uses only ⌈log₂ k⌉ bits per vertex instead of the one-hot k. A novel lexicographic penalty implicitly minimizes partition count without indicator variables. Provably sufficient conditions on every penalty coefficient (including Rosenberg quadratization penalties) are derived. Empirically on D-Wave Advantage2_1.11, the log encoding beats one-hot in time-to-solution by 1–2 orders of magnitude at |V|=20, with the gap widening with size. For Yuan this is the closest 2026-04-24 neighbour to Y2 (quasi-binary encoding of discrete-valued variables for QAOA on constrained optimization) and Y4 (structured-feasible-space optimization) — the lexicographic-penalty idea is a potential tool for budget/cardinality-constrained variants of Y4.

Main contribution

For a graph G=(V, E) with vertex labels in [k], the paper encodes each vertex as ⌈log₂ k⌉ binary variables and represents the indicator 1[ℓ_u=ℓ_v] as ∏_j(x_u,j ⊙ x_v,j) (XNOR product), yielding a HUBO of degree up to 2⌈log₂ k⌉. To minimize partition count without an explicit count register, the authors add a linear lexicographic term Σ_k P_k Σ_v x_v,k with geometrically increasing P_k that penalizes use of higher-index bits. The QAOA CNOT count per layer drops from Θ(k²|V| + k|E|) to Θ(k·logk·|E|) — near-exponential for sparse graphs. Practical penalty formulas P_k=(|V|+1)^k−1, A_adjacency=|V|·ΣP_k+1, and Rosenberg M = 2((|V|+1)^L−1)+1+ϵ are all given in closed form.

Key theorems / lemmas / algorithms

Theorem 3.1 (sufficient one-hot QUBO penalties): A_link>1, A_adjacency>A_link·C_num, A_one-hot>A_adjacency·|E|+A_link·C_num suffice for indicator faithfulness, proper coloring, one-hot constraint, and color-count minimality.
Theorem 3.2 (sufficient log HUBO penalties): With P_k+1>|V|·Σ_j≤k P_j and A>|V|·Σ_k P_k, any lowest-energy solution satisfies lexicographic ordering and feasibility (H_adjacency=0).
Corollary 3.3 (practical log penalties): P_k=(|V|+1)^k−1, A=|V|·ΣP_k+1.
Theorem 3.4 (Rosenberg quadratization penalties): M⁽¹⁾, M⁽²⁾ > A + |V|·ΣP_j suffice for the HUBO→QUBO reduction to preserve Theorem 3.2's guarantees.
Theorem 3.5 (CNOT count, one-hot): N_CNOT^(one-hot) = C_num·(|V|(C_num+1)+2|E|).
Theorem 3.6 (CNOT count, log): N_CNOT^(log) = |E|·(2(L−1)·2^L+2) via phase-gadget expansion of the XNOR product.
Theorem 4.1 (general GP penalty): A_partition>|V|·ΣP_k/Δ_min guarantees feasibility for arbitrary pairwise-decomposable graph partitioning problems with hard constraints, where Δ_min is the feasibility gap (min infeasible energy − min feasible energy).

Detailed walkthrough

Setup (§III.A–B). The benchmark problem is Minimum Graph Coloring (MGC): minimize |C| such that adjacent vertices receive different colors. The baseline one-hot QUBO uses C_num = C_num^u (an efficient upper bound via Brooks' theorem) and introduces a secondary register y of indicator bits y_c ∈ {0,1} for "color c is used", giving a Hamiltonian H_one-hot + H_adjacency + H_count + H_link requiring (|V|+1)·C_num qubits and three independent penalties.

Logarithmic HUBO (§III.C). Encode each vertex with L = ⌈log₂ C_num⌉ bits. Since x_u,k⊙x_v,k = 2x_u,kx_v,k−x_u,k−x_v,k+1, the adjacency Hamiltonian H_adjacency=A Σ_(u,v)∈E ∏_k(x_u,k⊙x_v,k) is exactly 0 on valid colorings (different bitstrings on adjacent vertices) and ≥1 otherwise. The innovation is the lexicographic term H_{lexicographic} = Σ_k P_k Σ_v x_v,k, with P_k+1>|V|·Σ_j≤kP_j. This geometric blowup ensures that reducing one "high-significance" bit (s_t) always beats any accompanying increases in lower-significance bits, which proves lexicographic minimization (Theorem 3.2(i)). Feasibility (Theorem 3.2(ii)) follows from A>|V|·ΣP_k: any infeasible solution costs at least A, which dominates any lexicographic saving. Concretely the authors recommend P_k=(|V|+1)^k−1.

Rosenberg quadratization (§III.D). For platforms that need 2-local Hamiltonians (quantum annealers), the degree-2L adjacency product is reduced in two stages: stage 1 introduces y_u,v,k=x_u,k⊙x_v,k with penalty M⁽¹⁾, yielding |E|·L auxiliary bits; stage 2 recursively reduces the remaining product with L−2 Rosenberg auxiliaries per edge. Total auxiliary count is |E|·(2L−2). The logarithmic encoding beats one-hot in logical-qubit count when |E| < ½·((|V|+1)·C_num−L)/(L−1), i.e., on sparser graphs. The sufficient Rosenberg penalties M⁽ⁱ⁾>A+|V|·ΣP_j preserve Theorem 3.2.

Gate-count comparison (§III.E). For QAOA phase-separation, the one-hot encoding gives Θ(C_num²|V|+C_num|E|) CNOTs per layer. The log encoding, via the identity x_u,k⊙x_v,k=(1+Z_u,kZ_v,k)/2, expands each edge factor into Σ_S⊆[L] ∏_k∈S Z_u,kZ_v,k — which requires Σ_s(L choose s)·2(2s−1)=2(L−1)·2^L+2 CNOTs per edge, total Θ(C_num·log C_num·|E|). For sparse graphs the ratio scales as Θ(C_num/log C_num), a near-exponential reduction. For |V|≥Ω(log C_num) the log encoding always asymptotically dominates.

General graph partitioning (§IV). The scheme extends to any problem of the form Σ_(u,v) [α_u,v·1[ℓ_u=ℓ_v]+β_u,v·1[ℓ_u≠ℓ_v]]+λ·|{ℓ_v}|. The partition penalty A_partition must exceed |V|·ΣP_k/Δ_min, where Δ_min is the feasibility gap between the best infeasible and best feasible partition costs. For MGC Δ_min=1 and the formula collapses to Corollary 3.3.

Benchmarking (§V–VI). 350 random graphs with edge density in [0.2, 0.8] and |V|∈[4, 100] were run on the D-Wave Advantage2_1.11 QPU (≈4400 flux qubits, Zephyr topology), with 1000 anneals per instance, T_S=20 μs. Kaplan-Meier survival analysis handles instances where p_S=0. Headline results (Fig. 2): (i) log-encoding TTS is 1–2 orders of magnitude lower than one-hot already at |V|=20; (ii) pre-quadratization logical qubits lie well below the y=x line (verifying exponential compression); post-quadratization, dense graphs can exceed one-hot, consistent with the sparsity-threshold formula; (iii) physical qubit counts post-embedding are comparable across encodings — so the TTS advantage is not a qubit-savings artifact; (iv) chain-length variance is markedly lower for the log encoding, which the authors credit as the decisive driver (non-uniform chains distort the effective problem Hamiltonian; a single global chain strength can't simultaneously serve long and short chains).

Figures

Figure 1. Small example graph colored improperly (upper row, violating edge colored red) and properly (bottom row). The tables contain bitstring assignments to each vertex under the one-hot and logarithmic encodings. With 4 vertices, one-hot uses 4 qubits per vertex and the logarithmic encoding uses 2.

Figure 2. Benchmarking on D-Wave Advantage2_1.11. Upper left: TTS as a function of |V|. Upper right: post-quadratization logical qubits per encoding (inset: pre-quadratization). Lower left: physical qubits after minor embedding. Lower right: chain-length variance (inset: average chain length).

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y2 (quasi-binary encoding, arXiv:2304.06915) — strong method overlap. Y2 encodes each integer variable in ~2⌈log₂(U−L+1)⌉ qubits and preserves hard constraints via a tailored mixer (no penalties). This paper encodes each k-valued label in ⌈log₂ k⌉ bits and handles constraints via lexicographic penalty instead. The difference in philosophy (penalty vs hard-mixer) is worth highlighting — Yuan could potentially adapt their hard-mixer construction to Zaborniak et al.'s lexicographic setting to avoid penalty-induced landscape distortion.
Y4 (Grover + ADMM for cardinality-constrained BO, arXiv:2603.14744) — scope/method overlap. Y4 concerns optimization over structured feasible spaces (cardinality constraint); this paper concerns optimization over symmetric-label spaces with partition-count minimization — both are "constrained combinatorial optimization with objective on a complexity-summary of the assignment". The lexicographic penalty idea may generalize to cardinality constraints (priority of "0" bits over "1" bits).
Y3 (QAOA DGMVP portfolio, arXiv:2410.16265) — indirect method overlap. Y3 gives empirical QAOA benchmarks with careful parameter-optimization; the gate-count reduction here (Theorem 3.6) is directly relevant to Yuan's next-iteration QAOA-on-hardware work, particularly if the portfolio DGMVP is reformulated with k-valued holdings rather than binary.
Y1 (warm-start QAOA) — weak. No direct method overlap; warm-starting is orthogonal to encoding choice but would compose cleanly on top.

Recommended action for Yuan

Read deeper and cite. This is a natural citation target for Y2 follow-ups and for any new QAOA-encoding work. Section III.B's literature review of qubit-efficient encodings (domain-wall, logarithmic, polynomial, Sciorilli-style Pauli-compression) is a ready-made related-work scaffold.
Adapt the lexicographic penalty. For Y4's cardinality-constrained setting, a lexicographic penalty ordering 1-bits by priority could provide an alternative to the Grover+ADMM hybrid when cardinality bounds are soft. Worth a concrete comparison paper.
Contrast with Y2's hard-mixer. A head-to-head experiment: quasi-binary + hard mixer (Y2) vs log-encoding + lexicographic penalty (this paper), on the same discrete portfolio instance, would clarify when penalty-free encodings outperform and when penalty-based ones do.