Finding the disjointness of stabilizer codes is NP-complete

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 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.

11 pages, 3 figures

References in corpus (8)

• Restrictions on Transversal Encoded Quantum Gate Sets
• Universal transversal gates with color codes - a simplified approach
• Fault-tolerant logical gates in quantum error-correcting codes
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Fault-Tolerant Postselected Quantum Computation: Threshold Analysis
• A four-dimensional toric code with non-Clifford transversal gates
• The surface code on the rhombic dodecahedron

Cited by in corpus (1)

• Universal Fault-Tolerant Quantum Computing with Stabiliser Codes