Quantum Subspace Correction for Constraints

• Published in: arXiv.org 2024-02
• Main Authors: Pawlak, Kelly Ann, Epstein, Jeffrey M, Crow, Daniel, Gandhari, Srilekha, Li, Ming, Bohdanowicz, Thomas C, King, Jonathan
• Format: Article
• Language: English
• Subjects: Algorithms; Constraints; Fault tolerance; Ising model; Subspaces
• ISSN: 2331-8422

We demonstrate that it is possible to construct operators that stabilize the constraint-satisfying subspaces of computational problems in their Ising representations. We provide an explicit recipe to construct unitaries and associated measurements given a set of 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 ''quantum 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. The stopping condition can be modified for sub-graph approximations. We show that it can prepare exact Gibbs distributions on \(d-\)regular graphs below a critical hardness \(\lambda_d^*\) in sub-linear time. Finally, we look at a potential use of quantum subspace correction for fault-tolerant depth-reduction. In particular we investigate how the technique detects and recovers errors induced by Trotterization in preparing maximum independent set using an adiabatic state preparation algorithm.