Złożoność kwantowa Kołmogorowa i korelacje kwantowe w kwantowych maszynach Turinga ze sterowaniem deterministycznym

Złożoność kwantowa Kołmogorowa i korelacje kwantowe w kwantowych maszynach Turinga ze sterowaniem deterministycznym

Znacznik czasu: 18 stycznia 2024 6:07
Węzeł źródłowy: 3070552

Mariano Lemusa1,2, Ricardo Faleiro1,2, Paweł Mateus1,2, Nikola Paunkovic1,2, André Souto2,3,4

1Departamento de Matemática, Instituto Superior Técnico, 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

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

W pracy przedstawiono badanie złożoności Kołmogorowa dla ogólnych stanów kwantowych z perspektywy kwantowych maszyn Turinga o kontroli deterministycznej (dcq-TM). Rozszerzamy model dcq-TM, aby uwzględnić wejścia i wyjścia stanu mieszanego oraz definiujemy stany obliczalne dcq jako te, które można aproksymować za pomocą dcq-TM. Ponadto wprowadzamy (warunkową) złożoność Kołmogorowa stanów kwantowych i wykorzystujemy ją do badania trzech konkretnych aspektów informacji algorytmicznej zawartej w stanie kwantowym: porównanie informacji w stanie kwantowym z jej klasyczną reprezentacją w postaci tablicy rzeczywistych liczb, badanie granic kopiowania stanu kwantowego w kontekście złożoności algorytmicznej oraz badanie złożoności korelacji w układach kwantowych, w wyniku czego powstała świadoma korelacji definicja algorytmicznej wzajemnej informacji, która spełnia symetrię właściwości informacji.

► Dane BibTeX

► Referencje

[1] L. Antunes, A. Matos, A. Pinto, A. Souto i A. Teixeira. Funkcje jednokierunkowe wykorzystujące algorytmiczną i klasyczną teorię informacji. Teoria systemów komputerowych, 52 (1): 162–178, styczeń 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: Rurociąg do grupowania przez kompresję z zastosowaniem do stratyfikacji pacjenta w spondyloartropatii. Czujniki, 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 złożoność kwantowa Kołmogorowa: Kwantowe twierdzenie Brudna. komuna. Matematyka. Fiz., 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. Kryptografia kwantowa: dystrybucja klucza publicznego i rzucanie monetą. W Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, s. 175, 1984. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[5] E. Bernsteina i U. Vazirani. Teoria złożoności kwantowej. 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. Kwantowa złożoność Kołmogorowa. 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. O długości programów do obliczania skończonych ciągów binarnych. J. ACM, 13 (4), 1966. 10.1145/​321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] D. Niemiecki. Teoria kwantowa, zasada Churcha-Turinga i uniwersalny komputer kwantowy. 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. Kwantowa entropia algorytmiczna. 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] Petera Grünwalda i Paula Vitányi. Algorytmiczna teoria informacji, strony 289–325. E., styczeń 2008.
arXiv: 0809.2754

[11] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki i Karol Horodecki. Splątanie kwantowe. Recenzje współczesnej fizyki, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] A. Kołmogorowa. Trzy podejścia do ilościowej definicji informacji. Problemy przekazywania informacji, 1 (1), 1965. 10.1080/​00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] T. Lee i A. Romaszczenko. Ponowna analiza symetrii informacji ograniczonej zasobami. Informatyka teoretyczna, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/​j.tcs.2005.07.017. Matematyczne podstawy informatyki 2004.
https: / / doi.org/ 10.1016 / j.tcs.2005.07.017

[14] Ming Li i Paul MB Vitányi. Wprowadzenie do złożoności Kołmogorowa i jej zastosowań, wydanie 4. Teksty z informatyki. 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] Noaha Lindena i Sandu Popescu. Problem zatrzymania komputerów kwantowych. 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. Uniwersalność kwantowych maszyn Turinga ze sterowaniem deterministycznym. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/​logcom/​exv008.
https://​/​doi.org/​10.1093/​logcom/​exv008

[17] T. Miyadera. Kwantowa złożoność Kołmogorowa i twierdzenie o zakłóceniu informacji. Entropia, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/​e13040778.
https: / / doi.org/ 10.3390 / e13040778

[18] T. Miyadera i H. Imai. Kwantowa złożoność Kołmogorowa i kwantowa dystrybucja klucza. Fiz. Rev. A, 79: 012324, styczeń 2009. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Takayuki Miyadera i Masanori Ohya. O zatrzymaniu procesu kwantowej maszyny Turinga. Systemy otwarte i dynamika informacji, 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. Granica klasyczno-kwantowa dla korelacji: Discord i miary pokrewne. Recenzje 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. Złożoność algorytmiczna i splątanie stanów kwantowych. 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. Złożoność kwantowa Kołmogorowa i jej zastosowania. International Journal of Quantum Information, 2007. 10.1142/​S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] M Muller. Złożoność kwantowa Kołmogorowa i kwantowa maszyna Turinga. Doktorat Praca dyplomowa, Uniwersytet Techniczny w Berlinie, 2007. 10.48550/​arXiv.0712.4377.
https://​/​doi.org/​10.48550/​arXiv.0712.4377

[24] M. Müller. Silnie uniwersalne kwantowe maszyny Turinga i niezmienność złożoności Kołmogorowa. Transakcje IEEE dotyczące teorii informacji, 54 (2): 763–780, 2008. ISSN 0018-9448. 10.1109/​TIT.2007.913263.
https: / / doi.org/ 10.1109 / TIT.2007.913263

[25] Johna M. Myersa. Czy uniwersalny komputer kwantowy może być w pełni kwantowy? 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. Obliczenia kwantowe i informacja kwantowa. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Rastegina. Dolna granica błędu względnego klonowania w stanie mieszanym i powiązanych operacji. 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. Szacowanie informacji algorytmicznej z wykorzystaniem obliczeń kwantowych do zastosowań genomiki. Nauki Stosowane, 11 (6), 2021. ISSN 2076-3417. 10.3390/​aplikacja11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Claude'a Elwooda Shannona. Matematyczna teoria komunikacji. 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. Solomonoffa. Formalna teoria wnioskowania indukcyjnego, część I. Informacja i kontrola, 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. Świadek ukrywa się bez ekstraktorów i symulatorów. W: Red. F. Manea, R. Miller i D. Nowotka, Trasy żeglarskie w świecie obliczeń, s. 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. Kwantowa algorytmiczna teoria informacji. Journal of Universal Computer Science, 2 (5): 311–346, maj 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. Miary entropii a złożoność Kołmogorowa. Entropia, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/​e13030595.
https: / / doi.org/ 10.3390 / e13030595

[34] P. Vitányi. Złożoność kwantowa Kołmogorowa na podstawie opisów klasycznych. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/​18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Paweł Witanyi. Trzy podejścia do ilościowej definicji informacji w indywidualnym czystym stanie kwantowym. W Proceedings 15. doroczna konferencja IEEE na temat złożoności obliczeniowej, strony 263–270. IEEE, 2000. 10.1109/​CCC.2000.856757.
https: / / doi.org/ 10.1109 / CCC.2000.856757

[36] AK Zvonkin i LA Levin. Złożoność obiektów skończonych oraz rozwój pojęć informacji i losowości za pomocą teorii algorytmów. Russian Mathematical Surveys, 25 (6): 83, grudzień 1970. 10.1070/​RM1970v025n06ABEH001269.
https:/​/​doi.org/​10.1070/​RM1970v025n06ABEH001269

Cytowany przez

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

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2024-01-18 23:13:56). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2024-01-18 23:13:55).

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy