T-Count Optimization and Reed-Muller Codes

In this paper, we study the close relationship between Reed-Muller codes and single-qubit phase gates from the perspective of T-count optimization. We prove that minimizing the number of T gates in an n-qubit quantum circuit over CNOT and T, together with the Clifford group powers of T, corresponds to finding a minimum distance decoding of a length 2(n) - 1 binary vector in the order n - 4 punctured Reed-Muller code. Moreover, we show that the problems are polynomially equivalent in the length of the code. As a consequence, we derive an algorithm for the optimization of T-count in quantum circuits based on Reed-Muller decoders, along with a new upper bound of O(n(2)) on the number of T gates required to implement an n-qubit unitary over CNOT and T gates. We further generalize this result to show that minimizing small angle rotations corresponds to decoding lower order binary Reed-Muller codes. In particular, we show that minimizing the number of R-Z(2 pi / m) gates for any integer m is equivalent to minimum distance decoding in RM(n - k - 1, n)*, where k is the highest power of 2 dividing m.