T-count and T-depth of any multi-qubit unitary

Abstract

While implementing a quantum algorithm it is crucial to reduce the quantum resources, in order to obtain the desired computational advantage. For most fault-tolerant quantum error-correcting codes the cost of implementing the non-Clifford gate is the highest among all the gates in a universal fault-tolerant gate set. In this paper we design provable algorithm to determine T-count of any $n$-qubit ($n\ge 1$) unitary $W$ of size $2^n\times 2^n$, over the Clifford+T gate set. The space and time complexity of our algorithm are $O\left(2^{2n}\right)$ and $O\left(2^{2n{\mathcal{T}}_{\epsilon }(W)+4n}\right)$ respectively. ${\mathcal{T}}_{\epsilon }(W)$ ($\epsilon$-T-count) is the (minimum possible) T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that $d(U,W)\le \epsilon$ and $\mathcal{T}(U)\le \mathcal{T}(U^{\prime })$ where $U^{\prime }$ is any exactly implementable unitary with $d(U^{\prime },W)\le \epsilon$. $d(.,.)$ is the global phase invariant distance. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary and the complexity has exponential dependence on $n$ and $\epsilon$-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit ($n\ge 1$) unitary. For small enough $\epsilon$, we can synthesize the T-count and T-depth-optimal circuits. Our results can be used to determine the minimum count (or depth) of non-Clifford gates required to implement any multi-qubit unitary with a universal gate set consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such optimal-synthesis algorithm for arbitrary multi-qubit unitaries in any universal gate set.

Accepted for publication in Nature Partner Journal Quantum Information. Not structured according to the journal policies. Compared to v3 : A note about implementation of 2-qubit QFT in Table 3

References in corpus (9)

• Simulating chemistry efficiently on fault-tolerant quantum computers
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Universal quantum circuits for quantum chemistry
• Time-optimal quantum computation
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Quantum circuit synthesis using Householder transformations
• Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
• Composability of global phase invariant distance and its application to approximation error management

Cited by in corpus (18)

• Projection algorithm for state preparation on quantum computers
• Systems Architecture for Quantum Random Access Memory
• Synthesizing efficient circuits for Hamiltonian simulation
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Single-step high-fidelity three-qubit gates by anisotropic chiral interactions
• Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning
• Classical simulation and quantum resource theory of non-Gaussian optics
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth
• Trotter simulation of vibrational Hamiltonians on a quantum computer
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Wasserstein Complexity of Quantum Circuits
• Weighted Quantum Channel Compiling through Proximal Policy Optimization
• High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
• Composability of global phase invariant distance and its application to approximation error management
• Quantum Chebyshev Probabilistic Models for Fragmentation Functions
• Quantum phase estimation with optimal confidence interval using three control qubits
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits