Finding the disjointness of stabilizer codes is NP-complete
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918149250613248 |
|---|---|
| author | Bostanci, John Kubica, Aleksander |
| author_facet | Bostanci, John Kubica, Aleksander |
| contents | The disjointness of a stabilizer code is a quantity used to constrain the level of the logical Clifford hierarchy attainable by transversal gates and constant-depth quantum circuits. We show that for any positive integer constant $c$, the problem of calculating the $c$-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes, concatenated codes and hypergraph product codes. We also describe numerical methods of finding the disjointness, which can be readily used to rule out the existence of any transversal gate implementing some non-Clifford logical operation in small stabilizer codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_04738 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Finding the disjointness of stabilizer codes is NP-complete Bostanci, John Kubica, Aleksander Quantum Physics The disjointness of a stabilizer code is a quantity used to constrain the level of the logical Clifford hierarchy attainable by transversal gates and constant-depth quantum circuits. We show that for any positive integer constant $c$, the problem of calculating the $c$-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes, concatenated codes and hypergraph product codes. We also describe numerical methods of finding the disjointness, which can be readily used to rule out the existence of any transversal gate implementing some non-Clifford logical operation in small stabilizer codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task. |
| title | Finding the disjointness of stabilizer codes is NP-complete |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2108.04738 |