T-Count Optimization and Reed–Muller Codes

DOI10.1109/TIT.2019.2906374MaRDI QIDQ5224110zbMATH OpenWikidataFDO

Authors Matthew Amy, Michele Mosca

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.07363

zbMATH Keywords

minimum distance decodingn-qubit quantum circuitrelationship between Reed-Muller codes and single-qubit phase gatesT-count optimization

Mathematics Subject Classification ID

Combinatorial codes (94B25) Decoding (94B35) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Abstract: 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(2pi/d)$ gates for any integer $d$ is equivalent to minimum distance decoding in $mathcalRM(n-k-1,n{)}^{\ast }$, where $k$ is the highest power of $2$ dividing $d$.

Cited in

(16)

• Optimal diagonal qutrit gates for creating Wigner negativity
• A finite presentation of CNOT-dihedral operators
• Towards large-scale functional verification of universal quantum circuits
• scientific article; zbMATH DE number 7449972 (Why is no real title available?)
• Techniques to reduce /4-parity-phase circuits, motivated by the ZX calculus
• scientific article; zbMATH DE number 7453183 (Why is no real title available?)
• Hierarchies of resources for measurement-based quantum computation
• Toffoli-depth reduction method preserving in-place quantum circuits and its application to SHA3-256
• Generators and relations for \(U_n(\mathbb{Z}[\frac{1}{2}, i])\)
• Groups of diagonal gates in the Clifford hierarchy
• Approximate optimisation of quantum circuits using the ZX calculus with phase squashing
• Deriving T-gates from cubic phase gates via GKP encoding
• Scalable spider nests ({\dots}or how to graphically grok transversal non-Clifford gates)
• Symbolic synthesis of Clifford circuits and beyond
• Generators and relations for 2-qubit Clifford+T operators
• Wasserstein complexity of quantum circuits

This page was built for publication: T-Count Optimization and Reed–Muller Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224110)