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

Constrained binary optimization problems, such as those found in logistics and power systems, are typically solved on quantum annealers by converting constraints into Quadratic Unconstrained Binary Optimization (QUBO) models. Standard approaches often use slack variables to transform inequalities into equalities, which introduces auxiliary qubits, increases the density of the interaction graph, and requires complex tuning of penalty coefficients. This paper addresses the challenge of creating slack-free, hardware-aware quadratic surrogates that respect the sparse connectivity of near-term quantum hardware.

The authors propose a framework that treats the construction of a penalty function as an orthogonal projection problem in a weighted L2 space. By using the Walsh–Fourier transform, they express a chosen penalty function (such as a Heaviside-function surrogate) in terms of Walsh characters. They then project this function onto a subspace defined by the constant, linear, and hardware-admissible quadratic terms. This projection is solved via the normal equations, resulting in a unique, optimal quadratic surrogate that is natively compatible with the target device's coupler graph.

The TAWP framework offers two primary advantages. First, it decouples the modeling of the constraint from the hardware topology; the user defines the penalty, and the framework automatically produces the best approximation consistent with the available physical couplings. Second, empirical evaluation on quantum annealers using multidimensional knapsack benchmarks demonstrates that this approach yields samples with lower objective gaps compared to traditional unbalanced penalization and hardware-blind projections. By avoiding minor embedding overheads like long ferromagnetic chains, the method improves both the feasibility and the quality of the solutions obtained from quantum hardware.