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$.

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

References in corpus (7)

• Superconducting qubit in waveguide cavity with coherence time approaching 0.1ms
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• Quantum circuits of T-depth one
• Novel constructions for the fault-tolerant Toffoli gate
• Exact synthesis of multiqubit Clifford+T circuits
• Efficient synthesis of universal Repeat-Until-Success circuits
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal 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