Custom Penalty QAOA via Walsh-Hadamard Transform
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 𝒪(nk) Pauli terms and leaves the qubit count untouched. The truncation is the optimal degree-k approximation of the penalty in L2, 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 2n 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.
Related
- Walsh-Transform Realization of Dense-to-Sparse Quantum State Preparation
- From Analytic Structure to Quantum Complexity: Walsh-Pauli Representations of Continuum Operators
- Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation
- Refuting the QAOA fixed-angle conjecture
- Development of an FPGA-Based Readout System and Functional Characterization of a Custom NSX1 ASIC for X-ray instrumentation
BibTeX
@misc{wei2026custom,
title = {{Custom Penalty QAOA via Walsh-Hadamard Transform}},
author = {Xin Wei LEE and Siong Thye GOH and Hoong Chuin LAU},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04908},
eprint = {2610.04908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04908},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Custom Penalty QAOA via Walsh-Hadamard Transform
AU - Xin Wei LEE
AU - Siong Thye GOH
AU - Hoong Chuin LAU
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04908
UR - https://arxiv.org/abs/2610.04908
AB - 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 𝒪(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.
ER -