T-count optimization and Reed-Muller codes

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

19 pages. Version 2 gives a substantially different presentation of the results, as well as a generalization to rotation angles of any finite order

References in corpus (8)

• Magic state distillation with low overhead
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Quantum circuits of T-depth one
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Fast Quantum Modular Exponentiation
• Efficient synthesis of universal Repeat-Until-Success circuits
• Reducing the quantum computing overhead with complex gate distillation
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Cited by in corpus (31)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Magic State Distillation: Not as Costly as You Think
• Reducing T-count with the ZX-calculus
• Lower bounds on the non-Clifford resources for quantum computations
• Phase Gadget Synthesis for Shallow Circuits
• Robust quantum compilation and circuit optimisation via energy minimisation
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Entanglement-magic separation in hybrid quantum circuits
• Reducing the Depth of Linear Reversible Quantum Circuits
• Constructing quantum circuits with global gates
• A polynomial time and space heuristic algorithm for T-count
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Hierarchies of resources for measurement-based quantum computation
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Linear and non-linear relational analyses for Quantum Program Optimization
• Disentangling magic states with classically simulable quantum circuits
• Generators and Relations for Un(Z[1/2,i])
• Symbolic Synthesis of Clifford Circuits and Beyond
• Generators and Relations for 2-Qubit Clifford+T Operators
• Optimal compilation of parametrised quantum circuits
• Lower T-count with faster algorithms
• Wasserstein Complexity of Quantum Circuits
• Quantum advantage in temporally flat measurement-based quantum computation
• Scalable Spider Nests (...Or How to Graphically Grok Transversal Non-Clifford Gates)
• T-Count Optimizing Genetic Algorithm for Quantum State Preparation
• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation
• Reducing depth and measurement weights in Pauli-based computation
• CNOT Minimal Circuit Synthesis: A Reinforcement Learning Approach