Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform

• URL: http://arxiv.org/abs/2607.26349v1
• Date: Tue, 28 Jul 2026 23:45:18 GMT
• Title: Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform
• Abstract summary: 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.
• Score: 1.3423094548772225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel slack-free, penalty-based framework for reformulating constrained binary optimization as Quadratic Unconstrained Binary Optimization (QUBO) on near-term quantum annealing hardware. Given a user-chosen penalty function that most naturally captures a constraint---typically non-quadratic, such as a Heaviside-function surrogate---and a target probability measure over the Boolean hypercube, our method returns the weighted least-squares projection of the chosen penalty function onto the subspace spanned by linear and quadratic Walsh--Fourier characters that correspond to physically realizable couplings on the target hardware graph. Within this restricted family, the resulting quadratic surrogate is uniquely and optimally determined by the normal equations: unlike state-of-the-art approaches, it introduces no per-constraint penalty coefficients to tune and avoids dense all-pairs couplings by construction. Two practical consequences follow. First, the projected penalty respects device connectivity, reducing chain lengths and physical-qubit overhead after minor embedding. Second, we show empirically that this hardware-native surrogate can outperform denser full-pairwise projections, despite being drawn from a strictly smaller approximation space. 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.

Related papers

• Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization [1.3827807729367585]
  We show that a class of binary optimization problems with complex non-quadratic objectives or constraints can be reformulated as multi-objective quadratic unconstrained binary optimization problems.<n>We demonstrate the approach for binary portfolio optimization under a Conditional Value-at-Risk constraint.
  arXiv  Detail & Related papers  (2026-09-12T08:07:15Z)
• Universal Optimization and Tighter Fidelity Bounds for Approximate Quantum Error Correction [5.2107604548805915]
  Approximate quantum error correction (AQEC) dictates the performance of discrete- and continuous-variable quantum error correction codes.<n>Finding the optimal recovery channel to maximize entanglement fidelity via standard semidefinite programming is computationally bottlenecked by the exponentially growing number of Kraus operators.<n>We establish an efficient framework by leveraging the duality between recovery and environment decoupling.
  arXiv  Detail & Related papers  (2026-07-27T18:18:58Z)
• Optimality-Preserving Decomposition for Scalable QAOA in Natural-Language-Guided Multi-Drone Assignment [1.189955933770711]
  We present an end-to-end framework integrating a fine-tuned Large Language Model front-end with a highly scalable, domain-specific quantum-classical backend.<n>Our framework features a novel constraint-preserving graph partitioner and a compressed separator-based dynamic programming (DP) merge.<n> Empirical results demonstrate that this architecture circumvents classical scaling walls, recovering the global optimum on 100% of idealized cases and 96.3% under real QAOA sampling.
  arXiv  Detail & Related papers  (2026-06-12T08:31:14Z)
• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  Penalty-based methods have become popular for solving bilevel optimization (BLO) problems.<n>They often require inner-loop iteration to solve the lower-level (LL) problem and small outer-loop step sizes to handle the increased smoothness induced by large penalty terms.<n>This work considers the general BLO problems with coupled constraints (CCs) and leverages a novel penalty reformulation that decouples the upper- and lower-level variables.
  arXiv  Detail & Related papers  (2025-11-20T20:48:14Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• 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)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Experimental demonstration of improved quantum optimization with linear Ising penalties [0.562479170374811]
  We explore an alternative penalty method that only involves linear Ising terms and apply it to a customer data science problem.<n>Our findings support our hypothesis that the linear Ising penalty method should improve the performance of quantum optimization.<n>For problems with many constraints, where making all penalties linear is unlikely to be feasible, we investigate strategies for combining linear Ising penalties with quadratic penalties.
  arXiv  Detail & Related papers  (2024-04-08T12:54:19Z)
• Quantum optimization with linear Ising penalty functions for customer data science [0.5242869847419834]
  In quantum algorithms, constraints are typically implemented with quadratic penalty functions.<n>This penalty method can introduce large energy scales and make interaction graphs much more dense.<n>We consider linear Ising penalty functions as an alternative method for implementing constraints that makes more efficient use of physical resources.
  arXiv  Detail & Related papers  (2024-04-08T12:46:22Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)

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.