QAOA for Constrained Selection Problems

Casting selection under a budget constraint as a QUBO and solving it with the Quantum Approximate Optimization Algorithm.

Selection as a QUBO

Many decision problems choose a subset of items to maximize a benefit measure while respecting a size or resource constraint. Represent each item by a binary variable x_i in {0,1}. A generic objective combines a benefit term, a pairwise interaction term capturing correlations between items, and a penalty enforcing the constraint. This is a Quadratic Unconstrained Binary Optimization (QUBO) problem. No monetary quantities are needed: the coefficients are abstract weights and correlations.

Mapping to a Hamiltonian

Substitute x_i = (1 - Z_i)/2 to turn the QUBO into an Ising cost Hamiltonian H_C = sum_i h_i Z_i + sum_{i

Constraint handling

• Penalty method: add a large multiplier times the squared constraint violation; simple but can distort the landscape.
• Constraint-preserving mixers: replace the standard X mixer with one that only moves between feasible states, keeping the search on the constraint surface.
• Post-selection: discard infeasible measurement outcomes after sampling.

Running QAOA

With H_C fixed, apply depth-p QAOA exactly as for MaxCut: alternate cost and mixer layers, optimize the angles against the measured average energy, and sample low-energy bitstrings. The interaction term J_{ij} produces ZZ rotations between the corresponding qubits, so the connectivity of the interaction graph sets the two-qubit gate pattern.

Practical remarks

Dense interaction matrices demand all-to-all coupling, which increases circuit depth on hardware with limited connectivity due to routing swaps. Constraint-preserving mixers reduce wasted samples on large instances. Because the objective is abstract, this template applies equally to portfolio-style selection, sensor placement, and feature subset selection, all without any economic figures.