On Optimality of CSS Codes for Transversal $T$

Abstract

In order to perform universal fault-tolerant quantum computation, one needs to implement a logical non-Clifford gate. Consequently, it is important to understand codes that implement such gates transversally. In this paper, we adopt an algebraic approach to characterize all stabilizer codes for which transversal $T$ and $T^{-1}$ gates preserve the codespace. Our Heisenberg perspective reduces this to a finite geometry problem that translates to the design of certain classical codes. We prove three corollaries: (a) For any non-degenerate $[[n,k,d]]$ stabilizer code supporting a physical transversal $T$, there exists an $[[n,k,d]]$ CSS code with the same property; (b) Triorthogonal codes are the most general CSS codes that realize logical transversal $T$ via physical transversal $T$; (c) Triorthogonality is necessary for physical transversal $T$ on a CSS code to realize the logical identity. The main tool we use is a recent efficient characterization of certain diagonal gates in the Clifford hierarchy (arXiv:1902.04022). We refer to these gates as Quadratic Form Diagonal (QFD) gates. Our framework generalizes all existing code constructions that realize logical gates via transversal $T$. We provide several examples and briefly discuss connections to decreasing monomial codes, pin codes, generalized triorthogonality and quasitransversality. We partially extend these results towards characterizing all stabilizer codes that support transversal $\pi /2^{\ell }$ $Z$-rotations. In particular, using Ax's theorem on residue weights of polynomials, we provide an alternate characterization of logical gates induced by transversal $\pi /2^{\ell }$ $Z$-rotations on a family of quantum Reed-Muller codes. We also briefly discuss a general approach to analyze QFD gates that might lead to a characterization of all stabilizer codes that support any given physical transversal $1$- or $2$-local diagonal gate.

arXiv commentv2: Much improved proof for Theorem 2, and some presentation improvements in other proofs. Main sections: 16 pages, double column, IEEEtran style. Examples included. Comments welcome!

References in corpus (29)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Experimental Comparison of Two Quantum Computing Architectures
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Restrictions on Transversal Encoded Quantum Gate Sets
• Magic state distillation with low overhead
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Algebraic Properties of Polar Codes From a New Polynomial Formalism
• Universal transversal gates with color codes - a simplified approach
• Using concatenated quantum codes for universal fault-tolerant quantum gates
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Diagonal gates in the Clifford hierarchy
• Unifying gate-synthesis and magic state distillation
• The disjointness of stabilizer codes and limitations on fault-tolerant logical gates
• 2-D Compass Codes
• Qudit Colour Codes and Gauge Colour Codes in All Spatial Dimensions
• Ground-state energy estimation of the water molecule on a trapped ion quantum computer
• Complex instruction set computing architecture for performing accurate quantum $Z$ rotations with less magic
• Unifying the Clifford Hierarchy via Symmetric Matrices over Rings
• Towers of generalized divisible quantum codes
• Synthesis of Logical Clifford Operators via Symplectic Geometry
• Classical Coding Problem from Transversal $T$ Gates
• Fault-tolerant conversion between adjacent Reed-Muller quantum codes based on gauge fixing
• Magic state distillation with punctured polar codes
• On products and powers of linear codes under componentwise multiplication

Cited by in corpus (28)

• Quantum Lego: Building Quantum Error Correction Codes from Tensor Networks
• The XP Stabiliser Formalism: a Generalisation of the Pauli Stabiliser Formalism with Arbitrary Phases
• Logical Clifford Synthesis for Stabilizer Codes
• Magic State Distillation from Entangled States
• Classification of Small Triorthogonal Codes
• Designing the Quantum Channels Induced by Diagonal Gates
• Quantum Pin Codes
• Entanglement Purification with Quantum LDPC Codes and Iterative Decoding
• Mitigating Coherent Noise by Balancing Weight-2 $Z$-Stabilizers
• Structure of CSS and CSS-T Quantum Codes
• An algebraic characterization of binary CSS-T codes and cyclic CSS-T codes for quantum fault tolerance
• Climbing the Diagonal Clifford Hierarchy
• Permutation-Invariant Quantum Codes with Transversal Generalized Phase Gates
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Non-Pauli Errors in the Three-Dimensional Surface Code
• Geometric structure and transversal logic of quantum Reed-Muller codes
• Transversal Clifford and T-gate codes of short length and high distance
• CSS-T Codes from Reed Muller Codes
• Contextuality of Quantum Error-Correcting Codes
• Classical Coding Approaches to Quantum Applications
• Scalable Spider Nests (...Or How to Graphically Grok Transversal Non-Clifford Gates)
• Describing quantum metrology with erasure errors using weight distributions of classical codes
• General entropic constraints on CSS codes within magic distillation protocols
• Secure multi-party quantum computation protocol for quantum circuits: the exploitation of triply-even quantum error-correcting codes
• GPU-Accelerated Syndrome Decoding for Quantum LDPC Codes below the 63 $\mu$s Latency Threshold
• Flexible Fault Tolerant Gate Gadgets
• Coxeter codes: Extending the Reed-Muller family
• Synthesis of Single Qutrit Circuits from Clifford+R