  Controlled operations are fundamental building blocks of quantum algorithms.
Decomposing $n$-control-NOT gates ($C^n(X)$) into arbitrary single-qubit and
CNOT gates, is a crucial but non-trivial task. This study introduces $C^n(X)$
circuits outperforming previous methods in the asymptotic and non-asymptotic
regimes. Three distinct decompositions are presented: an exact one using one
borrowed ancilla with a circuit depth $\Theta\left(\log(n)^{3}\right)$, an
approximating one without ancilla qubits with a circuit depth $\mathcal O
\left(\log(n)^{3}\log(1/\epsilon)\right)$ and an exact one with an
adjustable-depth circuit which decreases with the number $m\leq n$ of ancilla
qubits available as $O(log(2n/m)^3+log(m/2))$. The resulting exponential
speedup is likely to have a substantial impact on fault-tolerant quantum
computing by improving the complexities of countless quantum algorithms with
applications ranging from quantum chemistry to physics, finance and quantum
machine learning.
