Complejidad cuántica de Kolmogorov y correlaciones cuánticas en máquinas de Turing cuánticas de control determinista

Reeditado por Platón

seguidores: 0

Mariano Lemus^1,2, Ricardo Faleiro^1,2, paulo mateus^1,2, Nikola Paunković^1,2y Andres Souto^2,3,4

¹Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
²Instituto de Telecomunicaciones, Av. Rovisco País, 1049-001 Lisboa, Portugal
³Lasige, Facultad de Ciencias de la Universidad de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal
⁴Departamento de Informática,Faculdade de Ciências da Universidade de Lisboa, Campo Grande, 1749-016 Lisboa, Portugal

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

Este trabajo presenta un estudio de la complejidad de Kolmogorov para estados cuánticos generales desde la perspectiva de las Máquinas de Turing cuánticas de control determinista (dcq-TM). Ampliamos el modelo dcq-TM para incorporar entradas y salidas de estados mixtos, y definimos estados computables con dcq como aquellos que pueden ser aproximados por un dcq-TM. Además, introducimos la complejidad (condicional) de Kolmogorov de los estados cuánticos y la utilizamos para estudiar tres aspectos particulares de la información algorítmica contenida en un estado cuántico: una comparación de la información en un estado cuántico con la de su representación clásica como una matriz de estados cuánticos reales. números, una exploración de los límites de la copia de estados cuánticos en el contexto de la complejidad algorítmica y el estudio de la complejidad de las correlaciones en sistemas cuánticos, lo que da como resultado una definición consciente de la correlación para la información mutua algorítmica que satisface la simetría de la propiedad de la información.

► datos 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} }

► referencias

[ 1 ] L. Antunes, A. Matos, A. Pinto, A. Souto y A. Teixeira. Funciones unidireccionales que utilizan teorías de la información algorítmicas y clásicas. Teoría de los sistemas informáticos, 52 (1): 162–178, enero de 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 y A. Souto. Zgli: un tubo para agrupamiento por compresión con aplicación a la estratificación de pacientes en espondiloartritis. Sensores, 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 y A. Szkoła. Entropía y complejidad cuántica de Kolmogorov: un teorema cuántico de Brudno. Comunitario. Matemáticas. Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[ 4 ] CH Bennett y G. Brassard. Criptografía cuántica: distribución de claves públicas y lanzamiento de monedas. En Actas de la Conferencia Internacional IEEE sobre Computadoras, Sistemas y Procesamiento de Señales, página 175, 1984. 10.1016/j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[ 5 ] E. Bernstein y U. Vazirani. Teoría de la complejidad cuántica. Revista SIAM de Computación, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[ 6 ] A. Berthiaume, W. Dam y S. Laplante. Complejidad cuántica de Kolmogorov. Revista de Ciencias de la Computación y Sistemas, 63 (2): 201–221, 2001. 10.1006/jcss.2001.1765.
https: / / doi.org/ 10.1006 / jcss.2001.1765

[ 7 ] G. Chaitín. Sobre la duración de los programas para calcular secuencias binarias finitas. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[ 8 ] D. Alemán. Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal. Serie A de procedimientos de la Royal Society of London, 400 (1818): 97–117, 1985. 10.1098/rspa.1985.0070.
https: / / doi.org/ 10.1098 / rspa.1985.0070

[ 9 ] P. Gács. Entropía algorítmica cuántica. Revista de Física A: Matemática y 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 y Paul Vitányi. Teoría de la información algorítmica, páginas 289–325. E, enero de 2008.
arXiv: 0809.2754

[ 11 ] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki y Karol Horodecki. Entrelazamiento cuántico. Reseñas de física moderna, 81 (2): 865, 2009. 10.1103 / RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[ 12 ] A. Kolmogorov. Tres aproximaciones a la definición cuantitativa de información. Problemas de transmisión de información, 1 (1), 1965. 10.1080/00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[ 13 ] T. Lee y A. Romashchenko. Simetría de información limitada por recursos revisada. Informática teórica, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. Fundamentos matemáticos de la informática 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[ 14 ] Ming Li y Paul MB Vitányi. Introducción a la complejidad de Kolmogorov y sus aplicaciones, cuarta edición. Textos en Informática. Springer, 4. ISBN 2019-978-3-030-11297. 4/10.1007-978-3-030-11298.
https://doi.org/10.1007/978-3-030-11298-1

[ 15 ] Noah Linden y Sandu Popescu. El problema de la detención de los ordenadores cuánticos. Preimpresión de arXiv 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 y A. Souto. Universalidad de las máquinas cuánticas de Turing con control determinista. Revista de Lógica y Computación, 27 (1): 1–19, 2017. 10.1093/logcom/exv008.
https://doi.org/10.1093/logcom/exv008

[ 17 ] T. Miyadera. Teorema de complejidad cuántica de Kolmogorov y perturbación de la información. Entropía, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https: / / doi.org/ 10.3390 / e13040778

[ 18 ] T. Miyadera y H. Imai. Complejidad cuántica de Kolmogorov y distribución de claves cuánticas. Física. Rev. A, 79: 012324, enero de 2009. 10.1103/PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[ 19 ] Takayuki Miyadera y Masanori Ohya. Sobre la detención del proceso de la máquina cuántica de Turing. Sistemas abiertos y dinámica de la información, 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 y Vlatko Vedral. El límite cuántico clásico para las correlaciones: discordia y medidas relacionadas. Reseñas de Física Moderna, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[ 21 ] C. Mora y H. Briegel. Complejidad algorítmica y entrelazamiento de estados cuánticos. Cartas de revisión física, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[ 22 ] C. Mora, H. Briegel y B. Kraus. Complejidad cuántica de Kolmogorov y sus aplicaciones. Revista Internacional de Información Cuántica, 2007. 10.1142/S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[ 23 ] Müller. La complejidad cuántica de Kolmogorov y la máquina cuántica de Turing. Doctor. Tesis, Universidad Técnica de Berlín, 2007. 10.48550/arXiv.0712.4377.
https:///doi.org/10.48550/arXiv.0712.4377

[ 24 ] Sr. Müller. Máquinas cuánticas de Turing fuertemente universales e invariancia de la complejidad de Kolmogorov. Transacciones IEEE sobre teoría de la información, 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. ¿Puede una computadora cuántica universal ser completamente cuántica? Cartas de revisión física, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[ 26 ] M. Nielsen y I. Chuang. Computación cuántica e información cuántica. Prensa de la Universidad de Cambridge, 2010. 10.1017/CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[ 27 ] Un Rastegin. Un límite inferior del error relativo de la clonación de estado mixto y operaciones relacionadas. 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 y K. Bertels. Estimación de información algorítmica mediante computación cuántica para aplicaciones genómicas. Ciencias Aplicadas, 11 (6), 2021. ISSN 2076-3417. 10.3390/aplicación11062696.
https:///doi.org/10.3390/app11062696

[ 29 ] Claude Elwood Shannon. Una teoría matemática de la comunicación. 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. Salomónoff. Una teoría formal de la inferencia inductiva, parte i. Información y 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 y A. Teixeira. Escondite de testigos sin extractores ni simuladores. En F. Manea, R. Miller y D. Nowotka, editores, Sailing Routes in the World of Computation, páginas 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. Teoría de la información algorítmica cuántica. Journal of Universal Computer Science, 2 (5): 311–346, mayo de 1996. 10.3217/jucs-002-05-0311.
https:///doi.org/10.3217/jucs-002-05-0311

[ 33 ] Andreia Teixeira, Armando Matos, André Souto y Luís Antunes. Medidas de entropía versus complejidad de Kolmogorov. Entropía, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https: / / doi.org/ 10.3390 / e13030595

[ 34 ] P. Vitányi. Complejidad cuántica de Kolmogorov basada en descripciones clásicas. Transacciones IEEE sobre teoría de la información, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[ 35 ] Pablo Vitanyi. Tres enfoques para la definición cuantitativa de información en un estado cuántico puro individual. En Actas de la 15ª Conferencia Anual del IEEE sobre Complejidad Computacional, páginas 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[ 36 ] AK Zvonkin y LA Levin. La complejidad de los objetos finitos y el desarrollo de los conceptos de información y aleatoriedad mediante la teoría de los algoritmos. Russian Mathematical Surveys, 25 (6): 83, diciembre de 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

Citado por

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

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2024-01-18 23:13:56). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.

On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2024-01-18 23:13:55).

Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.