Checking strict positivity of Kraus maps is NP-hard

DOI10.1016/J.IPL.2016.09.008zbMATH Open1392.68202arXiv1402.1429OpenAlexW2963100021MaRDI QIDQ344532FDOQ344532

Authors: Stéphane Gaubert, Zheng Qu 

Publication date: 23 November 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Most tensor problems are NP-hard
• Completely positive linear maps on complex matrices
• Geometric algorithms and combinatorial optimization.
• Stable sets and polynomials
• Hilbert's projective metric in quantum information theory
• Extensions of Jentzsch's Theorem
• Sparse Approximate Solutions to Linear Systems
• 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 simplest proof of Burnside's theorem on matrix algebras
• Fundamentals of quantum information theory
• Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
• A Quantum Version of Wielandt's Inequality
• Spectral Properties of Positive Maps on C^* -Algebras
• Some observations on the spectra of positive operators on finite- dimensional C*-algebras
• Algebraic Perron-Frobenius theory
• The computational complexity of some problems of linear algebra
• Solving sparse rational linear systems
• Extending robustness and randomization from consensus to symmetrization algorithms
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Irreducible positive linear maps on operator algebras
• On the complexity of the generalized MinRank problem
• Periods of Connected Networks and Powers of Nonnegative Matrices
• Convergence speed in distributed consensus and averaging
• Null space conditions and thresholds for rank minimization

Cited In (3)

• Positive contraction mappings for classical and quantum Schrödinger systems
• Strict positivity and D-majorization
• 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)