Complexidade quântica de Kolmogorov e correlações quânticas em máquinas de Turing quânticas com controle determinístico

Complexidade quântica de Kolmogorov e correlações quânticas em máquinas de Turing quânticas com controle determinístico

Carimbo de data / hora: 18 de janeiro de 2024 6h07
Nó Fonte: 3070552

Mariano Lemos1,2, Ricardo Faleiro1,2, Paulo Matheus1,2, Nikola Paunkovic1,2 e Andre Souto2,3,4

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

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Este trabalho apresenta um estudo da complexidade de Kolmogorov para estados quânticos gerais sob a perspectiva de Máquinas de Turing quânticas de controle determinístico (dcq-TM). Estendemos o modelo dcq-TM para incorporar entradas e saídas de estado misto e definimos estados computáveis ​​dcq como aqueles que podem ser aproximados por um dcq-TM. Além disso, introduzimos a complexidade (condicional) de estados quânticos de Kolmogorov e a usamos para estudar três aspectos particulares da informação algorítmica contida em um estado quântico: uma comparação da informação em um estado quântico com a de sua representação clássica como uma matriz de dados reais. números, uma exploração dos limites da cópia do estado quântico no contexto da complexidade algorítmica e estudo da complexidade das correlações em sistemas quânticos, resultando em uma definição com reconhecimento de correlação para informações mútuas algorítmicas que satisfaça a simetria da propriedade da informação.

► dados BibTeX

► Referências

[1] L. Antunes, A. Matos, A. Pinto, A. Souto e A. Teixeira. Funções unidirecionais usando teorias algorítmicas e clássicas da informação. Teoria de Sistemas de Computação, 52 (1): 162–178, janeiro 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 e A. Souto. Zgli: Um pipeline para agrupamento por compressão com aplicação à estratificação de pacientes em espondiloartrite. 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 e A. Szkoła. Entropia e complexidade quântica de Kolmogorov: um teorema quântico de Brudno. Comum. Matemática. Física, 265 (1): 437–461, 2006. 10.1007/​s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] CH Bennett e G. Brassard. Criptografia quântica: distribuição de chave pública e lançamento de moeda. Em Anais da Conferência Internacional IEEE sobre Computadores, Sistemas e Processamento de Sinais, página 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[5] E. Bernstein e U. Vazirani. Teoria da complexidade quântica. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/​S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[6] A. Berthiaume, W. Dam e S. Laplante. Complexidade quântica de 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. Sobre a duração de programas para calcular sequências binárias finitas. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Alemão. Teoria quântica, o princípio de Church-Turing e o computador quântico 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 algorítmica quântica. 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 e Paul Vitányi. Teoria da Informação Algorítmica, páginas 289–325. E, janeiro de 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki e Karol Horodecki. Emaranhamento quântico. Reviews of modern physics, 81 (2): 865, 2009. 10.1103 / RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kolmogorov. Três abordagens para a definição quantitativa da informação. Problemas de transmissão de informações, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee e A. Romashchenko. Simetria de informações limitada por recursos revisitada. Ciência da Computação Teórica, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Fundamentos Matemáticos da Ciência da Computação 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li e Paul MB Vitányi. Uma introdução à complexidade de Kolmogorov e suas aplicações, 4ª edição. Textos em Ciência da Computação. 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 e Sandu Popescu. O problema da parada para computadores quânticos. pré-impressão 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 e A. Souto. Universalidade das máquinas quânticas de Turing com controle determinístico. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Complexidade quântica de Kolmogorov e teorema da perturbação da informação. Entropia, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera e H. Imai. Complexidade quântica de Kolmogorov e distribuição de chaves quânticas. Física. Rev. A, 79: 012324, janeiro de 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera e Masanori Ohya. Sobre a interrupção do processo da máquina de turing quântica. Sistemas Abertos e Dinâmica da Informação, 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 e Vlatko Vedral. O limite quântico clássico para correlações: discórdia e medidas relacionadas. Reviews of Modern Physics, 84 (4): 1655, 2012. 10.1103/​RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] C. Mora e H. Briegel. Complexidade algorítmica e emaranhamento de estados quânticos. Physical Review Letters, 95: 200503, 2005. 10.1103/​PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] C. Mora, H. Briegel e B. Kraus. Complexidade quântica de Kolmogorov e suas aplicações. Jornal Internacional de Informação Quântica, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Complexidade quântica de Kolmogorov e a máquina quântica de Turing. Ph.D. Tese, Universidade Técnica de Berlim, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Máquinas de Turing quânticas fortemente universais e invariância da complexidade de Kolmogorov. Transações IEEE sobre Teoria da Informação, 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. Um computador quântico universal pode ser totalmente quântico? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/​PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] M. Nielsen e I. Chuang. Computação Quântica e Informação Quântica. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Um Rastegin. Um limite inferior para o erro relativo da clonagem de estado misto e operações relacionadas. Journal of Optics B: Óptica Quântica e Semiclássica, 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 e K. Bertels. Estimativa de informações algorítmicas usando computação quântica para aplicações genômicas. Ciências Aplicadas, 11 (6), 2021. ISSN 2076-3417. 10.3390/​app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude Elwood Shannon. Uma teoria matemática de comunicação. 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. Uma teoria formal de inferência indutiva, parte i. Informação e Controle, 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 e A. Teixeira. Testemunha escondida sem extratores ou simuladores. Em F. Manea, R. Miller e 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. Teoria da informação algorítmica quântica. Journal of Universal Computer Science, 2 (5): 311–346, maio de 1996. 10.3217/​jucs-002-05-0311.
https://​/​doi.org/​10.3217/​jucs-002-05-0311

[33] Andreia Teixeira, Armando Matos, André Souto e Luís Antunes. Medidas de entropia vs. complexidade de Kolmogorov. Entropia, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Complexidade quântica de Kolmogorov baseada em descrições clássicas. Transações IEEE sobre Teoria da Informação, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paulo Vitanyi. Três abordagens para a definição quantitativa de informação em um estado quântico puro individual. Nos Anais da 15ª Conferência Anual do IEEE sobre Complexidade Computacional, páginas 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin e LA Levin. A complexidade dos objetos finitos e o desenvolvimento dos conceitos de informação e aleatoriedade por meio da teoria dos algoritmos. Russian Mathematical Surveys, 25 (6): 83, dezembro de 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Citado por

[1] Anne Broadbent, Martti Karvonen e Sébastien Lord, “Conselhos Quantum Incloneáveis”, arXiv: 2309.05155, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2024-01-18 23:13:56). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2024-01-18 23:13:55).

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Carimbo de hora:

Mais de Diário Quântico