{
  "id": "2312.13206",
  "version": "v1",
  "published": "2023-12-20T17:23:11.000Z",
  "updated": "2023-12-20T17:23:11.000Z",
  "title": "Polylogarithmic-depth controlled-NOT gates without ancilla qubits",
  "authors": [
    "Baptiste Claudon",
    "Julien Zylberman",
    "César Feniou",
    "Fabrice Debbasch",
    "Alberto Peruzzo",
    "Jean-Philip Piquemal"
  ],
  "categories": [
    "quant-ph"
  ],
  "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\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-20T17:23:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ancilla qubits",
      "polylogarithmic-depth controlled-not gates",
      "quantum algorithms",
      "circuit depth",
      "fault-tolerant quantum"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}