A polynomial time and space heuristic algorithm for T-count

Abstract

This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set. Our primary interest is to compute a circuit for a given $n$-qubit unitary $U$, using the minimum possible number of T gates (called the T-count of unitary $U$). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of $U$. In its decision version the goal is to decide if the T-count is at most some positive integer $m$. Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of $U$. We give a provable classical algorithm that solves COUNT-T (decision) in time $O\left(N^{2(c-1)\lceil \frac{m}{c}\rceil }\text{poly}(m,N)\right)$ and space $O\left(N^{2\lceil \frac{m}{c}\rceil }\text{poly}(m,N)\right)$, where $N=2^n$ and $c\ge 2$. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of $N^{0.7457}$ off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity $\text{poly}(m,N)$, under some assumptions. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent, there is a large improvement by going from exponential to polynomial scaling with $m$.

arXiv commentAccepted in Quantum Science and Technology journal (not the exact journal version)

References in corpus (27)

• Fault-tolerant quantum computation by anyons
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
• Superconducting qubit in waveguide cavity with coherence time approaching 0.1ms
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• High threshold universal quantum computation on the surface code
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Halving the cost of quantum addition
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Quantum circuits of T-depth one
• Single-qubit-gate error below 10^-4 in a trapped ion
• Novel constructions for the fault-tolerant Toffoli gate
• Towards practical classical processing for the surface code
• Exact synthesis of multiqubit Clifford+T circuits
• Reducing T-count with the ZX-calculus
• Strong Resilience of Topological Codes to Depolarization
• Efficient synthesis of universal Repeat-Until-Success circuits
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• On the CNOT-complexity of CNOT-PHASE circuits
• T-count optimization and Reed-Muller codes
• Parallelizing quantum circuit synthesis
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Synthesis of unitaries with Clifford+T circuits

Cited by in corpus (8)

• T-count and T-depth of any multi-qubit unitary
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Synthesizing efficient circuits for Hamiltonian simulation
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Wasserstein Complexity of Quantum Circuits
• Composability of global phase invariant distance and its application to approximation error management
• Constructing all qutrit controlled Clifford+T gates in Clifford+T