Finding the disjointness of stabilizer codes is NP-complete
- Creators
-
Bostanci, John
-
Kubica, Aleksander
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.
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.Attached Files
Published - PhysRevResearch.3.043192.pdf
Submitted - 2108.04738.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:2c8431cd552d8b8843c6ed993114d7ea
|
586.1 kB | Preview Download |
|
md5:690a86b922cdd2c98365da43a6bb52b6
|
489.1 kB | Preview Download |
Additional details
- Eprint ID
- 112570
- Resolver ID
- CaltechAUTHORS:20211220-495807000
- Simons Foundation
- Department of Innovation, Science and Economic Development (Canada)
- Ontario Ministry of Colleges and Universities
- Created
-
2021-12-20Created from EPrint's datestamp field
- Updated
-
2021-12-20Created from EPrint's last_modified field
- Caltech groups
- AWS Center for Quantum Computing