Quantum Kolmogorov-complexiteit en kwantumcorrelaties in kwantum Turing-machines met deterministische besturing

Quantum Kolmogorov-complexiteit en kwantumcorrelaties in kwantum Turing-machines met deterministische besturing

Tijdstempel: 18 januari 2024 6:07 uur
Bronknooppunt: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunkovic1,2 en 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

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

Dit werk presenteert een onderzoek naar de complexiteit van Kolmogorov voor algemene kwantumtoestanden vanuit het perspectief van kwantum Turing Machines met deterministische controle (dcq-TM). We breiden het dcq-TM-model uit om gemengde statusinvoer en -uitvoer op te nemen, en definiëren dcq-berekenbare toestanden als die welke kunnen worden benaderd door een dcq-TM. Bovendien introduceren we de (voorwaardelijke) Kolmogorov-complexiteit van kwantumtoestanden en gebruiken we deze om drie specifieke aspecten van de algoritmische informatie in een kwantumtoestand te bestuderen: een vergelijking van de informatie in een kwantumtoestand met die van de klassieke representatie ervan als een reeks reële getallen, een verkenning van de grenzen van het kopiëren van kwantumtoestanden in de context van algoritmische complexiteit, en onderzoek naar de complexiteit van correlaties in kwantumsystemen, resulterend in een correlatiebewuste definitie voor algoritmische wederzijdse informatie die voldoet aan de symmetrie van informatie-eigenschap.

► BibTeX-gegevens

► Referenties

[1] L. Antunes, A. Matos, A. Pinto, A. Souto en A. Teixeira. Eenrichtingsfuncties met behulp van algoritmische en klassieke informatietheorieën. Theory of Computing Systems, 52 (1): 162–178, januari 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 en A. Souto. Zgli: Een pijplijn voor clustering door compressie met toepassing op patiëntstratificatie bij spondyloartritis. 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 en A. Szkoła. Entropie en kwantum Kolmogorov-complexiteit: een kwantumstelling van Brudno. Gemeenschappelijk. Wiskunde. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett en G. Brassard. Kwantumcryptografie: verspreiding van openbare sleutels en het opgooien van munten. In Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pagina 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

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

[6] A. Berthiaume, W. Dam en S. Laplante. Kwantum Kolmogorov-complexiteit. 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. Over de lengte van programma's voor het berekenen van eindige binaire reeksen. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Duits. Kwantumtheorie, het Church-Turing-principe en de universele kwantumcomputer. 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. Gacs. Kwantum-algoritmische entropie. Journal of Physics A: Wiskundig en algemeen, 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 en Paul Vitányi. Algoritmische informatietheorie, pagina's 289–325. E, januari 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki en Karol Horodecki. Quantum verstrengeling. Recensies van moderne natuurkunde, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Drie benaderingen van de kwantitatieve definitie van informatie. Problemen met informatieoverdracht, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee en A. Romasjtsjenko. Resource-begrensde symmetrie van informatie opnieuw bekeken. Theoretische informatica, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Wiskundige grondslagen van computerwetenschappen 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li en Paul MB Vitányi. Een inleiding tot de complexiteit van Kolmogorov en haar toepassingen, 4e editie. Teksten in de informatica. 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 en Sandu Popescu. Het stopprobleem voor kwantumcomputers. arXiv voordruk 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 en A. Souto. Universaliteit van kwantum Turing-machines met deterministische controle. 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-complexiteit en informatieverstoringsstelling. Entropie, 13 (4): 778-789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera en H. Imai. Quantum Kolmogorov-complexiteit en kwantumsleutelverdeling. Fys. Rev. A, 79: 012324, januari 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera en Masanori Ohya. Over het stopzetten van het kwantumturing-proces. 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 en Vlatko Vedral. De klassiek-kwantumgrens voor correlaties: onenigheid en gerelateerde maatregelen. Recensies van moderne natuurkunde, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora en H. Briegel. Algoritmische complexiteit en verstrengeling van kwantumtoestanden. Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel en B. Kraus. Quantum Kolmogorov-complexiteit en zijn toepassingen. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Müller. Quantum Kolmogorov-complexiteit en de quantum Turing-machine. Ph.D. Thesis, Technische Universiteit van Berlijn, 2007. 10.48550/​arXiv.0712.4377.
https:/​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Muller. Sterk universele kwantum-Turing-machines en onveranderlijkheid van de Kolmogorov-complexiteit. 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. Kan een universele kwantumcomputer volledig kwantumcomputer zijn? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen en ik. Chuang. Kwantumcomputers en kwantuminformatie. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Een Rastegin. Een ondergrens voor de relatieve fout van klonen in gemengde toestanden en aanverwante bewerkingen. 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 en K. Bertels. Het schatten van algoritmische informatie met behulp van quantum computing voor genomics-toepassingen. Toegepaste Wetenschappen, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. Een wiskundige theorie van communicatie. 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. Een formele theorie van inductieve gevolgtrekking, deel i. Informatie en controle, 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 en A. Teixeira. Wees getuige van het verbergen zonder extractors of simulators. In F. Manea, R. Miller en D. Nowotka, redacteuren, Sailing Routes in the World of Computation, pagina's 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. Kwantumalgoritmische informatietheorie. Journal of Universal Computer Science, 2 (5): 311–346, mei 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto en Luís Antunes. Entropie meet versus Kolmogorov-complexiteit. Entropie, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Quantum Kolmogorov-complexiteit gebaseerd op klassieke beschrijvingen. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Drie benaderingen van de kwantitatieve definitie van informatie in een individuele zuivere kwantumtoestand. In Proceedings 15e jaarlijkse IEEE-conferentie over computationele complexiteit, pagina's 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin en LA Levin. De complexiteit van eindige objecten en de ontwikkeling van de concepten informatie en willekeur door middel van de theorie van algoritmen. Russian Mathematical Surveys, 25 (6): 83, december 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Geciteerd door

[1] Anne Broadbent, Martti Karvonen en Sébastien Lord, “Onkloonbaar kwantumadvies”, arXiv: 2309.05155, (2023).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2024-01-18 23:13:56). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2024-01-18 23:13:55).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Tijdstempel:

Meer van Quantum Journaal