Frankfurt 2006 – scientific programme
Parts | Days | Selection | Search | Downloads | Help
Q: Quantenoptik und Photonik
Q 40: Quanteninformation III
Q 40.3: Talk
Wednesday, March 15, 2006, 11:40–11:55, HI
Entropy and Quantum Kolmogorov Complexity: a Quantum Brudno’s Theorem — •Markus Müller1, Fabio Benatti2, Tyll Krüger1, Rainer Siegmund-Schultze1, and Arleta Szkola1 — 1Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften, Institut für Mathematik MA 7-2, Straße des 17. Juni 136, 10623 Berlin — 2University of Trieste, Department of Theoretical Physics, Strada Costiera, 11, 34014 Trieste, Italy
In classical information theory, entropy rate and Kolmogorov complexity per symbol are related by a theorem of Brudno. We prove a quantum version of this theorem, connecting the von Neumann entropy rate and two notions of quantum algorithmic complexity, both based on the shortest qubit descriptions of qubit strings that, run by a universal quantum Turing machine, reproduce them as outputs.