Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.04908

Custom Penalty QAOA via Walsh-Hadamard Transform

Xin Wei LEE, Siong Thye GOH, Hoong Chuin LAU

quant-phSubmitted Oct 4, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textIncrementalOverclaimsMissing comparisonPossible error

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

Related papers

Penalty-free approach to accelerating constrained quantum optimization

David Bucher, Jonas Stein, Sebastian Feld +1 more

Traditional methods for handling (inequality) constraints in the quantum approximate optimization (QAOA) typically rely on penalty terms and slack variables, which increase problem complexity and expand the search space. More sophisticated mixer-based QAOA variants restrict the search within the feasible assignments but often suffer from prohibitive circuit complexity. This paper presents a penalty-free formalism for incorporating inequality constraints into the cost function of QAOA using an oracle-based subroutine that evaluates constraint satisfaction in an additional register, subsequently called indicator function QAOA (IF-QAOA). Applied to the knapsack problem, we demonstrate in numerical simulations the superior performance of IF-QAOA over conventional penalty-based approaches. Using advanced QAOA simulation techniques, we find that IF-QAOA achieves significantly higher solution quality and a faster time to solution in 82% of our benchmark cases, even though circuit depth is approximately three times larger. Analysis of the scaling behavior shows favorable scaling of IF-QAOA compared to penalty-based methods. Also, benchmarks against the recently developed quantum tree generator QAOA for knapsack problems (P. Christiansen , ) demonstrated higher solution quality for circuits of similar depth. Additionally, this paper introduces a method for approximating the indicator function when the number of ancillary qubits is limited or the constraint function is noninteger. With a specialized simulation algorithm based on projective measurements, we empirically demonstrate that this formalism can encode general inequality constraints using a fixed number of ancillary qubits.

arXiv:2504.08663•Physical Review A•Oct 17, 2025•20 citations

Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers

Xin Lee, Hoong Chuin Lau

Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods. A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These steplike penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and thresholdbased constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.

arXiv:2504.12611•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•2 citations

CVaR-Assisted Custom Penalty Function for Constrained Optimization

Xin Wei Lee, Hoong Chuin Lau

We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables and preserves the feasibility structure of the original problem. The proposed approach introduces a nonlinear custom penalty function to enforce inequality constraints directly in the objective function. To address the computational challenges associated with evaluating nonlinear penalties in variational quantum algorithms, we employ the finite-sampling method that avoids the exponential complexity required by exact expectation computation. Furthermore, we integrate the Conditional Value-at-Risk (CVaR) objective to improve optimization robustness and guide the search toward high-quality solutions. The proposed framework is evaluated on instances of the multi-dimensional knapsack problem, a classical benchmark in combinatorial optimization. We showcase that the proposed custom-penalty formulation combined with CVaR sampling achieves improved optimality gaps and more consistent performance compared with conventional slack-based QUBO formulations. We also tested our method on the Quantinuum H2 quantum hardware, demonstrating the possibilities of training small-sized VQE on noisy trapped-ion quantum computers. The results suggest that careful penalty design can play a critical role in enabling quantum and hybrid quantum-classical algorithms for constrained optimization problems that arise in operations research.

quant-pharXiv:2604.20088•Apr 23, 2026•3 citations

Resource-efficient QUBO formulations for the Knapsack and Bin Packing problem

Pim van den Heuvel

Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.

•Jan 1, 2025•0 citations

Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware

Tristan Zaborniak

Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem whose maximum monomial degree grows with the cardinalities of the underlying CFN variables. Given that quantum optimization hardware generally favours quadratic unconstrained binary optimization or low-degree HUBO Hamiltonians, high-cardinality CFNs therefore incur substantial overhead in the form of circuit depth, or ancilla qubits when degree-reduction techniques are employed. To ameliorate these issues, we propose \textit{truncated-binary encoding} (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff $k_\text{max}$ are dropped from the encoded cost. We establish a tight $L^\infty$ bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting $k_\text{max}$ and for judging whether a given CFN admits a small-$k_\text{max}$ TBE.

quant-pharXiv:2605.17143•May 19, 2026•0 citations

Resource-efficient formulations of the Knapsack problem for quantum computing

Pim van den Heuvel, Vrinda Mehta, Dennis Willsch +2 more

Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.

arXiv:2611.06797•Nov 4, 2026•0 citations
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-ZZZ strings. We propose this framework as the Walsh custom penalty QAOA (WCP-QAOA). Truncating the expansion at Walsh degree kkk costs O(nk)\mathcal{O}(n^k)O(nk) Pauli terms and leaves the qubit count untouched. The truncation is the optimal degree-kkk approximation of the penalty in L2L^2L2, 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 2n2^n2n penalty values, we give an algorithm that returns any coefficient in sub-exponential time, so that the degree-kkk Hamiltonian is obtained in time polynomial in nnn for fixed kkk. 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 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 ϕ(x)=ξ(a⊤x−b)\phi(x)=\xi(a^\top x-b)ϕ(x)=ξ(a⊤x−b) in Walsh characters, which correspond to commuting Pauli-ZZZ strings. The exact phase separator therefore uses no ancillas or Trotter approximation, but generally has exponentially many terms.
Keeping Walsh degree at most kkk retains ∑j=1k(nj)=O(nk)\sum_{j=1}^k\binom{n}{j}=O(n^k)∑j=1k​(jn​)=O(nk) nonidentity terms. Orthogonal projection establishes that this is the optimal degree-kkk approximation under uniform-measure L2L^2L2 error. A sufficient condition for every feasible state to remain below every infeasible state is λ(δξ−2εk)>Δf\lambda(\delta_\xi-2\varepsilon_k)>\Delta_fλ(δξ​−2εk​)>Δf​, where εk\varepsilon_kεk​ is the discarded coefficient ℓ1\ell_1ℓ1​ mass. A signed subset-sum convolution computes each coefficient in O(n∥a∥1)O(n\|a\|_1)O(n∥a∥1​) time and O(∥a∥1)O(\|a\|_1)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 L2L^2L2 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.
Traditional methods for handling (inequality) constraints in the quantum approximate optimization (QAOA) typically rely on penalty terms and slack variables, which increase problem complexity and expand the search space. More sophisticated mixer-based QAOA variants restrict the search within the feasible assignments but often suffer from prohibitive circuit complexity. This paper presents a penalty-free formalism for incorporating inequality constraints into the cost function of QAOA using an oracle-based subroutine that evaluates constraint satisfaction in an additional register, subsequently called indicator function QAOA (IF-QAOA). Applied to the knapsack problem, we demonstrate in numerical simulations the superior performance of IF-QAOA over conventional penalty-based approaches. Using advanced QAOA simulation techniques, we find that IF-QAOA achieves significantly higher solution quality and a faster time to solution in 82% of our benchmark cases, even though circuit depth is approximately three times larger. Analysis of the scaling behavior shows favorable scaling of IF-QAOA compared to penalty-based methods. Also, benchmarks against the recently developed quantum tree generator QAOA for knapsack problems (P. Christiansen , ) demonstrated higher solution quality for circuits of similar depth. Additionally, this paper introduces a method for approximating the indicator function when the number of ancillary qubits is limited or the constraint function is noninteger. With a specialized simulation algorithm based on projective measurements, we empirically demonstrate that this formalism can encode general inequality constraints using a fixed number of ancillary qubits.
Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods. A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These steplike penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and thresholdbased constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.
We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables and preserves the feasibility structure of the original problem. The proposed approach introduces a nonlinear custom penalty function to enforce inequality constraints directly in the objective function. To address the computational challenges associated with evaluating nonlinear penalties in variational quantum algorithms, we employ the finite-sampling method that avoids the exponential complexity required by exact expectation computation. Furthermore, we integrate the Conditional Value-at-Risk (CVaR) objective to improve optimization robustness and guide the search toward high-quality solutions. The proposed framework is evaluated on instances of the multi-dimensional knapsack problem, a classical benchmark in combinatorial optimization. We showcase that the proposed custom-penalty formulation combined with CVaR sampling achieves improved optimality gaps and more consistent performance compared with conventional slack-based QUBO formulations. We also tested our method on the Quantinuum H2 quantum hardware, demonstrating the possibilities of training small-sized VQE on noisy trapped-ion quantum computers. The results suggest that careful penalty design can play a critical role in enabling quantum and hybrid quantum-classical algorithms for constrained optimization problems that arise in operations research.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem whose maximum monomial degree grows with the cardinalities of the underlying CFN variables. Given that quantum optimization hardware generally favours quadratic unconstrained binary optimization or low-degree HUBO Hamiltonians, high-cardinality CFNs therefore incur substantial overhead in the form of circuit depth, or ancilla qubits when degree-reduction techniques are employed. To ameliorate these issues, we propose \textit{truncated-binary encoding} (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff kmaxk_\text{max}kmax​ are dropped from the encoded cost. We establish a tight L∞L^\inftyL∞ bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting kmaxk_\text{max}kmax​ and for judging whether a given CFN admits a small-kmaxk_\text{max}kmax​ TBE.
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.