In combinatorial optimization, the "haystack" of possible solutions grows exponentially with the number of variables. For a problem with $N$ bits, there are $2^N$ possible configurations. However, in real-world problems—like scheduling flights or routing vehicles—the vast majority of these configurations are "illegal." They violate hard constraints, such as a single plane being in two places at once or a truck exceeding its cargo capacity.
Standard quantum approaches, like the original Quantum Approximate Optimization Algorithm (QAOA), treat these constraints as "soft" penalties. They search the entire $2^N$ space and hope the quantum state eventually settles into a valid region. Recent research has shifted toward a more efficient paradigm: hard constraint enforcement. By mathematically restricting the quantum search to a "feasible subspace," researchers are finding they can achieve higher accuracy with fewer computational resources.
The Problem with Soft Penalties
Traditionally, constraints are mapped to a Hamiltonian as penalty terms. If a constraint is violated, the energy of that state is increased. While simple to implement, this approach has two major drawbacks:
- Landscape Complexity: Adding penalties creates a "jagged" energy landscape. As noted by Jonas Stein and Maximilian Zorn in Quantum Optimization Algorithms, these penalties complicate the optimization process, making it harder for classical optimizers to find the right parameters.
- Wasted Exploration: In highly constrained problems, valid solutions might represent only a tiny fraction of the total space. Jingbo Wang 0001 and Zhihao Liu argue in Quantum approximate algorithm for NP optimization problems with constraints that exploring the entire Hilbert space is fundamentally inefficient when most states are invalid.
The Quantum Alternating Operator Ansatz
To solve this, Eleanor Rieffel, Stuart Hadfield, and colleagues at NASA’s QuAIL developed the Quantum Alternating Operator Ansatz (AOA). The core intuition is to replace the standard "mixer" operator—which can flip any bit—with a specialized mixer that only allows transitions between valid states.
In From Ansätze to Z-Gates: A NASA View of Quantum Computing, the authors demonstrate that if you start the quantum system in a valid state and only use mixers that preserve the problem's constraints, the system never leaves the feasible subspace. This ensures that every measurement at the end of the circuit yields a 100% valid solution.
Preserving Symmetry and Hamming Weight
The most common hard constraint is the cardinality constraint, where you must choose exactly $K$ items out of $N$. In quantum terms, this means the "Hamming weight" (the number of qubits in state $|1\rangle$) must remain constant.
Instead of a standard $X$-mixer, researchers use $XY$-mixers (or swap-based mixers). These operators exchange the states of two qubits: if they are both $|0\rangle$ or both $|1\rangle$, nothing happens; if they are different, they swap. As Pradeep Niroula and Shaohan Hu show in Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer, this natively preserves the number of selected items throughout the optimization.
Ge Yan further explores this in Rethinking the symmetry-preserving circuits for constrained variational quantum algorithms, proving that these Hamming Weight Preserving (HWP) circuits are not just restrictive, but also mathematically expressive enough to find optimal solutions in quantum chemistry and machine learning.
Enforcement via Quantum Zeno Dynamics
A different approach to staying within the feasible subspace involves frequent "checks" during the quantum evolution. This leverages the Quantum Zeno Effect, where frequent observation of a system prevents it from evolving out of a specific state.
In Constrained Optimization via Quantum Zeno Dynamics, Dylan Herman and Ruslan Shaydulin use mid-circuit projective measurements to "freeze" the system within the feasible subspace. By using an auxiliary "flag" qubit that triggers if a constraint is violated, they can suppress transitions into invalid states. This allows for the use of simpler, hardware-efficient mixers while still guaranteeing that the final output satisfies complex, non-linear constraints.
Application to Real-World Routing
The power of these methods is most evident in complex routing problems. In A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem, Ningyi Xie and Xinwei Lee apply constraint-preserving mixers to the Capacitated Vehicle Routing Problem (CVRP).
By integrating the constraints directly into the quantum state evolution and decoding logic, they achieved a 100% feasibility rate. This is a massive improvement over traditional penalty-based methods, which often return "illegal" routes that visit the same city twice or exceed vehicle capacity, rendering the quantum output useless without heavy classical post-processing.
The Trade-off: Complexity vs. Efficiency
While restricting the search space significantly improves the probability of finding an optimal solution, it comes with a cost. Specialized mixers and Zeno-based measurements often require more complex quantum circuits and deeper gate sequences.
As D. Bucher notes in Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems, the goal is to find a balance. By using specialized mixers for "hard" equality constraints and oracle-based penalties for "softer" inequalities, researchers can minimize the number of required quantum measurements while ensuring the algorithm stays focused on the most promising, valid regions of the solution space.