{
  "id": "2011.10031",
  "version": "v1",
  "published": "2020-11-19T18:52:38.000Z",
  "updated": "2020-11-19T18:52:38.000Z",
  "title": "Topological obstructions to implementing controlled unknown unitaries",
  "authors": [
    "Zuzana Gavorová",
    "Matan Seidel",
    "Yonathan Touati"
  ],
  "comment": "18 pages + 5 page Appendix, 6 figures",
  "categories": [
    "quant-ph"
  ],
  "abstract": "Is a quantum algorithm capable of implementing an if-clause? Given a black-box subroutine, a $d$-dimensional unitary $U\\in U(d)$, a quantum if-clause would correspond to applying it to an input qudit if and only if the value of a control qubit is $1$. It was previously shown by Thompson et al. and Ara\\'ujo et al. that implementations using single access to the oracle $U$ are impossible. Our main result is a strong generalization of this impossibility result: we prove that there is no unitary oracle algorithm implementing $control_\\phi(U)=\\left|0\\right>\\!\\!\\left<0\\right|\\otimes I+e^{i\\phi(U)}\\left|1\\right>\\!\\!\\left<1\\right|\\otimes U$, for some $U$-dependent phase $\\phi(U)$, even if allowed any finite number of calls to $U$ and $U^\\dagger$, and even if required to only approximate the desired operator $control_\\phi(U)$. Even further, there is no such \\emph{postselection} oracle algorithm, i.e. a unitary oracle algorithm followed by a binary success/fail measurement, that reports success and implements $control_\\phi(U)$ with a nonzero probability for each $U\\in U(d)$. Our proof relies on topological arguments which can be viewed as a modification of the Borsuk-Ulam theorem. Combining the topological arguments with the algorithm of Dong et al. in fact leads to an interesting dichotomy: implementing $control_\\phi(U^m)$ in our model is possible if and only if the integer $m$ is a multiple of the oracle's dimension $d$. Our impossibility no longer holds if the model is relaxed, either by dropping the worst-case requirement that the algorithm works for all $U\\in U(d)$, or, remarkably, by allowing measurements more general than a binary postselection measurement. We observe that for both relaxations, inefficient algorithms exist, and it remains open whether efficient ones do.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-11-19T18:52:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "implementing controlled unknown unitaries",
      "topological obstructions",
      "unitary oracle algorithm",
      "binary success/fail measurement",
      "topological arguments"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}