On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels
| dc.creator | Beigi, Salman | |
| dc.creator | Shor, Peter W. | |
| dc.date | 2007-09-13 | |
| dc.date | 2008-10-13 | |
| dc.date.accessioned | 2026-07-07T10:08:56Z | |
| dc.date.available | 2026-07-07T10:08:56Z | |
| dc.description | 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. | |
| dc.description | 19 pages, no figure, minor error fixed | |
| dc.identifier | https://arxiv.org/abs/0709.2090 | |
| dc.identifier | http://arxiv.org/abs/0709.2090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/171169 | |
| dc.subject | Quantum Physics | |
| dc.title | On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels | |
| dc.type | text |