The disjointness of stabilizer codes and limitations on fault-tolerant logical gates

Abstract

Stabilizer codes are a simple and successful class of quantum error-correcting codes. Yet this success comes in spite of some harsh limitations on the ability of these codes to fault-tolerantly compute. Here we introduce a new metric for these codes, the disjointness, which, roughly speaking, is the number of mostly non-overlapping representatives of any given non-trivial logical Pauli operator. We use the disjointness to prove that transversal gates on error-detecting stabilizer codes are necessarily in a finite level of the Clifford hierarchy. We also apply our techniques to topological code families to find similar bounds on the level of the hierarchy attainable by constant depth circuits, regardless of their geometric locality. For instance, we can show that symmetric 2D surface codes cannot have non-local constant depth circuits for non-Clifford gates.

8+3 pages, 2 figures. Comments welcome

References in corpus (10)

• Local stabilizer codes in three dimensions without string logical operators
• Topological Quantum Distillation
• Restrictions on Transversal Encoded Quantum Gate Sets
• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Universal transversal gates with color codes - a simplified approach
• Fault-tolerant logical gates in quantum error-correcting codes
• Code properties from holographic geometries
• Locality-Preserving Logical Operators in Topological Stabiliser Codes
• Framework for classifying logical operators in stabilizer codes

Cited by in corpus (38)

• Triangular color codes on trivalent graphs with flag qubits
• 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
• A fault-tolerant non-Clifford gate for the surface code in two dimensions
• The boundaries and twist defects of the color code and their applications to topological quantum computation
• On Optimality of CSS Codes for Transversal $T$
• 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
• Topological Order, Quantum Codes and Quantum Computation on Fractal Geometries
• New perspectives on covariant quantum error correction
• Partitioning qubits in hypergraph product codes to implement logical gates
• Cellular automaton decoders for topological quantum codes with noisy measurements and beyond
• Efficient color code decoders in $d\ge 2$ dimensions from toric code decoders
• Quantum Origami: Transversal Gates for Quantum Computation and Measurement of Topological Order
• A High Performance Compiler for Very Large Scale Surface Code Computations
• Universal Fault-Tolerant Quantum Computing with Stabiliser Codes
• A Family of Quantum Codes with Exotic Transversal Gates
• Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code
• A four-dimensional toric code with non-Clifford transversal gates
• Magic State Distillation from Entangled States
• Fault-tolerant gates via homological product codes
• Fault-tolerant quantum metrology
• Quantum error correction with fractal topological codes
• Fault-tolerant logical gates in holographic stabilizer codes are severely restricted
• Universal Logical Gates on Topologically Encoded Qubits via Constant-Depth Unitary Circuits
• Homological Quantum Rotor Codes: Logical Qubits from Torsion
• On Groups in the Qubit Clifford Hierarchy
• The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies
• Permutation-Invariant Quantum Codes with Transversal Generalized Phase Gates
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Lift-Connected Surface Codes
• Geometric structure and transversal logic of quantum Reed-Muller codes
• Classification of the Subgroups of the Two-Qubit Clifford Group
• Finding the disjointness of stabilizer codes is NP-complete
• Flexible Fault Tolerant Gate Gadgets
• Color code with a logical control-$S$ gate using transversal $T$ rotations