Quantum Kolmogorov komplexitet och kvantkorrelationer i deterministisk kontroll kvant Turing maskiner

Quantum Kolmogorov komplexitet och kvantkorrelationer i deterministisk kontroll kvant Turing maskiner

Tidsstämpel: 18 januari 2024 6:07
Källnod: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunković1,2och 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

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Detta arbete presenterar en studie av Kolmogorovs komplexitet för allmänna kvanttillstånd ur perspektivet av deterministisk-kontrollkvantturingmaskiner (dcq-TM). Vi utökar dcq-TM-modellen till att inkludera blandade tillståndsingångar och utgångar, och definierar dcq-beräknade tillstånd som de som kan approximeras av en dcq-TM. Dessutom introducerar vi (villkorad) Kolmogorov-komplexitet av kvanttillstånd och använder den för att studera tre särskilda aspekter av den algoritmiska informationen som finns i ett kvanttillstånd: en jämförelse av informationen i ett kvanttillstånd med den för dess klassiska representation som en uppsättning av verkliga siffror, en utforskning av gränserna för kopiering av kvanttillstånd i samband med algoritmisk komplexitet, och studie av komplexiteten hos korrelationer i kvantsystem, vilket resulterar i en korrelationsmedveten definition för algoritmisk ömsesidig information som tillfredsställer symmetri av informationsegenskap.

► BibTeX-data

► Referenser

[1] L. Antunes, A. Matos, A. Pinto, A. Souto och A. Teixeira. Envägsfunktioner med hjälp av algoritmiska och klassiska informationsteorier. 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, AM Rodrigues, H. Canhão, AM Carvalho och A. Souto. Zgli: En pipeline för klustring genom kompression med applicering på patientstratifiering vid spondyloartrit. Sensorer, 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 och A. Szkoła. Entropi och kvant Kolmogorovs komplexitet: En kvant Brudnos sats. Commun. Matematik. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett och G. Brassard. Kvantkryptografi: Offentlig nyckeldistribution och myntkastning. I Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, sidan 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

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

[6] A. Berthiaume, W. Dam och S. Laplante. Quantum Kolmogorov komplexitet. 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. Om längden på program för beräkning av ändliga binära sekvenser. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Kvantteorin, Church-Turing-principen och den universella kvantdatorn. 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. Kvantalgoritmisk entropi. 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 och Paul Vitányi. Algoritmisk informationsteori, sidorna 289–325. E, januari 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki och Karol Horodecki. Kvantsammanflätning. Recensioner av modern fysik, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Tre tillvägagångssätt för den kvantitativa definitionen av information. Problems of Information Transmission, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee och A. Romashchenko. Resursavgränsad symmetri av information som återbesöks. Teoretisk datavetenskap, 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 och Paul MB Vitányi. En introduktion till Kolmogorovs komplexitet och dess tillämpningar, 4:e upplagan. Texter i datavetenskap. 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 och Sandu Popescu. Det stoppande problemet för kvantdatorer. arXiv preprint quant-ph/​9806054, 1998. 10.48550/​arXiv.quant-ph/​9806054.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9806054
arXiv: kvant-ph / 9806054

[16] P. Mateus, A. Sernadas och A. Souto. Universalitet av quantum Turing-maskiner med deterministisk kontroll. 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 komplexitet och information-störning teorem. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera och H. Imai. Quantum Kolmogorov komplexitet och kvantnyckelfördelning. Phys. Rev. A, 79: 012324, jan 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera och Masanori Ohya. På att stoppa processen för kvantturningsmaskin. 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 och Vlatko Vedral. Den klassiska kvantgränsen för korrelationer: Discord och relaterade mått. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora och H. Briegel. Algoritmisk komplexitet och intrassling av kvanttillstånd. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel och B. Kraus. Quantum Kolmogorov komplexitet och dess tillämpningar. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Quantum Kolmogorov komplexitet och kvant Turing maskinen. 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. Starkt universella kvant Turing-maskiner och invarians av Kolmogorovs komplexitet. 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 en universell kvantdator vara helt kvant? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen och I. Chuang. Kvantberäkning och kvantinformation. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] En Rastegin. En nedre gräns för det relativa felet för kloning i blandade tillstånd och relaterade operationer. 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 och K. Bertels. Uppskattning av algoritmisk information med hjälp av kvantberäkning för genomiktillämpningar. Applied Sciences, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. En matematisk teori om 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. En formell teori om induktiv slutledning, del 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 och A. Teixeira. Vittne gömmer sig utan extraktorer eller simulatorer. I F. Manea, R. Miller och D. Nowotka, redaktörer, Sailing Routes in the World of Computation, sidorna 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. Kvantalgoritmisk informationsteori. Journal of Universal Computer Science, 2 (5): 311–346, maj 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto och Luís Antunes. Entropimått kontra Kolmogorovs komplexitet. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Quantum Kolmogorov komplexitet baserad på klassiska beskrivningar. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Tre tillvägagångssätt för den kvantitativa definitionen av information i ett individuellt rent kvanttillstånd. I Proceedings 15th Annual IEEE Conference on Computational Complexity, sidorna 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin och LA Levin. Komplexiteten hos ändliga objekt och utvecklingen av begreppen information och slumpmässighet med hjälp av teorin om algoritmer. Russian Mathematical Surveys, 25 (6): 83, dec 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Citerad av

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

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-01-18 23:13:56). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2024-01-18 23:13:55).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal