Checking strict positivity of Kraus maps is NP-hard

DOI10.1016/J.IPL.2016.09.008MaRDI QIDQ344532zbMATHOpenAlexFDO

Authors Stéphane Gaubert, Zheng Qu

Publication date 23 November 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.1429

zbMATH Keywords

algorithmscomputational complexityanalysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Positive matrices and their generalizations; cones of matrices (15B48)

Abstract: Basic properties in Perron-Frobenius theory are strict positivity, primitivityand irreducibility. Whereas for nonnegative matrices, these properties are equivalent to elementary graph properties which can be checked in polynomial time, we show that for Kraus maps- the noncommutative generalization of stochastic matrices - checking strict positivity (whether the map sends the cone to its interior) is NP-hard. The proof proceeds by reducing to the latter problem the existence of a non-zero solution of a special system of bilinear equations. The complexity of irreducibility and primitivity is also discussed in the noncommutative setting.

Recommendations

• The complexity of divisibility
• There are many more positive maps than completely positive maps
• Checking robust nonsingularity is NP-hard
• A Simple Proof of the Jamiołkowski Criterion for Complete Positivity of Linear Maps
• scientific article; zbMATH DE number 733109

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• A Quantum Version of Wielandt's Inequality
• Algebraic Perron-Frobenius theory
• Completely positive linear maps on complex matrices
• Convergence speed in distributed consensus and averaging
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Extensions of Jentzsch's Theorem
• Fundamentals of quantum information theory
• Geometric algorithms and combinatorial optimization.
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Hilbert's projective metric in quantum information theory
• Irreducible positive linear maps on operator algebras
• Most tensor problems are NP-hard
• Null space conditions and thresholds for rank minimization
• On the complexity of the generalized MinRank problem
• Periods of Connected Networks and Powers of Nonnegative Matrices
• Solving sparse rational linear systems
• Some observations on the spectra of positive operators on finite- dimensional C*-algebras
• Sparse Approximate Solutions to Linear Systems
• Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
• Spectral Properties of Positive Maps on C^* -Algebras
• Stable sets and polynomials
• States, effects, and operations. Fundamental notions of quantum theory. Lectures in mathematical physics at the University of Texas at Austin. Ed. by A. Böhm, J. D. Dollard and W. H. Wootters
• The computational complexity of some problems of linear algebra
• The simplest proof of Burnside's theorem on matrix algebras

Cited in

(3)

• Strict positivity and D-majorization
• Positive contraction mappings for classical and quantum Schrödinger systems
• On characteristic forms of positive vector bundles, mixed discriminants, and pushforward identities

This page was built for publication: Checking strict positivity of Kraus maps is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344532)