Quantum Kolmogorov Complexity And Quantum Correlations In Deterministic-control Quantum Turing Machines

Mariano Lemus^1,2, Ricardo Faleiro^1,2, Paulo Mateus^1,2, Nikola Paunković^1,2, and André Souto^2,3,4

¹Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
²Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
³Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal
⁴Departamento 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.

Abstract

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

@article{Lemus2024quantumkolmogorov, doi = {10.22331/q-2024-01-18-1230}, url = {https://doi.org/10.22331/q-2024-01-18-1230}, title = {Quantum {K}olmogorov complexity and quantum correlations in deterministic-control quantum {T}uring machines}, author = {Lemus, Mariano and Faleiro, Ricardo and Mateus, Paulo and Paunkovi{‘{c}}, Nikola and Souto, Andr{‘{e}}}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1230}, month = jan, year = {2024}<br /> }

► 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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1088/0305-4470/34/35/312

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

[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1016/j.tcs.2005.07.017

[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.
https://doi.org/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.
https://doi.org/10.48550/arXiv.quant-ph/9806054
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevLett.78.1823

[26] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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-01-18 23:13:56). 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-01-18 23:13:55).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Generative Data Intelligence

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

Abstract

► BibTeX data

► References

Cited by

Skywise.ai Founder Chris McGinty is a 2024 IQT Quantum + AI Conference Speaker – Inside Quantum Technology

TRON Resumes Its Upward Trend, But Encounters A Barrier At $0.12

Latest Intelligence

Quantum News Briefs: April 27, 2024: News From Colorado Senator John Hickenlooper • Ethereum and quantum cybersecurity threats • Stock trends – Inside Quantum...

Mauritania Embarks on Digital Currency Project with G+D Amid Economic Modernization

Understanding the New IRS 1099-DA for Digital Asset Reporting

Cardano Stabilizes Above $0.46 As Bulls Stop The Slide

John Deaton Files Amicus Brief in Support of Coinbase’s Appeal Against SEC

Drake Threatened With Lawsuit Over Tupac AI Vocals

Chat with us