The complexity of divisibility
From MaRDI portal
Stochastic matrices (15B51) Probability distributions: general theory (60E05) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
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
- scientific article; zbMATH DE number 4175058
- scientific article; zbMATH DE number 3221561
- scientific article; zbMATH DE number 3219076
- Complexity questions in number theory
Cites work
- 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
- 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?)
- 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)- Roots of completely positive maps
- Pauli semigroups and unistochastic quantum channels
- Diffusion and consensus on weakly connected directed graphs
- Checking strict positivity of Kraus maps is NP-hard
- scientific article; zbMATH DE number 7315090 (Why is no real title available?)
- Necessary criteria for Markovian divisibility of linear maps
- Log-convex set of Lindblad semigroups acting on N-level system
- Quantum and classical dynamical semigroups of superchannels and semicausal channels
- Embeddability of real and positive operators
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)
