Memory effects can make the transmission capability of a communication channel uncomputable
arXiv:1601.06101 · doi:10.1038/s41467-018-03428-0
Abstract
Most communication channels are subjected to noise. One of the goals of Information Theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels -information-stable finite state machine channels-, restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory.
arXiv commentImproved presentation and clarified claims
References in corpus (5)
- Unbounded number of channel uses are required to see quantum capacity
- Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel
- Superadditivity of private information for any number of uses of the channel
- On channels with positive quantum zero-error capacity having vanishing n-shot capacity
- Entanglement can completely defeat quantum noise
Cited by in corpus (7)
- Undecidability of the Spectral Gap in One Dimension
- Limitations of Deep Learning for Inverse Problems on Digital Hardware
- Resonant Multilevel Amplitude Damping Channels
- Undecidability of the Spectral Gap (full version)
- Undecidability in Physics: a Review
- Optimisation of time-ordered processes in the finite and asymptotic regime
- Undecidability of the spectral gap in rotationally symmetric Hamiltonians