Quantum circuit compilation with constant overhead

Abstract

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{CNOT}\}$ by replacing each original gate by a sequence of $O(\log(G/\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.