Polylogarithmic-depth controlled-NOT gates without ancilla qubits

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

Published 2023-12-20Version 1

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)^{\log_2(12)}\right)$, an approximating one without ancilla qubits with a circuit depth $\mathcal O \left(\log(n)^{\log_2(12)}\log(1/\epsilon)\right)$ and an exact one with an adjustable-depth circuit using $m\leq n$ ancilla qubits. 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.