Kvantti Kolmogorov -monimutkaisuus ja kvanttikorrelaatiot deterministisen ohjauksen kvantti Turingin koneissa

Kvantti Kolmogorov -monimutkaisuus ja kvanttikorrelaatiot deterministisen ohjauksen kvantti Turingin koneissa

Aikaleima: 18. tammikuuta 2024 6
Lähdesolmu: 3070552

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

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

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Tämä työ esittelee yleisten kvanttitilojen Kolmogorov-monimutkaisuuden tutkimuksen deterministisen ohjauksen kvantti-Turing-koneiden (dcq-TM) näkökulmasta. Laajennamme dcq-TM-mallia sisältämään sekatilan tulot ja lähdöt, ja määrittelemme dcq-laskettavat tilat sellaisiksi, jotka voidaan approksimoida dcq-TM:llä. Lisäksi esittelemme kvanttitilojen (ehdollisen) Kolmogorov-monimutkaisuuden ja käytämme sitä kvanttitilan sisältämän algoritmisen informaation kolmea erityistä näkökohtaa tutkiessamme: kvanttitilassa olevan tiedon vertailua sen klassiseen esitykseen todellisten tilanteiden joukona. numerot, kvanttitilan kopioimisen rajojen tutkiminen algoritmisen monimutkaisuuden kontekstissa ja kvanttijärjestelmien korrelaatioiden monimutkaisuuden tutkiminen, mikä johtaa korrelaatiotietoiseen määritelmään algoritmiselle keskinäiselle tiedolle, joka täyttää tiedon ominaisuuden symmetrian.

► BibTeX-tiedot

► Viitteet

[1] L. Antunes, A. Matos, A. Pinto, A. Souto ja A. Teixeira. Yksisuuntaiset funktiot algoritmisten ja klassisten informaatioteorioiden avulla. Theory of Computing Systems, 52 (1): 162–178, tammikuu 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 ja A. Souto. Zgli: Putkilinja klusterointiin puristamalla, jota käytetään potilaan kerrostumiseen spondylartriitissa. Sensors, 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 ja A. Szkoła. Entropia ja kvantti-Kolmogorovin kompleksisuus: Kvantti Brudnon lause. Commun. Matematiikka. Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett ja G. Brassard. Kvanttisalaus: Julkisen avaimen jakelu ja kolikoiden heittäminen. Julkaisussa Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, sivu 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

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

[6] A. Berthiaume, W. Dam ja S. Laplante. Kvantti Kolmogorov -kompleksi. 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. Äärillisten binäärijonojen laskemiseen tarkoitettujen ohjelmien pituudesta. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https: / / doi.org/ 10.1145 / +321356.321363

[8] D. Deutsch. Kvanttiteoria, Church-Turing-periaate ja universaali kvanttitietokone. 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. Kvanttialgoritminen entropia. 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 ja Paul Vitányi. Algorithmic Information Theory, sivut 289–325. E, tammikuu 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki ja Karol Horodecki. Kvanttinen sotkeutuminen. Arvioita nykyaikaisesta fysiikasta, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Kolme lähestymistapaa tiedon kvantitatiiviseen määrittelyyn. Tiedonsiirron ongelmat, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / +00207166808803030

[13] T. Lee ja A. Romashchenko. Tietojen resurssirajoitettu symmetria tarkasteltu uudelleen. Theoretical Computer Science, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Tietojenkäsittelytieteen matemaattiset perusteet 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li ja Paul MB Vitányi. Johdatus Kolmogorov-monimutkaisuuteen ja sen sovelluksiin, 4. painos. Tietojenkäsittelytieteen tekstejä. 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 ja Sandu Popescu. Kvanttitietokoneiden pysäytysongelma. 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 ja A. Souto. Kvanttituringin koneiden universaalisuus deterministisellä ohjauksella. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Kvantti Kolmogorovin kompleksisuus ja informaatiohäiriöteoreema. Entropy, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera ja H. Imai. Kvantti Kolmogorov -kompleksisuus ja kvanttiavaimen jakauma. Phys. Rev. A, 79: 012324, tammikuu 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera ja Masanori Ohya. Kvanttituring-koneen prosessin pysäyttämisestä. 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 ja Vlatko Vedral. Klassisen kvanttiraja korrelaatioille: epäsuhta ja siihen liittyvät suuret. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora ja H. Briegel. Algoritminen monimutkaisuus ja kvanttitilojen sotkeutuminen. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel ja B. Kraus. Kvantti Kolmogorovin kompleksisuus ja sen sovellukset. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Kvantti Kolmogorov -kompleksi ja kvantti Turingin kone. Ph.D. Väitöskirja, Berliinin teknillinen yliopisto, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Voimakkaasti universaalit Turingin kvanttikoneet ja Kolmogorovin kompleksisuuden invarianssi. 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. Voiko universaali kvanttitietokone olla täysin kvantti? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen ja I. Chuang. Kvanttilaskenta ja kvanttitieto. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Rastegin. Sekatilan kloonauksen ja siihen liittyvien toimintojen suhteellisen virheen alaraja. 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 ja K. Bertels. Algoritmisen tiedon arviointi kvanttilaskentaa käyttäen genomiikan sovelluksissa. Applied Sciences, 11 (6), 2021. ISSN 2076-3417. 10.3390/app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. Matemaattinen viestintäteoria. 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. Formaalinen induktiivisen päättelyn teoria, osa 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 ja A. Teixeira. Todistaja piiloutumassa ilman imureita tai simulaattoreita. Teoksessa F. Manea, R. Miller ja D. Nowotka, toimittajat, Sailing Routes in the World of Computation, sivut 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. Kvanttialgoritminen informaatioteoria. Journal of Universal Computer Science, 2 (5): 311–346, toukokuu 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto ja Luís Antunes. Entropiamitat vs. Kolmogorov-kompleksi. Entropy, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Klassisiin kuvauksiin perustuva kvantti-Kolmogorov-kompleksi. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / +18.945258

[35] Paul Vitanyi. Kolme lähestymistapaa tiedon kvantitatiiviseen määrittelyyn yksittäisessä puhtaassa kvanttitilassa. Julkaisussa Proceedings 15th Annual IEEE Conference on Computational Complexity, sivut 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin ja LA Levin. Äärillisten objektien monimutkaisuus sekä informaation ja satunnaisuuden käsitteiden kehittäminen algoritmien teorian avulla. Russian Mathematical Surveys, 25 (6): 83, joulukuu 1970. 10.1070/RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Viitattu

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

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2024-01-18 23:13:56). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2024-01-18 23:13:55).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal