Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware
Abstract
Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem whose maximum monomial degree grows with the cardinalities of the underlying CFN variables. Given that quantum optimization hardware generally favours quadratic unconstrained binary optimization or low-degree HUBO Hamiltonians, high-cardinality CFNs therefore incur substantial overhead in the form of circuit depth, or ancilla qubits when degree-reduction techniques are employed. To ameliorate these issues, we propose \textit{truncated-binary encoding} (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff $k_\text{max}$ are dropped from the encoded cost. We establish a tight $L^\infty$ bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting $k_\text{max}$ and for judging whether a given CFN admits a small-$k_\text{max}$ TBE.
Executive summary
This paper introduces truncated-binary encoding (TBE): a third compilation axis for mapping discrete cost-function networks onto quantum hardware. The standard alternatives — one-hot, domain-wall, exact-binary — all aim for exact representation and trade only along the qubit-count vs. graph-density axis. TBE keeps the logarithmic qubit count of exact-binary but drops all Walsh-Hadamard monomials of degree above a chosen cutoff k_max, yielding a HUBO of bounded degree (k_max = 2 recovers a pure QUBO with no quadratization). The technical contribution is a tight L∞ error bound on the omitted couplings plus sufficient conditions on the energy gap and basin-barrier under which the truncation preserves the global minimum and its bit-flip basin. This overlaps directly with the encoding-choice analysis at the heart of Yuan's Y2 (quasi-binary encoding) but follows an orthogonal axis (approximation quality vs. constraint preservation).
Main contribution
The key conceptual move is to work natively in the Ising ±1 basis throughout, where exact-binary HUBO-degree truncation is identically Walsh-Hadamard projection onto the low-degree subspace. This equivalence fails in the {0,1} basis (Theorem 2.1: spectral leakage), forcing the entire framework into the Ising basis. From there, the L∞ truncation error is bounded tightly by the sum of magnitudes of the omitted couplings (Theorem 3.1), and basin / global-minimum preservation conditions follow directly. A Gaussian-field "noise-floor" condition (Theorem 5.3) governs whether the truncation acts perturbatively under random ensembles, and an additive cost-table decomposition (Theorem 6.1) gives a structural a priori criterion for whether a given CFN admits a small-k_max TBE.
Key theorems / lemmas / algorithms
- Theorem 2.1 (Spectral leakage in the {0,1} basis): Truncation by degree in the {0,1} HUBO basis distributes mass across all lower Walsh degrees; only in the Ising basis does HUBO-degree truncation coincide with Walsh-degree truncation. This forces all subsequent analysis into the Ising basis.
- Theorem 3.1 (L∞ truncation error bound): Truncation error is tightly bounded by the sum of magnitudes of the omitted couplings. The bound is computable in time linear in the number of HUBO monomials.
- Theorem 4.1 (Global minimum preservation): When the original CFN energy gap exceeds twice the L∞ truncation bound, the global minimum of the truncated encoding coincides with that of the full encoding.
- Theorem 4.3 (Local minimum / basin preservation): Analogous statement holds for the local-minimum status of z* under single bit-flip moves, governed by the basin-barrier slack δ_f(z*) − 2ε(k_max).
- Theorem 5.3 (Strong noise floor condition): Under a Gaussian random-coupling ensemble, the truncation residual acts as a perturbative correction to the underlying landscape when the spectral profile {P_k} is concentrated at low k.
- Theorem 6.1 (Cost-table form of encoded couplings): The encoded Walsh coefficients decompose additively over the cost tables of the underlying CFN, giving an a priori, table-by-table criterion.
- Lemma 6.2 (Smoothness ⇒ spectral decay): A bound under which k-th-order smoothness of each cost table implies rapid decay of its high-degree Walsh mass.
- Algorithm 7.1 (TBE Compilation): Input CFN + cutoff k_max → output certified-error Ising HUBO of degree ≤ k_max + optional bit-flip refinement using z** as a warm start.
Detailed walkthrough
The paper sits at the same compilation layer as Yuan's Y2 (quasi-binary encoding) but follows the approximation quality axis rather than the hard-constraint preservation axis. Both attack the same pain point — exact-binary encoding produces a HUBO whose degree grows logarithmically with variable cardinalities, and current quantum hardware (annealers, gate-based QAOA) is fundamentally a 2-local or low-k device. Quasi-binary encoding (Y2) sidesteps the degree blow-up by structuring the encoding so that hard constraints can be enforced through a constraint-preserving mixer with no penalty terms. TBE, by contrast, accepts the exact-binary HUBO and simply drops all Walsh monomials of degree > k_max, accepting a quantified approximation error in exchange.
The technical heart of the paper is the move from the {0,1} basis to the Ising basis. In the {0,1} basis (the standard presentation of exact-binary encoding), HUBO-degree truncation is not the same as Walsh-degree truncation: a degree-k {0,1}-monomial contributes mass at all Walsh degrees 0, 1, …, k. The author proves this explicitly (Theorem 2.1) and uses it to motivate doing all of the encoding directly in the Ising ±1 basis, where the monomial ∏_{i∈S} z_i is identically the Walsh-Hadamard character χ_S. Once in the Ising basis, HUBO-degree truncation is orthogonal projection onto the low-Walsh-degree subspace, and the spectral profile P_k = Σ_{|S|=k} c_S² is a direct readout of the encoded coupling magnitudes.
The L∞ error bound (Theorem 3.1, Section 3.2) is tight and computable: ε(k_max) = Σ_{|S| > k_max} |c_S|. From this, two preservation theorems follow almost immediately. Global-minimum preservation (Theorem 4.1) requires the energy gap of the original landscape to exceed 2ε(k_max); local-minimum / basin preservation (Theorem 4.3) requires the single-bit-flip basin barrier δ_f(z*) to exceed 2ε(k_max). The same slack δ_f(z*) − 2ε(k_max) controls how close the truncated optimum z** sits to the nearest local minimum of the full landscape under bit-flip descent — i.e., z** serves as a warm start for classical refinement.
Section 5 is the more interesting theoretical contribution: a Gaussian-field argument that characterizes when ε(k_max) is small enough to satisfy the noise-floor condition under random Ising couplings. The pointwise CLT (Theorem 5.1) shows the residual converges to a Gaussian field whose variance equals Σ_{|S| > k_max} c_S². The author notes that this can be made rigorous via hypercontractivity. Together with a single bit-flip variance lemma (Lemma 5.2), this yields a strong noise-floor condition (Theorem 5.3): if the spectral profile is concentrated at low k, the truncation acts perturbatively and basin preservation holds heuristically.
Section 6 carries the analysis back to the CFN level. The encoded Walsh coefficients decompose additively over the cost tables of the underlying CFN (Theorem 6.1). The author then introduces discrete calculus on the hypercube (Lipschitz constants, Parseval's identity) and proves that k-th order smoothness of each cost table implies rapid decay of its high-degree Walsh mass (Lemma 6.4). This gives a practitioner a structural a priori criterion: smooth physical-style cost tables (distances, capacities, similarity scores) should admit small-k_max TBE, while truth-table-style or random cost tables will not.
The compilation pipeline (Algorithm 7.1) is straightforward: build the exact Ising HUBO, compute the spectral profile {P_k}, verify the noise-floor condition, set ε ← Σ_{|S| > k_max} |c_S|, truncate, sample on hardware, optionally bit-flip refine. Critically, the algorithm certifies the error ε up-front, so the user knows whether the global optimum is preserved before running the quantum solver. The author notes that k_max = 2 recovers a pure QUBO with no quadratization, while k_max ∈ {3, 4} matches LHZ-style native locality.
The paper does not present hardware benchmarks — it is a purely structural / theoretical contribution. This is both a strength (the analysis is general, not tied to D-Wave or any specific device) and a limitation (the practical regime of effectiveness still needs to be mapped out empirically).
Figures
No figures extracted from source (paper has no figure environments — purely mathematical exposition).
Citations to Yuan's papers
Overlap with Y1–Y6
- Y2 (quasi-binary encoding for constrained QAOA portfolio): Both papers attack the qubit / degree trade-off in encoding discrete CFN variables for quantum hardware. Y2 uses a ~2 log₂(U−L+1) encoding with a hard-constraint mixer to preserve cardinality with no penalty. TBE uses exact-binary log₂ encoding and drops high-degree monomials. The two are complementary along orthogonal axes: Y2 trades qubit-count vs. constraint-preservation; TBE trades qubit-count vs. approximation quality. A natural follow-up is to ask whether quasi-binary encoding admits its own Walsh-spectral truncation analysis.
- Y1 (iterative warm-started QAOA) and Y3 (QAOA DGMVP portfolio): TBE's Algorithm 7.1 explicitly proposes z** as a warm start for single-bit-flip descent on the full landscape. This is structurally identical to Y1's iterative measurement-based warm-starting for QAOA, except that here the "iteration" is between a truncated quantum solver and classical bit-flip refinement rather than between QAOA layers. The basin-barrier slack analysis (δ_f(z*) − 2ε(k_max)) is the analogue of Y1's DGMVP scaling argument for how aggressively one can warm-start.
- Y3 (DGMVP portfolio QAOA): Y3 establishes that DGMVP under QAOA shows favourable scaling only in the shot-noise regime, with thermal relaxation precluding advantage. TBE's noise-floor analysis is directly relevant: a successful truncation needs the spectral mass at low k to dominate the "noise floor" of the high-k residual, which is precisely the same signal-vs-noise framing that determines whether QAOA optimization beats thermal relaxation.
- Y4 (Grover + ADMM for cardinality-constrained BO): Less direct overlap, but TBE's principled error-bound + warm-start design philosophy mirrors Y4's ε-approximation guarantees for ADMM.
Recommended action for Yuan
- Adapt method: Run Walsh-spectral analysis on the quasi-binary encoding of Y2 to characterize when high-degree mass is concentrated. If the spectrum is naturally front-loaded for the quasi-binary monomials encountered in portfolio CFNs, a Y2+TBE hybrid encoding could combine hard-constraint preservation with a guaranteed-degree-reduction. Worth a short experiment.
- Cite in next paper: The paper is a natural reference for any future Yuan paper involving encoding choice for QAOA on cardinality-constrained portfolios — and the L∞ bound + basin-preservation framework is a clean tool to use when reporting approximation-quality claims.
- Discuss with collaborators: Author Tristan Zaborniak (Flatiron / U Victoria) is concretely working in the same compilation-layer territory; an email exchange could be productive if Yuan is thinking of extending Y2 / Y3 toward higher-degree CFN encodings.