Custom Penalty QAOA via Walsh-Hadamard Transform

AI summary

Overview

Research area: Quantum computing for combinatorial optimization — specifically constrained optimization with the Quantum Approximate Optimization Algorithm (QAOA), quantum Hamiltonian encoding, and Walsh–Hadamard spectral methods.

Technical level: Advanced. The paper is written for readers comfortable with QAOA/VQE formalism, Pauli-Z operator expansions, and Fourier/Walsh analysis; the proofs rely on Parseval's identity, discrete convolution, and circuit-synthesis arguments.

Scope: The paper introduces WCP-QAOA, a framework that turns a nonlinear, slack-free penalty on a linear inequality constraint into an exact sum of commuting Pauli-Z strings via the Walsh–Hadamard transform, and analyzes truncation, coefficient computation, and circuit cost — with a 6-qubit knapsack test mentioned but whose numerical results are not present in the supplied text.

What This Paper Is About

Inequality constraints in quantum optimization are usually handled by adding slack variables and quadratic penalties, which consumes extra qubits and distorts the optimization landscape. "Slack-free" custom penalty functions avoid both problems but are nonlinear, and a nonlinear function cannot be placed inside the QAOA phase separator, which requires the cost Hamiltonian in an exponent. The paper shows that the Walsh–Hadamard transform expresses any penalty on a linear constraint exactly as a weighted sum of Pauli-Z strings, so the phase separator can be implemented exactly without ancillas or Trotter error — the open questions then become how many terms are needed and how to compute them efficiently.

Key Contributions

1. Exact spectral form of the custom penalty phase separator. The penalty Hamiltonian is exactly a sum of commuting Pauli-Z strings, so the phase separator factorizes into CNOT ladders and Z rotations with no ancilla and no Trotter error. Truncating at Walsh degree k costs O(n^k) Pauli terms while the qubit count stays fixed at n.

2. A sub-exponential algorithm for individual Walsh coefficients. Any single coefficient of a penalty ξ(aᵀx − b) is computed exactly in O(n‖a‖₁) time and O(‖a‖₁) memory, without enumerating the 2ⁿ bit-strings and without sampling — using a convolution of n small vectors ("signed frequencies"). For fixed k, the whole degree-k Hamiltonian follows in polynomial time; the total classical preprocessing is O(n^{k+1}‖a‖₁).

3. A proof that Walsh truncation is L²-optimal, plus a feasibility-separation condition. The truncated Walsh series is the orthogonal projection of the penalty onto degree-k polynomials, hence the best degree-k L² approximation under the uniform measure — never worse than any polynomial surrogate of the same degree, established by showing least-squares fitting of the Walsh series returns the Walsh coefficients. Proposition 2 gives a sufficient condition (λ(δ_ξ − 2ε_k) > Δ_f) under which the truncated Hamiltonian still ranks every feasible solution below every infeasible one.

4. Structural shortcuts and closed forms. For the exponential penalty there is a closed product form of the Walsh–Hadamard transform, so coefficients follow directly from the constraint coefficients without summing the full transform. A constraint acting on r of the n variables has at most 2^r nonzero coefficients; a cardinality-type constraint has only n + 1 distinct coefficient values; a step-like penalty at a balanced threshold has no even-degree coefficients at all.

Main Findings

• The obstruction is removable in principle. Since all Pauli-Z strings commute, the phase separator for the full Walsh Hamiltonian factorizes exactly in any ordering, so the only error from truncation is the classical function-approximation error φ − T_kφ, not a quantum circuit error.

• Circuit cost, exact case. A term indexed by subset S costs 2(|S| − 1) CNOTs and one single-qubit rotation on the pivot qubit max(S). Concatenating all 2ⁿ − 1 non-identity terms naively needs n2ⁿ − 2^{n+1} + 2 CNOTs; the Gray-code (sequency) ordering reduces this to 2ⁿ − 2. At n = 12 this is a reduction from 40962 to 4094 CNOTs — still exponential, which motivates truncation.

• Circuit cost, truncated case. No closed-form optimal CNOT count exists for a truncated Walsh series; synthesizing a CNOT-minimal parity network is NP-complete even when all CNOTs share a common target. The paper instead gives the bound Σ_{i=2}^{k} C(n,i) ≤ N_CNOT ≤ Σ_{i=2}^{k} 2(i−1)C(n,i), noting the GraySynth heuristic attains C(n,2) + n − 1 CNOTs including uncomputation.

• Error is controlled by discarded spectral weight. The uniform error is bounded by the ℓ₁ tail ε_k = Σ_{|S|>k} |φ̂(S)|, and the squared L² error equals Σ_{|S|>k} φ̂(S)² by Parseval. The retained-power ratio Π_k is proposed as a figure of merit for comparing penalty profiles at fixed term budget — and it is a property of the (penalty, constraint) pair, not of the penalty alone.

• The step penalty has a clean threshold. For the step penalty δ_Θ = 1 for every constraint, so Proposition 2 requires only that the discarded weight be below one half and that λ exceed Δ_f/(1 − 2ε_k).

• The retained power is exactly computable; the ℓ₁ tail is not. By Parseval, Σ_S φ̂(S)² equals the expectation of φ², computable from ω_∅ alone at the same cost as one coefficient — so Π_k and the L² truncation error need no high-degree coefficients. The ℓ₁ tail ε_k admits no such identity, only a Cauchy–Schwarz bound.

• The separation criterion is conservative. The paper states explicitly that Proposition 2 is sufficient and pessimistic because it requires every feasible string to beat every infeasible one; under CVaR training only the low-energy tail matters, so a tail-based criterion is argued to be the operationally relevant one and is expected to be satisfied at considerably smaller k.

• Empirical scope. The abstract reports testing WCP-QAOA on a 6-qubit knapsack problem; the specific results of that experiment are not reported in the supplied content.

Methodology in Plain English

The authors start from a simple observation about bookkeeping. Any function of n bits can be written as a unique weighted sum of "parity" functions — products of ±1 signs, one per bit in a chosen subset — and this is exactly what the Walsh–Hadamard transform computes. Crucially, each parity function becomes a Pauli-Z string once bits are mapped to qubits, so a non-polynomial penalty has an exact operator representation as a sum of Z strings.

Because Z strings all commute, the QAOA phase separator — which normally requires exponentiating the cost Hamiltonian — splits into a product of simple, independent pieces, each implementable with a short chain of CNOTs and one rotation. That gets rid of ancillas, comparators, and Trotter error.

The problem then becomes size: the full expansion has 2ⁿ terms. The authors' response is threefold. First, keep only terms up to degree k, which they prove is the best possible degree-k approximation in L² (so no polynomial fitting scheme can beat it at the same degree). Second, prove a condition guaranteeing the truncated penalty still puts every feasible solution below every infeasible one. Third, make the coefficients cheap to obtain: rather than summing over all 2ⁿ bit-strings, they group bit-strings by the value of the constraint (a small integer between 0 and ‖a‖₁) and build a "signed frequency" vector by convolving n tiny vectors — giving exact coefficients in time linear in n times ‖a‖₁.

They also catalog structural shortcuts that shrink the spectrum before truncation (few variables in the constraint, cardinality structure, symmetries of step penalties), and supply a closed product form for the exponential penalty so its coefficients need no transform at all. The 6-qubit knapsack instance is the paper's numerical testbed.

Why This Matters

Impact on research. The paper removes a genuine structural obstacle: it shows that the reason custom penalties were confined to VQE — the cost Hamiltonian appearing in an exponent — is an artifact of not expanding in the right basis. It connects the slack-free penalty literature to the Walsh/Pauli-Z correspondence and gives the truncation a variational-approximation guarantee, so QAOA's structural advantages (adiabatic inheritance, parameter-initialization heuristics, periodicity and symmetry of the landscape, compatibility with XY and Grover mixers) become available to constrained problems without reintroducing slack qubits.

Real-world applications.

• Knapsack and multidimensional knapsack problems (capacity constraints of the exact linear form aᵀx ≤ b treated here), which underlie logistics, portfolio selection, and resource allocation.
• Scheduling and allocation problems where inequality constraints on totals (budgets, capacities, headcounts) are ubiquitous and where qubit counts are the binding resource.
• Problems where a hard threshold is more natural than a quadratic penalty — for example accepting or rejecting a plan that exceeds a budget, encoded by the Heaviside step penalty.
• Settings where penalties are ranked or exponentially weighted rather than quadratic, which the exponential-penalty closed form addresses directly.

Industry relevance. The framework is aimed at near-term hardware: it fixes the qubit count at n, avoids ancillas, avoids Trotter error, and treats CNOT count as the cost metric on the grounds that R_z gates are often virtual. The degree k becomes a tunable dial trading circuit size against penalty fidelity, which is the kind of knob practitioners deploying QAOA on limited devices need. The empirical demonstration, however, is a 6-qubit instance, so the practical reach on real hardware is not established in this paper.

Future Directions

• Replacing the pessimistic separation condition with a tail-based one. The paper notes that ε_k is an ℓ₁ tail that cannot generally be evaluated without the high-degree coefficients it sums, and that Proposition 2 demands far more than variational sampling or CVaR training actually needs. Developing a criterion about whether the best feasible solution remains among the lowest-energy states of the truncated Hamiltonian is the stated operational target.

• Better truncated-state circuit synthesis. No closed-form optimal CNOT count exists for a truncated Walsh series, Gray-code ordering need not be efficient for sparse sets, and CNOT-minimal parity-network synthesis is NP-complete even with a common target. Closing the gap between the proven bounds and what heuristic synthesis achieves is open.

• Extending closed forms to more penalties. A closed product form of the Walsh transform is shown for the exponential penalty. Whether other useful penalty profiles — the step function being the obvious next case — admit comparable closed forms or tighter shortcut-driven spectra is left open.

• Scaling the empirical evaluation. The reported test is a 6-qubit knapsack instance; how the retained-power ratio Π_k behaves for larger n and for multiple simultaneous constraints, and how WCP-QAOA compares against slack-based QAOA at matched qubit and gate budgets, are natural next experiments.

Target Audience

Quantum algorithm researchers and graduate students working on constrained optimization with variational quantum algorithms — particularly those already familiar with QAOA, QUBO/Ising encodings, and slack-variable reformulations. The paper is also relevant to quantum circuit-synthesis researchers interested in parity-network and CNOT-count questions, and to practitioners who need slack-free constraint handling on qubit-limited hardware and are comfortable deciding a truncation degree themselves. Readers seeking experimental benchmark tables will find the empirical portion of the supplied text thin: only the existence of a 6-qubit knapsack test is reported.

Authors’ 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.