Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2310.20191 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910321563664384 |
|---|---|
| author | Pawlak, Kelly Ann Epstein, Jeffrey M. Crow, Daniel Gandhari, Srilekha Li, Ming Bohdanowicz, Thomas C. King, Jonathan |
| author_facet | Pawlak, Kelly Ann Epstein, Jeffrey M. Crow, Daniel Gandhari, Srilekha Li, Ming Bohdanowicz, Thomas C. King, Jonathan |
| contents | 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 $λ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_20191 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum Subspace Correction for Constraints Pawlak, Kelly Ann Epstein, Jeffrey M. Crow, Daniel Gandhari, Srilekha Li, Ming Bohdanowicz, Thomas C. King, Jonathan Quantum Physics 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 $λ_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. |
| title | Quantum Subspace Correction for Constraints |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2310.20191 |