Open Collections

T-count optimization and Reed-Muller codes

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Quantum theory; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: University of Waterloo

2016-10-25

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59563

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/