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.