REVIEW 3 cited by
On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 3 Pith papers
-
Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
Deciding if a classical-quantum channel can exactly preserve a single bit is QCMA-complete, with optimal witnesses characterized as computational basis states (minimum) and |+>, |-> states (maximum).
-
Sufficient conditions for additivity of the zero-error classical capacity of quantum channels
Sufficient conditions for multiplicativity of the independence number of noncommutative graphs, hence additivity of one-shot and asymptotic zero-error classical capacity.
-
The Shape of Information: Global Information Geometric Limits in Multi-task Quantum Systems
The Holevo information of a multi-task quantum system is bounded by K log(1 + √TrA/(2√K)), where A is a prior-weighted global quantum Fisher information matrix.
Discussion (0). Sign in to comment.