Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks

It is a major challenge to construct good quantum codes supporting fault-tolerant (e.g. transversal) non-Clifford gates with low-weight parity-check measurements. In this paper, we construct the first known quantum codes with linear dimension and distance supporting transversal non-Clifford gates that have sublinear locality (i.e. parity-check weight). Specifically, we construct codes with transversal CCZ gates that have dimension and distance growing linearly in the block length, and have locality growing as the square root of the block length. We furthermore design an efficient decoding algorithm for these codes. The alphabet size of these codes grows as the square root of the block length, but it can be reduced to a constant (e.g. binary) while incurring a polylogarithmic loss in other parameters. We also show how to decrease the locality to the cube root of the block length, albeit with a larger alphabet size and slightly lower distance.We construct these codes as products of classical codes with appropriate algebraic structure. While our quantum codes are subsystem codes with non-commuting gauge operators, we show they nevertheless permit error correction from noisy syndrome measurements.As byproducts, we prove multiple technical results of independent interest. In particular, our efficient decoder can be viewed as a new multivariate generalization of Prony’s method for reconstructing a function from partial access to its Fourier transform. Meanwhile, our distance analysis involves new connections to the classical study of maximally recoverable codes. Our results on product codes also resolve a conjecture of Bravyi & Hastings (2014) in the large-alphabet regime, by providing a new construction of quantum codes with linear dimension and distance and small polynomial locality.