The complexity of divisibility
From MaRDI portal
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)
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.
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
Cites work
- scientific article; zbMATH DE number 4051615 (Why is no real title available?)
- scientific article; zbMATH DE number 3651468 (Why is no real title available?)
- scientific article; zbMATH DE number 193132 (Why is no real title available?)
- scientific article; zbMATH DE number 3624599 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3997615 (Why is no real title available?)
- scientific article; zbMATH DE number 3417832 (Why is no real title available?)
- Completely positive dynamical semigroups of \(N\)-level systems
- Completely positive linear maps on complex matrices
- Computing real square roots of a real matrix
- Dividing quantum channels
- Geometry of Quantum States
- On \(p\)th roots of stochastic matrices
- On the generators of quantum dynamical semigroups
- On the infinite divisbility of the Pareto distribution
- On the infinite divisibility of the lognormal distribution
- Practical polynomial factoring in polynomial time
- Quantum Subdivision Capacities and Continuous-Time Quantum Coding
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
- The complexity of relating quantum channels to master equations
- The imbedding problem for finite Markov chains
- The nonnegative inverse eigenvalue problem.
- Über eine Eigenschaft der normalen Verteilungsfunktion
Cited in
(9)- Diffusion and consensus on weakly connected directed graphs
- Pauli semigroups and unistochastic quantum channels
- scientific article; zbMATH DE number 7315090 (Why is no real title available?)
- 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)
