Kvantna Kolmogorova kompleksnost in kvantne korelacije v kvantnih Turingovih strojih z determinističnim nadzorom

Kvantna Kolmogorova kompleksnost in kvantne korelacije v kvantnih Turingovih strojih z determinističnim nadzorom

Časovni žig: 18. januar 2024 6
Izvorno vozlišče: 3070552

Mariano Lemus1,2, Ricardo Faleiro1,2, Paulo Mateus1,2, Nikola Paunković1,2in André Souto2,3,4

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

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

To delo predstavlja študijo kompleksnosti Kolmogorova za splošna kvantna stanja z vidika kvantnih Turingovih strojev z determinističnim nadzorom (dcq-TM). Model dcq-TM razširimo tako, da vključuje vhode in izhode mešanih stanj, in definiramo stanja, ki jih je mogoče izračunati z dcq, kot tista, ki jih je mogoče približati z dcq-TM. Poleg tega uvedemo (pogojno) Kolmogorovsko kompleksnost kvantnih stanj in jo uporabimo za preučevanje treh posebnih vidikov algoritemskih informacij, vsebovanih v kvantnem stanju: primerjava informacije v kvantnem stanju z njeno klasično predstavitvijo kot nizom realnih števil, raziskovanje meja kopiranja kvantnega stanja v kontekstu algoritemske kompleksnosti in študij kompleksnosti korelacije v kvantnih sistemih, kar ima za posledico definicijo, ki se zaveda korelacije za algoritemske medsebojne informacije, ki izpolnjujejo simetrijo informacijske lastnosti.

► BibTeX podatki

► Reference

[1] L. Antunes, A. Matos, A. Pinto, A. Souto in A. Teixeira. Enosmerne funkcije z uporabo algoritemskih in klasičnih informacijskih teorij. 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 in A. Souto. Zgli: Cevovod za združevanje v skupine s stiskanjem z uporabo za stratifikacijo bolnikov pri spondiloartritisu. Senzorji, 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 in A. Szkoła. Entropija in kvantna Kolmogorova kompleksnost: kvantni Brudnov izrek. Komun. matematika Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett in G. Brassard. Kvantna kriptografija: distribucija javnih ključev in met kovancev. V zborniku mednarodnih konferenc IEEE o računalnikih, sistemih in obdelavi signalov, stran 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

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

[6] A. Berthiaume, W. Dam in S. Laplante. Kvantna Kolmogorova kompleksnost. 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. O dolžini programov za računanje končnih binarnih zaporedij. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Kvantna teorija, Church-Turingov princip in univerzalni kvantni računalnik. 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. Kvantna algoritemska entropija. 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 in Paul Vitányi. Algoritemska teorija informacij, strani 289–325. E, januar 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki in Karol Horodecki. Kvantno prepletanje. Recenzije sodobne fizike, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Trije pristopi k kvantitativni definiciji informacije. Problemi prenosa informacij, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee in A. Romashchenko. Ponovno obravnavana simetrija informacij, omejena z viri. Theoretical Computer Science, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Matematične osnove računalništva 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li in Paul MB Vitányi. Uvod v kompleksnost Kolmogorova in njene aplikacije, 4. izdaja. Besedila iz računalništva. 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 in Sandu Popescu. Problem zaustavitve za kvantne računalnike. arXiv prednatis 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 in A. Souto. Univerzalnost kvantnih Turingovih strojev z determinističnim krmiljenjem. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Kvantna Kolmogorova kompleksnost in izrek informacijske motnje. Entropija, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera in H. Imai. Kvantna Kolmogorova kompleksnost in kvantna porazdelitev ključev. Phys. Rev. A, 79: 012324, januar 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera in Masanori Ohya. O zaustavitvi procesa kvantnega turingovega stroja. 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 in Vlatko Vedral. Klasično-kvantna meja za korelacije: Discord in sorodne mere. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora in H. Briegel. Algoritemska kompleksnost in prepletenost kvantnih stanj. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel in B. Kraus. Kvantna Kolmogorova kompleksnost in njene aplikacije. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Kvantna Kolmogorova kompleksnost in kvantni Turingov stroj. dr. Diplomsko delo, Tehnična univerza v Berlinu, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Močno univerzalni kvantni Turingovi stroji in invariantnost Kolmogorove kompleksnosti. 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. Ali je lahko univerzalni kvantni računalnik popolnoma kvantni? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen in I. Chuang. Kvantno računanje in kvantne informacije. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Rastegin. Spodnja meja relativne napake kloniranja v mešanem stanju in sorodnih operacij. Journal of Optics B: Kvantna in semiklasična optika, 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 in K. Bertels. Ocenjevanje algoritemskih informacij z uporabo kvantnega računalništva za genomske aplikacije. Uporabne znanosti, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. Matematična teorija komunikacije. Tehnični časopis za sistem Bell, 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. Solomonov. Formalna teorija induktivnega sklepanja, I. del. Informacije in nadzor, 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 in A. Teixeira. Skrivanje prič brez ekstraktorjev ali simulatorjev. V F. Manea, R. Miller in D. Nowotka, uredniki, Sailing Routes in the World of Computation, strani 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. Kvantna algoritemska teorija informacij. 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 in Luís Antunes. Entropijske mere proti kompleksnosti Kolmogorova. Entropija, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Kvantna Kolmogorova kompleksnost na podlagi klasičnih opisov. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Trije pristopi h kvantitativni opredelitvi informacije v posameznem čistem kvantnem stanju. V zborniku 15. letne konference IEEE o računalniški kompleksnosti, strani 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin in LA Levin. Kompleksnost končnih objektov in razvoj konceptov informacije in naključnosti s pomočjo teorije algoritmov. Ruski matematični pregledi, 25 (6): 83, dec 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Navedel

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

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2024-01-18 23:13:56). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2024-01-18 23:13:55).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal