Codes and Protocols for Distilling T, controlled-S, and Toffoli Gates

We present several different codes and protocols to distill T, controlled-S, and Toffoli (or CCZ) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal T. We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency γ→ 1. We also present a Reed-Muller based construction of these codes which obtains a worse γ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of CCZ magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of 1703.07847. Several examples, including a Reed-Muller code for T-to-Toffoli distillation, punctured Reed-Muller codes for T-gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a 512 T-gate to 10 Toffoli gate code with distance 8 as well as triorthogonal codes with parameters [[887,137,5]],[[912,112,6]],[[937,87,7]] with very low prefactors in front of the leading order error terms in those codes.