Open Collections

Description

In this talk I will show that minimizing T-count in n-qubit CNOT and T quantum circuits reduces to minimum distance decoding of the length $2^n-1$ punctured Reed-Muller code of order $n-4$. A converse reduction also exists, providing strong evidence that no polynomial-time solution is possible. As a consequence, we derive an algorithm for the optimization of T-count in Clifford+T circuits which can utilize the wide variety of Reed-Muller decoders developed over the years, along with a new upper bound on the number of T gates required to implement a unitary over CNOT and T gates. I will further generalize this result to show that minimizing finer angle Z-rotations corresponds to decoding lower order binary Reed-Muller codes. Joint work with Michele Mosca.