Bostanci, John and Kubica, Aleksander (2021) Finding the disjointness of stabilizer codes is NP-complete. Physical Review Research, 3 (4). Art. No. 043192. ISSN 2643-1564. doi:10.1103/physrevresearch.3.043192. https://resolver.caltech.edu/CaltechAUTHORS:20211220-495807000
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Creative Commons Attribution. 489kB |
|
PDF
- Submitted Version
See Usage Policy. 586kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20211220-495807000
Abstract
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 Calderbank-Shor-Steane 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.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 2021 The Author(s). Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI. (Received 12 August 2021; accepted 18 November 2021; published 20 December 2021) A.K. thanks D. Gosset, A. Landahl, P. Ronagh, and J. Sikora for helpful discussions. A.K. acknowledges funding provided by the Simons Foundation through the “It from Qubit” Collaboration. Research at Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Colleges and Universities. J.B. thanks J. Watrous, D. Gosset, D. Geier, and L. Shaeffer for their helpful discussions. This work was completed prior to A.K. joining AWS Center for Quantum Computing. | |||||||||
| Group: | AWS Center for Quantum Computing | |||||||||
| Funders: |
| |||||||||
| Issue or Number: | 4 | |||||||||
| DOI: | 10.1103/physrevresearch.3.043192 | |||||||||
| Record Number: | CaltechAUTHORS:20211220-495807000 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20211220-495807000 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 112570 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | George Porter | |||||||||
| Deposited On: | 20 Dec 2021 22:00 | |||||||||
| Last Modified: | 20 Dec 2021 22:00 |
Repository Staff Only: item control page
