Kvante Kolmogorov kompleksitet og kvante korrelasjoner i deterministisk-kontroll kvante Turing maskiner

Kvante Kolmogorov kompleksitet og kvante korrelasjoner i deterministisk-kontroll kvante Turing maskiner

Tidsstempel: 18. januar 2024 6:07
Kilde node: 3070552

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

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Dette arbeidet presenterer en studie av Kolmogorovs kompleksitet for generelle kvantetilstander fra perspektivet til deterministisk-kontroll kvante Turing Machines (dcq-TM). Vi utvider dcq-TM-modellen til å inkludere innganger og utganger med blandede tilstander, og definerer dcq-beregnbare tilstander som de som kan tilnærmes med en dcq-TM. Dessuten introduserer vi (betinget) Kolmogorov-kompleksiteten til kvantetilstander og bruker den til å studere tre spesielle aspekter ved den algoritmiske informasjonen i en kvantetilstand: en sammenligning av informasjonen i en kvantetilstand med den av dens klassiske representasjon som en rekke reelle tall, en utforskning av grensene for kvantetilstandskopiering i sammenheng med algoritmisk kompleksitet, og studie av kompleksiteten til korrelasjoner i kvantesystemer, noe som resulterer i en korrelasjonsbevisst definisjon for algoritmisk gjensidig informasjon som tilfredsstiller symmetri av informasjonsegenskap.

► BibTeX-data

► Referanser

[1] L. Antunes, A. Matos, A. Pinto, A. Souto og A. Teixeira. Enveisfunksjoner ved bruk av algoritmiske og klassiske informasjonsteorier. 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 og A. Souto. Zgli: En rørledning for gruppering ved kompresjon med påføring på pasientstratifisering ved spondyloartritt. 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 og A. Szkoła. Entropi og kvante Kolmogorov kompleksitet: En kvante Brudnos teorem. Commun. Matte. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett og G. Brassard. Kvantekryptografi: Offentlig nøkkeldistribusjon og myntkasting. I Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, side 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

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

[6] A. Berthiaume, W. Dam og S. Laplante. Quantum Kolmogorov kompleksitet. 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 lengden på programmer for å beregne endelige binære sekvenser. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Kvanteteori, Church-Turing-prinsippet og den universelle kvantedatamaskinen. 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. Kvantealgoritmisk 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 og Paul Vitányi. Algoritmisk informasjonsteori, side 289–325. E, januar 2008.
arxiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki og Karol Horodecki. Kvantforvikling. Anmeldelser av moderne fysikk, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Tre tilnærminger til den kvantitative definisjonen av informasjon. Problemer med informasjonsoverføring, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee og A. Romasjtsjenko. Ressursavgrenset symmetri av informasjon som besøkes på nytt. Teoretisk informatikk, 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 og Paul MB Vitányi. En introduksjon til Kolmogorovs kompleksitet og dens anvendelser, 4. utgave. Tekster i informatikk. 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 og Sandu Popescu. Det stoppende problemet for kvantedatamaskiner. 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 og A. Souto. Universaliteten til kvante 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 kompleksitet og informasjon-forstyrrelse teorem. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera og H. Imai. Kvante Kolmogorov kompleksitet og kvantenøkkeldistribusjon. Phys. Rev. A, 79: 012324, januar 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera og Masanori Ohya. Ved å stoppe prosessen med kvanteturmaskin. 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 og Vlatko Vedral. Den klassisk-kvantegrense for korrelasjoner: uenighet og relaterte mål. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora og H. Briegel. Algoritmisk kompleksitet og sammenfiltring av kvantetilstander. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel og B. Kraus. Quantum Kolmogorov kompleksitet og dens applikasjoner. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Quantum Kolmogorov kompleksitet og kvante Turing-maskinen. Ph.D. Avhandling, Technical University of Berlin, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Sterkt universelle kvante Turing-maskiner og invarians av Kolmogorov-kompleksitet. 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 kvantedatamaskin være fullstendig kvante? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen og I. Chuang. Kvanteberegning og kvanteinformasjon. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] En Rastegin. En nedre grense for den relative feilen ved kloning i blandet tilstand og relaterte operasjoner. 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 og K. Bertels. Estimering av algoritmisk informasjon ved bruk av kvanteberegning for genomikkapplikasjoner. 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 kommunikasjon. 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 inferens, del i. Informasjon og kontroll, 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 og A. Teixeira. Vitne gjemmer seg uten ekstraktorer eller simulatorer. I F. Manea, R. Miller og D. Nowotka, redaktører, Sailing Routes in the World of Computation, side 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. Kvantealgoritmisk informasjonsteori. 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 og Luís Antunes. Entropimål kontra Kolmogorov-kompleksitet. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Quantum Kolmogorov kompleksitet basert på klassiske beskrivelser. 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 tilnærminger til den kvantitative definisjonen av informasjon i en individuell ren kvantetilstand. I Proceedings 15th Annual IEEE Conference on Computational Complexity, side 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin og LA Levin. Kompleksiteten til endelige objekter og utviklingen av begrepene informasjon og tilfeldighet ved hjelp av teorien om algoritmer. Russian Mathematical Surveys, 25 (6): 83, des 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Sitert av

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

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2024-01-18 23:13:56). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2024-01-18 23:13:55).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal