Quantum circuit compilation with constant overhead

Compiling a continuous gate set to a discrete universal gate set generally incurs an overhead. A circuit composed of $G$ arbitrary one- and two-qubit gates can be $\epsilon$-approximated by a sequence of gates from $\{H,T,\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}\}$ by replacing each original gate by a sequence of $O(\log (G\mathrm{/}\epsilon ))$ elementary gates. We show that this overhead can be avoided using adaptivity for polynomial-sized circuits with inverse-polynomial target error, which is optimal.