Lower T-count with faster algorithms

Abstract

Among the cost metrics characterizing a quantum circuit, the $T$-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the $T$-count reduction problem by proposing efficient $T$-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of $T$ gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated. We also prove that the number of $T$ gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of $n$ qubits is upper bounded by $n(n+1)/2+1$, which improves on the worst-case $T$-count of existing optimization algorithms. From this we derive an upper bound of $(n+1)(n+2h)/2+1$ for the number of $T$ gates in a Clifford$+T$ circuit where $h$ is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last $T$ gate of the circuit.

References in corpus (35)

• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Topological fault-tolerance in cluster state quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• High threshold universal quantum computation on the surface code
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Magic state distillation with low overhead
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum circuits of T-depth one
• Novel constructions for the fault-tolerant Toffoli gate
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• staq -- A full-stack quantum processing toolkit
• On the CNOT-complexity of CNOT-PHASE circuits
• Efficient synthesis of probabilistic quantum circuits with fallback
• Shorter gate sequences for quantum computing by mixing unitaries
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Improved upper bounds on the stabilizer rank of magic states
• T-count optimization and Reed-Muller codes
• Reducing the quantum computing overhead with complex gate distillation
• Shorter quantum circuits via single-qubit gate approximation
• Quantum circuits and low-degree polynomials over F_2
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Architecture aware compilation of quantum circuits via lazy synthesis
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• AND-gates in ZX-calculus: Spider Nest Identities and QBC-completeness

Cited by in corpus (1)

• Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation