{
  "id": "0709.2090",
  "version": "v3",
  "published": "2007-09-13T14:46:45.000Z",
  "updated": "2008-10-13T16:31:19.000Z",
  "title": "On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels",
  "authors": [
    "Salman Beigi",
    "Peter W. Shor"
  ],
  "comment": "19 pages, no figure, minor error fixed",
  "categories": [
    "quant-ph"
  ],
  "abstract": "One of the main problems in quantum complexity theory is that our understanding of the theory of QMA-completeness is not as rich as its classical analogue, the NP- completeness. In this paper we consider the clique problem in graphs, which is NP- complete, and try to find its quantum analogue. We show that, quantum clique problem can be defined as follows; Given a quantum channel, decide whether there are k states that are distinguishable, with no error, after passing through channel. This definition comes from reconsidering the clique problem in terms of the zero-error capacity of graphs, and then redefining it in quantum information theory. We prove that, quantum clique problem is QMA-complete. In the second part of paper, we consider the same problem for the Holevo capacity. We prove that computing the Holevo capacity as well as the minimum entropy of a quantum channel is NP-complete. Also, we show these results hold even if the set of quantum channels is restricted to entanglement breaking ones.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2008-10-13T16:31:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum channel",
      "holevo capacity",
      "computing zero-error",
      "quantum clique problem",
      "quantum complexity theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0709.2090B"
    }
  }
}