Subspace Correction for Constraints

We demonstrate that it is possible to construct operators that stabilize the constraint-satisfying subspaces of computational problems in their Ising representations. We explicitly construct concrete unitaries and associated measurements for some common constraints. The stabilizer measurements allow the detection of constraint violations, and provide a route to recovery back into the constrained subspace. We call this technique "subspace correction". As an example, we explicitly investigate the stabilizers using the simplest local constraint subspace: Independent Set. We find an algorithm that is guaranteed to produce a perfect uniform or weighted distribution over all constraint-satisfying states when paired with a stopping condition: a quantum analogue of partial rejection sampling.