Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunković1,2, and André Souto2,3,4

1Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
2Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
3Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal
4Departamento de Informática,Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM). We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM. Moreover, we introduce (conditional) Kolmogorov complexity of quantum states and use it to study three particular aspects of the algorithmic information contained in a quantum state: a comparison of the information in a quantum state with that of its classical representation as an array of real numbers, an exploration of the limits of quantum state copying in the context of algorithmic complexity, and study of the complexity of correlations in quantum systems, resulting in a correlation-aware definition for algorithmic mutual information that satisfies symmetry of information property.

► BibTeX data

► References

[1] L. Antunes, A. Matos, A. Pinto, A. Souto, and A. Teixeira. One-way functions using algorithmic and classical information theories. Theory of Computing Systems, 52 (1): 162–178, Jan 2013. ISSN 1433-0490. 10.1007/​s00224-012-9418-z.

[2] D. Azevedo, A. M. Rodrigues, H. Canhão, A. M. Carvalho, and A. Souto. Zgli: A pipeline for clustering by compression with application to patient stratification in spondyloarthritis. Sensors, 23 (3), 2023. ISSN 1424-8220. 10.3390/​s23031219.

[3] F. Benatti, T. Krüger, M. Müller, R. Siegmund-Schultze, and A. Szkoła. Entropy and quantum Kolmogorov complexity: A quantum Brudno’s theorem. Commun. Math. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.

[4] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, page 175, 1984. 10.1016/​j.tcs.2014.05.025.

[5] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.

[6] A. Berthiaume, W. Dam, and S. Laplante. Quantum Kolmogorov complexity. Journal of Computer and System Sciences, 63 (2): 201–221, 2001. 10.1006/​jcss.2001.1765.

[7] G. Chaitin. On the length of programs for computing finite binary sequences. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.

[8] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Royal Society of London Proceedings Series A, 400 (1818): 97–117, 1985. 10.1098/​rspa.1985.0070.

[9] P. Gács. Quantum algorithmic entropy. Journal of Physics A: Mathematical and General, 34 (35): 6859, 2001. 10.1088/​0305-4470/​34/​35/​312.

[10] Peter Grünwald and Paul Vitányi. Algorithmic Information Theory, pages 289–325. E, January 2008.

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of modern physics, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.

[12] A. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1 (1), 1965. 10.1080/​00207166808803030.

[13] T. Lee and A. Romashchenko. Resource bounded symmetry of information revisited. Theoretical Computer Science, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Mathematical Foundations of Computer Science 2004.

[14] Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer, 2019. ISBN 978-3-030-11297-4. 10.1007/​978-3-030-11298-1.

[15] Noah Linden and Sandu Popescu. The halting problem for quantum computers. arXiv preprint quant-ph/​9806054, 1998. 10.48550/​arXiv.quant-ph/​9806054.

[16] P. Mateus, A. Sernadas, and A. Souto. Universality of quantum Turing machines with deterministic control. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.

[17] T. Miyadera. Quantum Kolmogorov complexity and information-disturbance theorem. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.

[18] T. Miyadera and H. Imai. Quantum Kolmogorov complexity and quantum key distribution. Phys. Rev. A, 79: 012324, Jan 2009. 10.1103/​PhysRevA.79.012324.

[19] Takayuki Miyadera and Masanori Ohya. On halting process of quantum turing machine. Open Systems & Information Dynamics, 12 (3): 261–264, 2005. 10.1007/​s11080-005-0923-2.

[20] Kavan Modi, Aharon Brodutch, Hugo Cable, Tomasz Paterek, and Vlatko Vedral. The classical-quantum boundary for correlations: Discord and related measures. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.

[21] C. Mora and H. Briegel. Algorithmic complexity and entanglement of quantum states. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.

[22] C. Mora, H. Briegel, and B. Kraus. Quantum Kolmogorov complexity and its applications. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.

[23] M Muller. Quantum Kolmogorov complexity and the quantum Turing machine. Ph.D. Thesis, Technical University of Berlin, 2007. 10.48550/​arXiv.0712.4377.

[24] M. Müller. Strongly universal quantum Turing machines and invariance of Kolmogorov complexity. IEEE Transactions on Information Theory, 54 (2): 763–780, 2008. ISSN 0018-9448. 10.1109/​TIT.2007.913263.

[25] John M Myers. Can a universal quantum computer be fully quantum? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.

[26] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.

[27] A Rastegin. A lower bound on the relative error of mixed-state cloning and related operations. Journal of Optics B: Quantum and Semiclassical Optics, 5 (6): S647, 2003. 10.1088/​1464-4266/​5/​6/​017.

[28] A. Sarkar, Z. Al-Ars, and K. Bertels. Estimating algorithmic information using quantum computing for genomics applications. Applied Sciences, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.

[29] Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27 (3): 379–423, 7 1948. 10.1002/​j.1538-7305.1948.tb01338.x.

[30] R. Solomonoff. A formal theory of inductive inference, part i. Information and Control, 7 (1), 1964. 10.1016/​S0019-9958(64)90223-2.

[31] A. Souto, L. Antunes, P. Mateus, and A. Teixeira. Witness hiding without extractors or simulators. In F. Manea, R. Miller, and D. Nowotka, editors, Sailing Routes in the World of Computation, pages 397–409, Cham, 2018. Springer International Publishing. 10.1007/​978-3-319-94418-0_40.

[32] K. Svozil. Quantum algorithmic information theory. Journal of Universal Computer Science, 2 (5): 311–346, may 1996. 10.3217/​jucs-002-05-0311.

[33] Andreia Teixeira, Armando Matos, André Souto, and Luís Antunes. Entropy measures vs. Kolmogorov complexity. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.

[34] P. Vitányi. Quantum Kolmogorov complexity based on classical descriptions. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.

[35] Paul Vitanyi. Three approaches to the quantitative definition of information in an individual pure quantum state. In Proceedings 15th Annual IEEE Conference on Computational Complexity, pages 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.

[36] A K Zvonkin and L A Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25 (6): 83, dec 1970. 10.1070/​RM1970v025n06ABEH001269.

Cited by

[1] Anne Broadbent, Martti Karvonen, and Sébastien Lord, "Uncloneable Quantum Advice", arXiv:2309.05155, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-26 21:07:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-26 21:07:50).