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.
On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels
1 Pith paper cite this work, alongside 4 external citations. Polarity classification is still indexing.
1
Pith paper citing it
4
external citations · Pith
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.
fields
quant-ph 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
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.