Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem

Adleman L.M., Demarrais J., Huang M.A. (1997) Quantum Computability. SIAM J. Comput. 26, 1524–1540 Alekseev V.M., Yakobson M.V. (1981) “Symbolic Dynamics and Hyperbolic Dynamic Systems”. Phys. Rep. 75, 287 Alicki R., Narnhofer H. (1995) “Comparison of dynamical entropies for the noncommutative shifts”. Lett. Math. Phys. 33, 241–247 Bernstein E., Vazirani U. (1997) “Quantum Complexity Theory”. SIAM J. Comput. 26, 1411–1473 Berthiaume A., Van Dam W., Laplante S. (2001) “Quantum Kolmogorov complexity”. J. Comput., System Sci. 63, 201–221 Billingsley P. (1965) “Ergodic Theory and Information”. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York Bjelaković I., Krüger T., Siegmund-Schultze Ra., Szkoła A. (2004) “The Shannon- McMillan theorem for ergodic quantum lattice systems”. Invent. Math. 155, 203–222 Bjelaković, I., Krüger, T., Siegmund-Schultze, Ra., Szkoła, A. “Chained Typical Subspaces- a Quantum Version of Breiman’s Theorem”. http://arxiv.org/list/quant-ph/0301177, 2003 Bjelaković I., Szkoła A. (2005) “The Data Compression Theorem for Ergodic Quantum Information Sources”. Quant. Inform. Proc. 4(1): 49–63 Brudno A.A. (1983) “Entropy and the complexity of the trajectories of a dynamical system”. Trans. Moscow Math. Soc. 2, 127–151 Chaitin G.J. (1966) “On the Length of Programs for Computing Binary Sequences”. J. Assoc. Comp. Mach. 13, 547–569 Cover T.M., Thomas J.A. (1991) “Elements of Information Theory”. Wiley Series in Telecommunications. John Wiley & Sons, New York Deutsch D. (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A400, 97–117 Feynman R. (1982) Simulating physics with computers. Int. J. Theor. Phys. 21, 467–488 Gács P. (2001) “Quantum algorithmic entropy”. J. Phys. A: Math. Gen. 34, 6859–6880 Gruska J. (1999) “Quantum Computing”. McGraw–Hill, London Hiai F., Petz D. (1991) “The Proper Formula for Relative Entropy and its Asymptotics in Quantum Probability”. Commun. Math. Phys. 143, 99–114 Holevo A.S. (2001) “Statistical Structure of Quantum Theory”. Springer Lecture Notes 67, Springer, Berlin Heidelberg New York Jozsa R., Schumacher B. (1994) “A new proof of the quantum noiseless coding theorem”. J. Mod. Optics 41, 2343–2349 Jozsa R., Horodecki M., Horodecki P., Horodecki R. (1998) “Universal Quantum Information Compression”. Phys. Rev. Lett. 81, 1714–1717 Kaltchenko A., Yang E.H. (2003) “Universal compression of ergodic quantum sources”. Quantum Information and Computation 3(4): 359–375 Keller, G. “Wahrscheinlichkeitstheorie”. Lecture Notes, Universität Erlangen-Nürnberg, 2003 Kieffer J. (1978) “A unified approach to weak universal source coding”. IEEE Trans. Inform. Theory 24(6): 674–682 Kolmogorov A.N. (1965) Three Approaches to the Quantitative Definition on Information. Prob. Inf. Trans. 1, 4–7 Kolmogorov A.N. (1968) “Logical Basis for Information Theory and Probability Theory”. IEEE Trans. Inform. Theory 14, 662–664 Li M., Vitanyi P. (1997) “An Introduction to Kolmogorov Complexity and Its Applications”. Springer Verlag, Berlin-Heidelberg-New York Mora, C., Briegel, H.J. “Algorithmic complexity of quantum states”. http://arxiv.org/list/quant-ph/0412172, 2004 Mora, C., Briegel, H.J. “Algorithmic complexity and entanglement of quantum states”. http://arxiv.org/list/quant-ph/0505200, 2005 Nielsen M.A., Chuang I.L. (2000) “Quantum Computation and Quantum Information”. Cambridge University Press, Cambridge Ozawa M., Nishumura H. (2000) “Local Transition Functions of Quantum Turing Machines”. Theoret. Informatics and Appl. 34, 379–402 Paulsen V. (2002) “Completely Bounded Maps and Operator Algebras”. Cambridge Studies in Advanced Mathematics 78, Cambridge Univ. Press, Cambridge Perdrix, S., Jorrand, P. “Measurement-Based Quantum Turing Machines and their Universality”. http: arxiv.org/list/quant-ph/0404146, 2004 Petz D., Mosonyi M. (2001) “Stationary quantum source coding”. J. Math. Phys. 42, 4857–4864 Shor, P. “Algorithms for quantum computation: Discrete log and factoring”. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1994, pp. 124–134 Segre G. (2004) “Physical Complexity of Classical and Quantum Objects and Their Dynamical Evolution From an Information-Theoretic Viewpoint”. Int. J. Th. Phys. 43, 1371–1395 Solomonoff, R.J. “A Formal Theory of Inductive Inference”. Inform. Contr. 7, 1–22, 224–254 (1964) Sow D.M., Eleftheriadis A. (2003) “Complexity distortion theory”. IEEE Trans. Inform. Theory IT-49, 604–608 Svozil K. (1993) “Randomness and Undecidability in Physics”. World Scientific, Singapore Uspenskii V.A., Semenov A.L., Shen A.Kh. (1990) “Can an individual sequence of zeros and ones be random”. Usp. Mat. Nauk. 45/1, 105–162 Vitányi P. (2001) “Quantum Kolmogorov complexity based on classical descriptions”. IEEE Trans. Inform. Theory 47/6, 2464–2479 White H. (1993) “Algorithmic complexity of points in a dynamical system”. Erg. Th. Dyn. Sys. 13, 807 Ziv J. (1972) “Coding of sources with unknown statistics–I: Probability of encoding error”. IEEE Trans. Inform. Theory 18, 384–389 Zvonkin A.K., Levin L.A. (1970) “The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms”. Russ. Math. Surv. 25(6): 83–124