Two Simple Proofs of Müller's Theorem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910510598848512 |
|---|---|
| author | Epstein, Samuel |
| author_facet | Epstein, Samuel |
| contents | Due to Müller's theorem, the Kolmogorov complexity of a string was shown to be equal to its quantum Kolmogorov complexity. Thus there are no benefits to using quantum mechanics to compress classical information. The quantitative amount of information in classical sources is invariant to the physical model used. These consequences make this theorem arguably the most important result in the intersection of algorithmic information theory and physics. The original proof is quite extensive. This paper contains two simple proofs of this theorem. This paper also contains new bounds for quantum Kolmogorov complexity with error. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05328 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two Simple Proofs of Müller's Theorem Epstein, Samuel Computational Complexity Quantum Physics Due to Müller's theorem, the Kolmogorov complexity of a string was shown to be equal to its quantum Kolmogorov complexity. Thus there are no benefits to using quantum mechanics to compress classical information. The quantitative amount of information in classical sources is invariant to the physical model used. These consequences make this theorem arguably the most important result in the intersection of algorithmic information theory and physics. The original proof is quite extensive. This paper contains two simple proofs of this theorem. This paper also contains new bounds for quantum Kolmogorov complexity with error. |
| title | Two Simple Proofs of Müller's Theorem |
| topic | Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2402.05328 |