Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware

• URL: http://arxiv.org/abs/2605.17143v1
• Date: Sat, 16 May 2026 20:27:06 GMT
• Title: Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware
• Abstract summary: Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem.<n>We propose textittruncated-binary encoding (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff $k_textmax$ are dropped from the encoded cost.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• The Gain-Engineered Transmon [68.89136228609398]
  We introduce and experimentally realize a noise-biased qubit in a standard transmon-readout resonator circuit.<n>Our results open a path towards using this system as a simple building-block for hardware-efficient quantum error detection and correction schemes.
  arXiv  Detail & Related papers  (2026-08-26T17:00:42Z)
• Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform [1.3423094548772225]
  We present a novel framework for reformulating constrained binary optimization as Quadratic Unconstrained Binary Optimization (QUBO)<n>We show that this hardware-native surrogate can outperform denser full-pairwise projections, despite being drawn from a strictly smaller approximation space.<n>This advantage widens once the QUBO is embedded and sampled on quantum annealers, yielding samples with the lowest worst-case and mean objective gaps compared to unbalanced penalization and a hardware-blind projection onto all quadratic terms.
  arXiv  Detail & Related papers  (2026-07-28T23:45:18Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints [0.35331503620315147]
  We propose a method to construct a significantly sparser logical QUBO model for equality and inequality constraints.<n>By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints.<n> Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding.
  arXiv  Detail & Related papers  (2026-01-26T03:40:06Z)
• Charge-Informed Quantum Error Correction [0.0]
  We investigate the statistical physics of quantum error correction in $rm U(1)$-enriched topological quantum memories.<n>The error threshold of the optimal decoder corresponds to a continuous phase transition in a disordered two-dimensional integer loop model on the Nishimori line.<n>We show that the optimal decoding transition exhibits Berezinskii-Kosterlitz-Thouless with a modified universal jump in winding number variance.
  arXiv  Detail & Related papers  (2025-12-26T18:59:21Z)
• Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes [0.9453554184019106]
  Quantum error correction (QEC) is essential for scalable quantum computing.<n>We propose textbfQuBA, a Bayesian graph neural decoder that integrates attention to both dot-product and multi-head.<n>We further develop textbfSAGU textbf(Sequential Aggregate Generalization under Uncertainty), a multi-code training framework with enhanced cross-domain robustness.
  arXiv  Detail & Related papers  (2025-10-05T01:08:39Z)
• MPQ-DMv2: Flexible Residual Mixed Precision Quantization for Low-Bit Diffusion Models with Temporal Distillation [74.34220141721231]
  We present MPQ-DMv2, an improved textbfMixed textbfPrecision textbfQuantization framework for extremely low-bit textbfDiffusion textbfModels.
  arXiv  Detail & Related papers  (2025-07-06T08:16:50Z)
• Approximate quantum error correcting codes from conformal field theory [0.0]
  We consider generic 1+1D CFT codes under extensive local dephasing channels. We show that a CFT code with continuous symmetry saturates a bound on the recovery fidelity for covariant codes.
  arXiv  Detail & Related papers  (2024-06-13T19:40:36Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Erasure qubits: Overcoming the $T_1$ limit in superconducting circuits [105.54048699217668]
  amplitude damping time, $T_phi$, has long stood as the major factor limiting quantum fidelity in superconducting circuits. We propose a scheme for overcoming the conventional $T_phi$ limit on fidelity by designing qubits in a way that amplitude damping errors can be detected and converted into erasure errors.
  arXiv  Detail & Related papers  (2022-08-10T17:39:21Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.