Quantum 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 provide an explicit recipe to construct unitaries and associated measurements given a set of constraints. The stabilizer measureme...

Full description

Saved in:
Bibliographic Details
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
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422