# Checking the strict positivity of Kraus maps is NP-hard

1 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : Basic properties in Perron-Frobenius theory are positivity, primitivity, and irreducibility. Whereas these properties can be checked in polynomial time for stochastic matrices, we show that for Kraus maps - the noncommutative generalization of stochastic matrices - checking positivity is NP-hard. This is in contrast with irreducibility and primitivity, which we show to be checkable in strongly polynomial time for completely positive maps - the noncommutative generalization of nonpositive matrices. As an intermediate result, we get that the bilinear feasibility problem over $\mathbb{Q}$ is NP-hard.
Keywords :
Document type :
Journal articles
Domain :

https://hal.inria.fr/hal-01097942
Contributor : Stephane Gaubert <>
Submitted on : Monday, December 22, 2014 - 2:45:02 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:32 PM

### Citation

Stéphane Gaubert, Zheng Qu. Checking the strict positivity of Kraus maps is NP-hard. Information Processing Letters, Elsevier, 2017, 118, pp.35--43. ⟨10.1016/j.ipl.2016.09.008⟩. ⟨hal-01097942⟩

Record views