Polylogarithmic-depth controlled-NOT gates without ancilla qubits

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 O(log(n)^3), an approximating one without ancilla qubits with a circuit depth O(log(n)^3 log(1/ε)), and an exact one with an adjustable-depth circuit which decreases with the number m ≤ n of ancilla qubits available as O(log(n/m/2)^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.

Baptiste Claudon, Julien Zylberman, César Feniou, Fabrice Debbasch, Alberto Peruzzo, Jean-Philip Piquemal