Quantum state preparation with optimal T-count

Abstract

How many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $\epsilon$? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is $\hat{I}˜\left(\sqrt{2^n\log (1/\epsilon )}+\log (1/\epsilon )\right)$ if we allow ancilla qubits. We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $\epsilon$. We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.

Quantum journal version; minor revision