arXiv preprint ·
Custom Penalty QAOA via Walsh-Hadamard Transform
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Sidewall spacer passivated epitaxial NbN/AlN/NbN Josephson junctions for superconducting qubit applications
Transformer-Based Time-Series Inference of Lindblad Dynamics in Open Quantum Systems
Epitaxial NbN-junction-based self-shunted superconducting flux qubit with high anharmonicity
Constraints on the Origin of Universal $1/f^2$ Photon-Count Spectra at Baseband
Entanglement-of-formation potentials for feedback-assisted classical communication and randomness distillation
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.