The complexity of divisibility

DOI10.1016/J.LAA.2016.03.041zbMATH Open1381.68094arXiv1411.7380OpenAlexW1778086900WikidataQ33782819 ScholiaQ33782819MaRDI QIDQ286139FDOQ286139

Authors: Johannes Bausch, Toby Cubitt 

Publication date: 20 May 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We address two sets of long-standing open questions in probability theory, from a computational complexity perspective: divisibility of stochastic maps, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic maps is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic maps. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.

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

Recommendations

• scientific article; zbMATH DE number 799777
• scientific article; zbMATH DE number 1031238
• On the complexity of linear arithmetic with divisibility
• The complexity of Euler's integer partition theorem
• scientific article; zbMATH DE number 3143751
• scientific article; zbMATH DE number 512852
• Publication:3199512
• scientific article; zbMATH DE number 3221561
• scientific article; zbMATH DE number 3219076
• Complexity questions in number theory

zbMATH Keywords

complexity theorydecomposabilitystochastic matricesprobability distributionsdivisibility

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Stochastic matrices (15B51)

Cites Work

• Über eine Eigenschaft der normalen Verteilungsfunktion
• Title not available (Why is that?)
• Title not available (Why is that?)
• Completely positive linear maps on complex matrices
• On the generators of quantum dynamical semigroups
• Completely positive dynamical semigroups of \(N\)-level systems
• Geometry of Quantum States
• The nonnegative inverse eigenvalue problem.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(p\)th roots of stochastic matrices
• Quantum Subdivision Capacities and Continuous-Time Quantum Coding
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the infinite divisbility of the Pareto distribution
• On the infinite divisibility of the lognormal distribution
• Title not available (Why is that?)
• Practical polynomial factoring in polynomial time
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• The imbedding problem for finite Markov chains
• Computing real square roots of a real matrix
• The complexity of relating quantum channels to master equations
• Dividing quantum channels

Cited In (9)

• Diffusion and consensus on weakly connected directed graphs
• Pauli semigroups and unistochastic quantum channels
• Title not available (Why is that?)
• Necessary criteria for Markovian divisibility of linear maps
• Embeddability of real and positive operators
• Log-convex set of Lindblad semigroups acting on N-level system
• Checking strict positivity of Kraus maps is NP-hard
• Roots of completely positive maps
• Quantum and classical dynamical semigroups of superchannels and semicausal channels

This page was built for publication: The complexity of divisibility

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