Multi-qubit controlled gate synthesis without T-count overhead in the small-error limit

Abstract

We study the Clifford+T synthesis of quantum multiplexers $U={⨁}_{i=1}^{2^n}{U}_i$: an $n$-qubit control register selects which single-qubit gate $U_i\in \mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$, consider the minimum even T-count needed to approximate it within diamond distance $\epsilon$ without ancillae, and let $m$ be the largest of these costs. For an arbitrary multiplexer $U$, we construct an approximation of $U$ within the same distance using at most $m+O(\sqrt{2^n(m+1)})$ $T$ gates. With one control qubit, the cost is $m+O(1)$ and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed $n$ and independent Haar-random blocks, the minimum T-count among these circuits lies between $(3-\delta ){\log }_2(1/\epsilon )$ and $(3+\delta ){\log }_2(1/\epsilon )$ for every fixed $\delta >0$, except with probability $O({\epsilon }^{c_{n,\delta }})$ as $\epsilon \to 0$. The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{SU}(2)$ gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ${\epsilon }^2$. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random $\mathrm{SU}(4)$ gates within diamond distance $\epsilon$, using at most $(9+\delta ){\log }_2(1/\epsilon )$ $T$ gates for every fixed $\delta >0$, except with probability $O({\epsilon }^{c_{\delta }})$ with $c_{\delta }>0$.

arXiv comment39 pages, 2 figures