Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Abstract

Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cⁿ(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cⁿ(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 {\left(n\right)}^3\right)$ , an approximating one without ancilla qubits with a circuit depth $O\left(\log {\left(n\right)}^3\log \left(1/ϵ\right)\right)$ and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as $O\left(\log {\left(n/\lfloor m/2\rfloor \right)}^3+\log \left(\lfloor m/2\rfloor \right)\right)$ . 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.