Quantum state preparation with optimal T-count

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 $\mathrm{\Theta }(\sqrt{2^n\log (1\mathrm{/}\epsilon )}+\log (1\mathrm{/}\epsilon ))$ 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.