Complexitatea cuantică a lui Kolmogorov și corelațiile cuantice în mașinile Turing cuantice cu control determinist

Complexitatea cuantică a lui Kolmogorov și corelațiile cuantice în mașinile Turing cuantice cu control determinist

Marca temporală: 18 ianuarie 2024 6:07
Nodul sursă: 3070552

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

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

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Această lucrare prezintă un studiu al complexității Kolmogorov pentru stări cuantice generale din perspectiva mașinilor Turing cuantice cu control determinist (dcq-TM). Extindem modelul dcq-TM pentru a încorpora intrări și ieșiri cu stări mixte și definim stările dcq-calculabile ca acelea care pot fi aproximate printr-un dcq-TM. Mai mult, introducem complexitatea (condițională) Kolmogorov a stărilor cuantice și o folosim pentru a studia trei aspecte particulare ale informațiilor algoritmice conținute într-o stare cuantică: o comparație a informațiilor într-o stare cuantică cu cea a reprezentării sale clasice ca o matrice de informații reale. numere, o explorare a limitelor copierii stărilor cuantice în contextul complexității algoritmice și studiul complexității corelațiilor în sistemele cuantice, rezultând o definiție conștientă de corelație pentru informațiile reciproce algoritmice care satisface simetria proprietății informației.

► Date BibTeX

► Referințe

[1] L. Antunes, A. Matos, A. Pinto, A. Souto și A. Teixeira. Funcții unidirecționale folosind teorii algoritmice și clasice ale informației. Teoria sistemelor de calcul, 52 (1): 162–178, ianuarie 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 și A. Souto. Zgli: O conductă pentru gruparea prin compresie cu aplicare la stratificarea pacienților în spondiloartrită. Senzori, 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 și A. Szkoła. Entropia și complexitatea cuantică a lui Kolmogorov: o teoremă cuantică a lui Brudno. comun. Matematică. Phys., 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett şi G. Brassard. Criptografia cuantică: distribuirea cheilor publice și aruncarea de monede. În 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 şi U. Vazirani. Teoria complexității cuantice. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[6] A. Berthiaume, W. Dam și S. Laplante. Complexitatea cuantică a lui Kolmogorov. 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. Despre lungimea programelor pentru calculul secvențelor binare finite. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Deutsch. Teoria cuantică, principiul Church-Turing și computerul cuantic universal. 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. Entropia algoritmică cuantică. 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 și Paul Vitányi. Teoria informației algoritmice, paginile 289–325. E, ianuarie 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki și Karol Horodecki. Legatura cuantica. Recenzii de fizică modernă, 81 (2): 865, 2009. 10.1103 / RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Trei abordări ale definiției cantitative a informațiilor. Probleme de transmitere a informațiilor, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee și A. Romașcenko. Simetria mărginită de resurse a informațiilor revizuită. Teoretic Computer Science, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Fundamentele matematice ale informaticii 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li și Paul MB Vitányi. O introducere în complexitatea Kolmogorov și aplicațiile sale, ediția a 4-a. Texte în informatică. 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 și Sandu Popescu. Problema de oprire pentru calculatoarele cuantice. 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 și A. Souto. Universalitatea mașinilor Turing cuantice cu control determinist. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Complexitatea cuantică a lui Kolmogorov și teorema perturbării informației. Entropie, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera şi H. Imai. Complexitatea cuantică a lui Kolmogorov și distribuția cheilor cuantice. Fiz. Rev. A, 79: 012324, ianuarie 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera și Masanori Ohya. Despre procesul de oprire al mașinii de turnare cuantică. 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 și Vlatko Vedral. Limita clasico-cuantică pentru corelații: Discord și măsuri aferente. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora şi H. Briegel. Complexitatea algoritmică și încurcarea stărilor cuantice. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel și B. Kraus. Complexitatea cuantică a lui Kolmogorov și aplicațiile sale. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Complexitatea cuantică a lui Kolmogorov și mașina cuantică Turing. Ph.D. Teză, Universitatea Tehnică din Berlin, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Mașini Turing cuantice puternic universale și invarianța complexității Kolmogorov. 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. Poate un computer cuantic universal să fie complet cuantic? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen și I. Chuang. Calcul cuantic și informația cuantică. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Un Rastegin. O limită inferioară a erorii relative a clonării cu stări mixte și a operațiunilor conexe. 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 și K. Bertels. Estimarea informațiilor algoritmice folosind calculul cuantic pentru aplicații de genomică. Applied Sciences, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. O teorie matematică a comunicării. 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. O teorie formală a inferenței inductive, partea 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 și A. Teixeira. Ascunderea martorilor fără extractoare sau simulatoare. În F. Manea, R. Miller și D. Nowotka, editori, Sailing Routes in the World of Computation, paginile 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. Teoria informației algoritmice cuantice. 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 și Luís Antunes. Măsuri de entropie vs. complexitatea Kolmogorov. Entropie, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Complexitatea cuantică a lui Kolmogorov pe baza descrierilor clasice. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paul Vitanyi. Trei abordări ale definiției cantitative a informațiilor într-o stare cuantică pură individuală. În Proceedings, a 15-a Conferință anuală IEEE privind complexitatea computațională, paginile 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin și LA Levin. Complexitatea obiectelor finite și dezvoltarea conceptelor de informație și aleatorietate prin intermediul teoriei algoritmilor. Russian Mathematical Surveys, 25 (6): 83, dec 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Citat de

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

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2024-01-18 23:13:56). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2024-01-18 23:13:55).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic