Quanten-Kolmogorov-Komplexität und Quantenkorrelationen in Quanten-Turing-Maschinen mit deterministischer Steuerung

Quanten-Kolmogorov-Komplexität und Quantenkorrelationen in Quanten-Turing-Maschinen mit deterministischer Steuerung

Zeitstempel: 18. Januar 2024, 6:07 Uhr
Quellknoten: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paul Mateus1,2, Nikola Paunkovic1,2 und André Souto2,3,4

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

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Diese Arbeit präsentiert eine Studie der Kolmogorov-Komplexität für allgemeine Quantenzustände aus der Perspektive deterministisch gesteuerter Quanten-Turing-Maschinen (dcq-TM). Wir erweitern das dcq-TM-Modell um Ein- und Ausgänge mit gemischten Zuständen und definieren durch dcq berechenbare Zustände als solche, die durch ein dcq-TM angenähert werden können. Darüber hinaus führen wir die (bedingte) Kolmogorov-Komplexität von Quantenzuständen ein und verwenden sie, um drei besondere Aspekte der in einem Quantenzustand enthaltenen algorithmischen Informationen zu untersuchen: einen Vergleich der Informationen in einem Quantenzustand mit der seiner klassischen Darstellung als Array realer Zahlen, eine Untersuchung der Grenzen des Quantenzustandskopierens im Kontext algorithmischer Komplexität und eine Untersuchung der Komplexität von Korrelationen in Quantensystemen, was zu einer korrelationsbewussten Definition für algorithmische gegenseitige Information führt, die die Symmetrie der Informationseigenschaft erfüllt.

► BibTeX-Daten

► Referenzen

[1] L. Antunes, A. Matos, A. Pinto, A. Souto und A. Teixeira. Einwegfunktionen unter Verwendung algorithmischer und klassischer Informationstheorien. Theory of Computing Systems, 52 (1): 162–178, Januar 2013. ISSN 1433-0490. 10.1007/​s00224-012-9418-z.
https: / / doi.org/ 10.1007 / s00224-012-9418-z

[2] D. Azevedo, AM Rodrigues, H. Canhão, AM Carvalho und A. Souto. Zgli: Eine Pipeline für Clustering durch Kompression mit Anwendung auf die Patientenstratifizierung bei Spondyloarthritis. Sensoren, 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 und A. Szkoła. Entropie und Quantenkomplexität von Kolmogorov: Ein Quantensatz von Brudno. Komm. Mathematik. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett und G. Brassard. Quantenkryptographie: Verteilung öffentlicher Schlüssel und Münzwurf. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, Seite 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[5] E. Bernstein und U. Vazirani. Quantenkomplexitätstheorie. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[6] A. Berthiaume, W. Dam und S. Laplante. Quanten-Kolmogorov-Komplexität. 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. Über die Länge von Programmen zur Berechnung endlicher Binärfolgen. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Quantentheorie, das Church-Turing-Prinzip und der universelle Quantencomputer. 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. Quantenalgorithmische Entropie. 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 und Paul Vitányi. Algorithmische Informationstheorie, Seiten 289–325. E, Januar 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki und Karol Horodecki. Quantenverschränkung. Reviews of Modern physics, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Drei Ansätze zur quantitativen Definition von Informationen. Problems of Information Transmission, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee und A. Romashchenko. Ressourcenbeschränkte Informationssymmetrie überarbeitet. Theoretische Informatik, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Mathematische Grundlagen der Informatik 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li und Paul MB Vitányi. Eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen, 4. Auflage. Texte in der Informatik. 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 und Sandu Popescu. Das Halteproblem für Quantencomputer. 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 und A. Souto. Universalität von Quanten-Turing-Maschinen mit deterministischer Steuerung. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Quanten-Kolmogorov-Komplexitäts- und Informationsstörungssatz. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera und H. Imai. Quanten-Kolmogorov-Komplexität und Quantenschlüsselverteilung. Physik. Rev. A, 79: 012324, Januar 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera und Masanori Ohya. Über den Stoppprozess einer Quantenturingmaschine. 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 und Vlatko Vedral. Die klassische Quantengrenze für Korrelationen: Zwietracht und verwandte Maße. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora und H. Briegel. Algorithmische Komplexität und Verschränkung von Quantenzuständen. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https://doi.org/ 10.1103/PhysRevLett.95.200503

[22] C. Mora, H. Briegel und B. Kraus. Quantenkolmogorov-Komplexität und ihre Anwendungen. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Müller. Quanten-Kolmogorov-Komplexität und die Quanten-Turing-Maschine. Ph.D. Diplomarbeit, Technische Universität Berlin, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Stark universelle Quanten-Turing-Maschinen und Invarianz der Kolmogorov-Komplexität. 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. Kann ein universeller Quantencomputer vollständig quantenbasiert sein? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https://doi.org/ 10.1103/PhysRevLett.78.1823

[26] M. Nielsen und I. Chuang. Quantenberechnung und Quanteninformation. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Ein Rastegin. Eine Untergrenze für den relativen Fehler des Mixed-State-Klonens und verwandter Vorgänge. 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 und K. Bertels. Schätzung algorithmischer Informationen mithilfe von Quantencomputern für Genomikanwendungen. Angewandte Wissenschaften, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. Eine mathematische Theorie der Kommunikation. 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. Eine formale Theorie der induktiven Folgerung, Teil 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 und A. Teixeira. Zeugenversteck ohne Extraktoren oder Simulatoren. In F. Manea, R. Miller und D. Nowotka, Herausgeber, Sailing Routes in the World of Computation, Seiten 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. Quantenalgorithmische Informationstheorie. Journal of Universal Computer Science, 2 (5): 311–346, Mai 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto und Luís Antunes. Entropiemaße vs. Kolmogorov-Komplexität. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Quantenkolmogorov-Komplexität basierend auf klassischen Beschreibungen. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Drei Ansätze zur quantitativen Definition von Information in einem einzelnen reinen Quantenzustand. In Proceedings 15th Annual IEEE Conference on Computational Complexity, Seiten 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin und LA Levin. Die Komplexität endlicher Objekte und die Entwicklung der Konzepte von Information und Zufälligkeit mittels der Theorie der Algorithmen. Russian Mathematical Surveys, 25 (6): 83, Dezember 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Zitiert von

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

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2024, 01:18:23 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2024-01-18 23:13:55).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal