Nature Communications (Jul 2024)

Polylogarithmic-depth controlled-NOT gates without ancilla qubits

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

DOI
https://doi.org/10.1038/s41467-024-50065-x
Journal volume & issue
Vol. 15, no. 1
pp. 1 – 8

Abstract

Read online

Abstract 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 (\log {(n)}^{3})$$ Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth $${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$$ 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 $${{{{{{{\mathcal{O}}}}}}}}(\log {(n/\lfloor m/2\rfloor )}^{3}+\log (\lfloor m/2\rfloor ))$$ 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.