New Directions From Old Codes

Abstract

Reed-Muller (RM) codes form a classic family studied for its interesting algebraic and combinatorial properties as well as from the perspective of information transmission. They achieve Shannon capacity of the basic binary channel models such as channels with independent erasures or flip errors. They have numerous applications to the theory of computational complexity and have well-understood local testability. They also give rise to a family of quantum codes admitting transversal logical operators in increasing levels of the Clifford hierarchy, a property of codes considered necessary for future fault-tolerant quantum computations.

In this dissertation, we show that, despite decades of research surrounding RM codes, new directions sprouting from their simple definition continue to be possible. We will begin by considering an alternate description of RM codes in terms of faces of the Boolean hypercube, and will see that by replacing the hypercube with a more general algebraic object we obtain a large class of previously undiscovered classical error-correcting codes sharing many structural properties with RM codes. These classical codes directly lead to an even larger class of new quantum error-correcting codes with explicitly determined parameters; we will demonstrate that these quantum codes admit many natural transversal logical gates. We finish by specializing to the class of quantum Reed-Muller codes and provide a complete characterization of the logic implemented by these transversal operators, yielding a broad generalization of prior work on the subject.