Physics – Quantum Physics
Scientific paper
2007-09-13
Physics
Quantum Physics
19 pages, no figure, minor error fixed
Scientific paper
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.
Beigi Salman
Shor Peter W.
No associations
LandOfFree
On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-215112