Finding the disjointness of stabilizer codes is NP-complete
arXiv:2108.04738 · doi:10.1103/PhysRevResearch.3.043192
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 , the problem of calculating the -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.
arXiv comment11 pages, 3 figures
References in corpus (30)
- Good Quantum Error-Correcting Codes Exist
- Quantum Teleportation is a Universal Computational Primitive
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Multiple Particle Interference and Quantum Error Correction
- A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
- Quantum Computing with Very Noisy Devices
- Restrictions on Transversal Encoded Quantum Gate Sets
- Active stabilisation, quantum computation and quantum state synthesis
- Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
- Classification of topologically protected gates for local stabilizer codes
- Unfolding the color code
- Universal transversal gates with color codes - a simplified approach
- Fault-tolerant logical gates in quantum error-correcting codes
- Continuous symmetries and approximate quantum error correction
- 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
- Three-dimensional surface codes: Transversal gates and fault-tolerant architectures
- A fault-tolerant non-Clifford gate for the surface code in two dimensions
- Concatenated Quantum Codes
- Fault-Tolerant Postselected Quantum Computation: Threshold Analysis
- Protected gates for topological quantum field theories
- Code properties from holographic geometries
- Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem
- Continuous groups of transversal gates for quantum error correcting codes from finite clock reference frames
- The disjointness of stabilizer codes and limitations on fault-tolerant logical gates
- Qudit Colour Codes and Gauge Colour Codes in All Spatial Dimensions
- 2D quantum computation with 3D topological codes
- A four-dimensional toric code with non-Clifford transversal gates
- Transversal gates and error propagation in 3D topological codes
- The surface code on the rhombic dodecahedron