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=\bigoplus_{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 $\varepsilon$ without ancillae, and let $m$ be the largest of these costs. For arbitrary blocks, 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 approximating unitary to mix different control values and the 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-δ)L$ and $(3+δ)L$ for every fixed $δ>0$, except with probability $O(\varepsilon^{c_{n,δ}})$; here $L=\log_2(1/\varepsilon)$, $c_{n,δ}>0$, and the bound holds for sufficiently small $\varepsilon$. 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 $\varepsilon^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 $\varepsilon$, using at most $(9+δ)L$ $T$ gates for every fixed $δ>0$, with failure probability polynomially small in $\varepsilon$.