T-count optimization and Reed-Muller codes

Understand

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.