Complessità quantistica di Kolmogorov e correlazioni quantistiche nelle macchine di Turing quantistiche a controllo deterministico

Ripubblicato da Platone

Seguaci: 0

Mariano Lemus^1,2, Ricardo Faleiro^1,2, Paolo Matteo^1,2, Nikola Paunkovic^1,2e André Souto^2,3,4

¹Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portogallo
²Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Lisbona, Portogallo
³Lasige, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisbona, Portogallo
⁴Departamento de Informática, Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisbona, Portogallo

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Questo lavoro presenta uno studio della complessità di Kolmogorov per stati quantistici generali dal punto di vista delle macchine di Turing quantistiche a controllo deterministico (dcq-TM). Estendiamo il modello dcq-TM per incorporare input e output a stati misti e definiamo stati calcolabili dcq come quelli che possono essere approssimati da un dcq-TM. Inoltre, introduciamo la complessità (condizionale) di Kolmogorov degli stati quantistici e la usiamo per studiare tre aspetti particolari dell'informazione algoritmica contenuta in uno stato quantistico: un confronto dell'informazione in uno stato quantistico con quella della sua rappresentazione classica come una serie di reali numeri, un'esplorazione dei limiti della copia dello stato quantistico nel contesto della complessità algoritmica e uno studio della complessità delle correlazioni nei sistemi quantistici, con conseguente definizione consapevole della correlazione per l'informazione reciproca algoritmica che soddisfa la simmetria della proprietà dell'informazione.

► dati BibTeX

@article{Lemus2024quantumkolmogorov, doi = {10.22331/q-2024-01-18-1230}, url = {https://doi.org/10.22331/q-2024-01-18-1230}, title = {Quantum {K}olmogorov complexity and quantum correlations in deterministic-control quantum {T}uring machines}, author = {Lemus, Mariano and Faleiro, Ricardo and Mateus, Paulo and Paunkovi{‘{c}}, Nikola and Souto, Andr{‘{e}}}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1230}, month = jan, year = {2024} }

► Riferimenti

, L. Antunes, A. Matos, A. Pinto, A. Souto e A. Teixeira. Funzioni unidirezionali utilizzando teorie algoritmiche e classiche dell'informazione. Teoria dei sistemi informatici, 52 (1): 162–178, gennaio 2013. ISSN 1433-0490. 10.1007/s00224-012-9418-z.
https: / / doi.org/ 10.1007 / s00224-012-9418-z

, D. Azevedo, AM Rodrigues, H. Canhão, AM Carvalho e A. Souto. Zgli: Una pipeline per il clustering mediante compressione con applicazione alla stratificazione dei pazienti affetti da spondiloartrite. Sensori, 23 (3), 2023. ISSN 1424-8220. 10.3390/s23031219.
https: / / doi.org/ 10.3390 / s23031219

, F. Benatti, T. Krüger, M. Müller, R. Siegmund-Schultze e A. Szkoła. Entropia e complessità quantistica di Kolmogorov: un teorema di Brudno quantistico. Comune. Matematica. Fisica, 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

, CH Bennett e G. Brassard. Crittografia quantistica: distribuzione della chiave pubblica e lancio di monete. In Atti della conferenza internazionale IEEE su computer, sistemi e elaborazione dei segnali, pagina 175, 1984. 10.1016/j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

, E. Bernstein e U. Vazirani. Teoria della complessità quantistica. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

, A. Berthiaume, W. Dam e S. Laplante. Complessità quantistica di 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

, G. Chaitin. Sulla lunghezza dei programmi per il calcolo di sequenze binarie finite. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363 mila

, D.Deutsch. Teoria quantistica, principio di Church-Turing e computer quantistico universale. Atti della Royal Society of London Serie A, 400 (1818): 97–117, 1985. 10.1098/rspa.1985.0070.
https: / / doi.org/ 10.1098 / rspa.1985.0070

, P. Gács. Entropia algoritmica quantistica. 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

, Peter Grünwald e Paul Vitányi. Teoria dell'informazione algoritmica, pagine 289–325. E, gennaio 2008.
arXiv: 0809.2754

, Ryszard Horodecki, Paweł Horodecki, Michał Horodecki e Karol Horodecki. Entanglement quantistico. Recensioni di fisica moderna, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

, A. Kolmogorov. Tre approcci alla definizione quantitativa dell'informazione. Problemi di trasmissione dell'informazione, 1 (1), 1965. 10.1080/00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030 mila

, T. Lee e A. Romashchenko. Simmetria delle informazioni limitata alle risorse rivisitata. Informatica teorica, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. Fondamenti matematici dell'informatica 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

, Ming Li e Paul MB Vitányi. Un'introduzione alla complessità di Kolmogorov e alle sue applicazioni, 4a edizione. Testi di informatica. 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

, Noah Linden e Sandu Popescu. Il problema dell’arresto per i computer quantistici. arXiv prestampa quant-ph/9806054, 1998. 10.48550/arXiv.quant-ph/9806054.
https:///doi.org/10.48550/arXiv.quant-ph/9806054
arXiv: Quant-ph / 9806054

, P. Mateus, A. Sernadas e A. Souto. Universalità delle macchine di Turing quantistiche con controllo deterministico. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/logcom/exv008.
https:///doi.org/10.1093/logcom/exv008

, T. Miyadera. Complessità quantistica di Kolmogorov e teorema del disturbo dell'informazione. Entropia, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https: / / doi.org/ 10.3390 / e13040778

, T. Miyadera e H. Imai. Complessità quantistica di Kolmogorov e distribuzione delle chiavi quantistiche. Fis. Rev. A, 79: 012324, gennaio 2009. 10.1103/PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

, Takayuki Miyadera e Masanori Ohya. Sul processo di arresto della macchina di Turing quantistica. Open Systems & Information Dynamics, 12 (3): 261–264, 2005. 10.1007/s11080-005-0923-2.
https://doi.org/10.1007/s11080-005-0923-2

, Kavan Modi, Aharon Brodutch, Hugo Cable, Tomasz Paterek e Vlatko Vedral. Il confine classico-quantistico per le correlazioni: Discordanza e misure correlate. Recensioni di fisica moderna, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

, C. Mora e H. Briegel. Complessità algoritmica ed entanglement di stati quantistici. Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

, C. Mora, H. Briegel e B. Kraus. Complessità quantistica di Kolmogorov e sue applicazioni. International Journal of Quantum Information, 2007. 10.1142/S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

, M. Muller. Complessità quantistica di Kolmogorov e macchina quantistica di Turing. Dottorato di ricerca Tesi, Università Tecnica di Berlino, 2007. 10.48550/arXiv.0712.4377.
https:///doi.org/10.48550/arXiv.0712.4377

, M. Müller. Macchine di Turing quantistiche fortemente universali e invarianza della complessità di 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

, John M. Myers. Un computer quantistico universale può essere completamente quantistico? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

, M. Nielsen e I. Chuang. Calcolo quantistico e informazione quantistica. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

, Un Rastegin. Un limite inferiore all'errore relativo della clonazione a stati misti e delle operazioni correlate. 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

, A. Sarkar, Z. Al-Ars e K. Bertels. Stima delle informazioni algoritmiche utilizzando il calcolo quantistico per applicazioni di genomica. Scienze applicate, 11 (6), 2021. ISSN 2076-3417. 10.3390/app11062696.
https:///doi.org/10.3390/app11062696

, Claude Elwood Shannon. Una teoria matematica di comunicazione. 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

, R. Solomonoff. Una teoria formale dell'inferenza induttiva, parte i. Informazioni e controllo, 7 (1), 1964. 10.1016/S0019-9958(64)90223-2.
https://doi.org/10.1016/S0019-9958(64)90223-2

, A. Souto, L. Antunes, P. Mateus e A. Teixeira. Testimone nascosto senza estrattori o simulatori. In F. Manea, R. Miller e D. Nowotka, editori, Sailing Routes in the World of Computation, pagine 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

, K.Svozil. Teoria algoritmica quantistica dell'informazione. Journal of Universal Computer Science, 2 (5): 311–346, maggio 1996. 10.3217/jucs-002-05-0311.
https:///doi.org/10.3217/jucs-002-05-0311

, Andreia Teixeira, Armando Matos, André Souto e Luís Antunes. Misure di entropia vs. complessità di Kolmogorov. Entropia, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https: / / doi.org/ 10.3390 / e13030595

, P. Vitanyi. Complessità quantistica di Kolmogorov basata su descrizioni classiche. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https: / / doi.org/ 10.1109 / 18.945258 mila

, Paolo Vitanyi. Tre approcci alla definizione quantitativa dell'informazione in uno stato quantistico puro individuale. Negli atti della 15a conferenza annuale IEEE sulla complessità computazionale, pagine 263–270. IEEE, 2000/CCC.10.1109.
https: / / doi.org/ 10.1109 / CCC.2000.856757

, AK Zvonkin e LA Levin. La complessità degli oggetti finiti e lo sviluppo dei concetti di informazione e casualità attraverso la teoria degli algoritmi. Russian Mathematical Surveys, 25 (6): 83, dic 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

Citato da

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

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2024-01-18 23:13:56). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2024-01-18 23:13:55).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.