No algorithm can tell how much memory a repeated quantum channel needs
In plain wordsNo algorithm can tell, from an explicit description of a quantum channel, whether a device that applies it over and over, releasing each output at once and given only maximally mixed fresh qubits, needs memory that grows logarithmically or linearly with the number of uses.
The result
As the paper states it, in briefFor a device that applies a channel again and again with maximally mixed fresh qubits, the answer turns on one set of channels: inside it, channels with a flat probe can be served with memory that grows more slowly than the number of uses; outside it, a device with sublinear memory fails with probability tending to one.
Questionson the index
How this was checked
- Machine checks
- Scripts that check the listed statements of the paper; they do not replace the proofs.
- Lean
- None.
- Peer review
- Not yet.
Every check here is internal. How we check results.
Novelty and credit
- Novelty
- Extends named prior work: the static equivalence is Haagerup and Musat’s, and undecidability for quantum correlation sets is Slofstra’s and his coauthors’. New, in the paper’s words: the transfer to channels and its memory consequences.
Versionstwo, each with its own DOI
| Version | Date | DOI | Notes |
|---|---|---|---|
| 1.1.0 | 10.5281/zenodo.23204398 | PDF hosted here. | |
| 1.0.0 | 10.5281/zenodo.23199341 |
Paper, code and links
papers/no-algorithm-v1.1.0.pdf, version 1.1.0, 660,469 bytes.SHA-256 5e23e3033e847b286de9a29af542302d00610d0c33f1f60846d1980559c79777
- DOI
10.5281/zenodo.23204398; all versions 10.5281/zenodo.23199340
Corrections
None so far.
All corrections, and what counts as one.
Cite
@misc{douglas2026noalgorithm,
author = {Douglas, Seth and Mghirbi, Nidhal},
title = {No algorithm can tell how much memory a repeated quantum channel needs},
year = {2026},
version = {1.1.0},
doi = {10.5281/zenodo.23204398},
url = {https://doi.org/10.5281/zenodo.23204398}
}