Are problems in Quantum Information Theory (un)decidable?
arXiv:1111.5425
Abstract
This note is intended to foster a discussion about the extent to which typical problems arising in quantum information theory are algorithmically decidable (in principle rather than in practice). Various problems in the context of entanglement theory and quantum channels turn out to be decidable via quantifier elimination as long as they admit a compact formulation without quantification over integers. For many asymptotically defined properties which have to hold for all or for one integer N, however, effective procedures seem to be difficult if not impossible to find. We review some of the main tools for (dis)proving decidability and apply them to problems in quantum information theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a two-qubit singlet state?" easily become undecidable. A closer look at such questions might rule out some of the "single-letter" formulas sought in quantum information theory.
11 pages
References in corpus (6)
- Bounding the set of quantum correlations
- Quantum Communication With Zero-Capacity Channels
- Connes' embedding problem and Tsirelson's problem
- Maximal violation of the I3322 inequality using infinite dimensional quantum systems
- Super-Activation of Zero-Error Capacity of Noisy Quantum Channels
- Quantum measurement occurrence is undecidable
Cited by in corpus (12)
- Undecidability of the Spectral Gap (short version)
- Tensor Network Contractions for #SAT
- Undecidability in Tensor Network States
- Undecidability of the Spectral Gap (full version)
- Halos and undecidability of tensor stable positive maps
- Universality and Optimality in the Information-Disturbance Tradeoff
- Algorithmic complexity of quantum capacity
- Quantum realism and quantum surrealism
- Second Law of Entanglement Dynamics for the Non-Asymptotic Regime
- Transcendental properties of entropy-constrained sets: Part II
- A Note on Quantum Markov Models
- A constructive proof of Tarski's theorem on quantifier elimination in the theory of ACF