A Caltech Library Service

Finding the disjointness of stabilizer codes is NP-complete

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.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Bostanci, John0000-0001-9666-7114
Kubica, Aleksander0000-0001-8213-8190
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
Funding AgencyGrant Number
Simons FoundationUNSPECIFIED
Department of Innovation, Science and Economic Development (Canada)UNSPECIFIED
Ontario Ministry of Colleges and UniversitiesUNSPECIFIED
Issue or Number:4
Record Number:CaltechAUTHORS:20211220-495807000
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112570
Deposited By: George Porter
Deposited On:20 Dec 2021 22:00
Last Modified:20 Dec 2021 22:00

Repository Staff Only: item control page