arXiv:2610.04908
Custom Penalty QAOA via Walsh-Hadamard Transform
Xin Wei LEE, Siong Thye GOH, Hoong Chuin LAU
Abstract
Inequality constraints in combinatorial optimization are conventionally handled by introducing slack variables and quadratic penalties, which increase the qubit count and distort the optimization landscape. Slack-free formulations instead apply a nonlinear custom penalty function directly to the constraint, which are difficult to be implemented in quantum approximate optimization algorithm (QAOA). We show that the Walsh--Hadamard transform (WHT) removes this obstruction for any penalty function: a penalty applied to a linear constraint is exactly a weighted sum of Pauli-$Z$ strings. We propose this framework as the Walsh custom penalty QAOA (WCP-QAOA). Truncating the expansion at Walsh degree $k$ costs $\mathcal{O}(n^k)$ Pauli terms and leaves the qubit count untouched. The truncation is the optimal degree-$k$ approximation of the penalty in $L^2$, and we give a condition on the discarded Walsh coefficients under which the truncated Hamiltonian still ranks every feasible solution below every infeasible one. Since evaluating a Walsh coefficient from its definition requires all $2^n$ penalty values, we give an algorithm that returns any coefficient in sub-exponential time, so that the degree-$k$ Hamiltonian is obtained in time polynomial in $n$ for fixed $k$. We show that for the exponential penalty, there exists a closed product form of WHT, and hence a closed form expression to calculate the Walsh coefficients. We identify structural shortcuts that shorten the exact spectrum. We also tested WCP-QAOA in solving a 6-qubit knapsack problem.
AI Summary
The paper asks how to implement slack-free nonlinear penalties for linear inequality constraints in QAOA without ancillary arithmetic registers. It develops Walsh custom penalty QAOA: expand $\phi(x)=\xi(a^\top x-b)$ in Walsh characters, which correspond to commuting Pauli-$Z$ strings. The exact phase separator therefore uses no ancillas or Trotter approximation, but generally has exponentially many terms. Keeping Walsh degree at most $k$ retains $\sum_{j=1}^k\binom{n}{j}=O(n^k)$ nonidentity terms. Orthogonal projection establishes that this is the optimal degree-$k$ approximation under uniform-measure $L^2$ error. A sufficient condition for every feasible state to remain below every infeasible state is $\lambda(\delta_\xi-2\varepsilon_k)>\Delta_f$, where $\varepsilon_k$ is the discarded coefficient $\ell_1$ mass. A signed subset-sum convolution computes each coefficient in $O(n\|a\|_1)$ time and $O(\|a\|_1)$ memory: pseudo-polynomial in integer constraint data, rather than unconditionally sub-exponential. Exponential penalties admit closed product-form coefficients; support, permutation symmetry and balanced thresholds provide additional spectral simplifications. Statevector tests use one six-variable knapsack instance, ten random initializations and QAOA depths up to five. Exponential and ReLU penalties retain over 99% of nonconstant spectral power by degree three. For the step-penalty QAOA tests, however, optimum-sampling probability improves appreciably only with the full degree-six spectrum. The paper notes that high retained $L^2$ power does not ensure ground-state preservation, the separation certificate requires generally inaccessible high-degree information, and larger comparative benchmarks are needed. Penalties and truncation can also distort ordering within the feasible set.
Central claim may not hold: The advertised sub-exponential coefficient computation and polynomial-in-n fixed-degree preprocessing are only pseudo-polynomial bounds and can be exponential in n for permitted integer weights. The paper incorrectly infers constrained optimality from feasible–infeasible energy separation, although its allowed penalties can change the ordering of feasible solutions even without truncation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 16 pages, 4 figures. Submission to QIP 27. Subject to major changes