Quantum computers, particularly quantum annealers and those running the Quantum Approximate Optimization Algorithm (QAOA), are naturally designed to solve unconstrained problems. They act like marbles rolling through a landscape, seeking the lowest point of "energy." However, real-world problems—from protein folding to vehicle routing—are defined by strict rules or constraints.
To bridge this gap, researchers use penalty methods to transform logical constraints into physical energy barriers. This turns a constrained search into an unconstrained "ground-state" search, where the laws of physics do the heavy lifting of optimization.
Mapping Logic to Energy
The fundamental challenge in quantum optimization is representing a problem as a Quadratic Unconstrained Binary Optimization (QUBO) model or an Ising Hamiltonian. As Tian Huang and colleagues explain in Benchmarking Quantum(-inspired) Annealing Hardware on Practical Use Cases, this framework serves as a universal interface.
The intuition is simple: if a solution violates a constraint (e.g., two objects occupying the same space), we add a positive energy "penalty" to that state. In Construction of model Hamiltonians for adiabatic quantum computation, Alejandro Perdomo demonstrates this by adding energy penalties for invalid protein configurations. If the penalty is high enough, the quantum system will naturally avoid those "high-altitude" invalid states, settling instead into a "low-energy" valid solution.
The Landscape Distortion Problem
While adding penalties sounds straightforward, it creates a treacherous mathematical terrain. Kun Cao and Guang‐Can Guo note in Efficient numerical method to calculate the three-tangle of mixed states that enforcing physical constraints often results in a highly irregular and "rough" optimization landscape.
This leads to a fundamental trade-off:
- Low Penalties: If the penalty is too small, the "optimal" point found by the computer might be an invalid solution that simply has very low base energy.
- High Penalties: If the penalty is too large, it dominates the landscape, "flattening" the subtle valleys of the actual objective function. As Finley Alexander Quinton observes in Quantum annealing applications, challenges and limitations, this distortion makes the global minimum nearly impossible to locate, as the solver gets trapped in the "jagged" local minima created by the constraints.
Engineering the Weights
Because the success of the algorithm depends on the precise balance of these penalties (often called Lagrange multipliers), much of the current research focuses on penalty calibration.
Traditionally, these weights were tuned manually through trial and error. However, Christoph Roch and Thomas Gabor proposed using the Cross Entropy method to automatically "smooth out" the terrain. More recently, Lorenzo Cellini and Antonio Macaluso introduced QAL-BP, which uses an Augmented Lagrangian framework to analytically calculate penalty multipliers, removing the need for instance-by-instance manual tuning.
Beyond Soft Penalties
Recognizing the limitations of "soft" penalties, some researchers are moving toward "hard" constraint enforcement within the quantum circuit itself.
- Symmetry-Preserving Circuits: Ge Yan and Junchi Yan argue in Rethinking the symmetry-preserving circuits for constrained variational quantum algorithms that we should use quantum gates that natively stay within the valid search space (like Hamming Weight preserving gates), rather than letting the state wander into invalid territory and penalizing it later.
- Quantum Zeno Dynamics: In Constrained Optimization via Quantum Zeno Dynamics, Dylan Herman and Ruslan Shaydulin use repeated measurements to "freeze" the quantum system within a feasible subspace, preventing it from ever evolving into an invalid state.
By refining how we translate human rules into quantum landscapes, these methods allow NISQ-era devices to tackle increasingly complex industrial problems, from railway rescheduling to aerospace design.