Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
<|reference_start|>Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem: In classical information theory, entropy rate and Kolmogorov complexity per symbol are related by a theorem of Brudno. In this paper, we prove a quantum version of this theorem, connecting the von Neumann entropy rate and two notions of quantum Kolmogorov complexity, both based on the shortest qubit descriptions of qubit strings that, run by a universal quantum Turing machine, reproduce them as outputs.<|reference_end|>
@article{benatti2005entropy,
    title={Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem},
    author={Fabio Benatti, Tyll Krueger, Markus Mueller, Rainer Siegmund-Schultze,
  Arleta Szkola},
    journal={Communications in Mathematical Physics, Vol. 265, No.2 / July
  2006, 437-461},
    year={2005},
    doi={10.1007/s00220-006-0027-z},
    archivePrefix={arXiv},
    eprint={quant-ph/0506080},
    primaryClass={quant-ph cs.IT math-ph math.DS math.IT math.MP}
}