Квантова складність Колмогорова та квантові кореляції в квантових машинах Тьюрінга з детермінованим керуванням

Перевидано Платоном

читають: 0

Маріано Лемус^1,2, Рікардо Фалейро^1,2, Пауло Матеус^1,2, Нікола Паункович^1,2 та Андре Соуто^2,3,4

¹Departamento de Matemática, Instituto Superior Técnico, Universidade de Lisboa, Av.Rovisco Pais, 1049-001 Lisboa, Portugal
²Instituto de Telecomunicações, Av.Rovisco Pais, 1049-001 Лісабон, Португалія
³Lasige, Faculdade de Ciências da Universidade 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

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Ця робота представляє дослідження складності Колмогорова для загальних квантових станів з точки зору квантових машин Тьюринга з детермінованим керуванням (dcq-TM). Ми розширюємо модель dcq-TM, щоб включити вхідні та вихідні дані зі змішаним станом, а також визначаємо стани, які можна обчислити за допомогою dcq, як ті, які можна апроксимувати за допомогою dcq-TM. Крім того, ми вводимо (умовну) колмогорівську складність квантових станів і використовуємо її для вивчення трьох конкретних аспектів алгоритмічної інформації, що міститься в квантовому стані: порівняння інформації в квантовому стані з її класичним представленням у вигляді масиву реальних чисел, дослідження меж квантового копіювання стану в контексті алгоритмічної складності та дослідження складності кореляцій у квантових системах, що призводить до кореляційного визначення для алгоритмічної взаємної інформації, яка задовольняє симетрію інформаційної властивості.

► Дані BibTeX

@article{Lemus2024quantumkolmogorov, doi = {10.22331/q-2024-01-18-1230}, url = {https://doi.org/10.22331/q-2024-01-18-1230}, title = {Квантова складність {K}олмогорова та квантові кореляції в квантових {T}машинах Турінга} з детермінованим керуванням, автор = {Лемус, Маріано та Фалейро, Рікардо та Матеус, Пауло та Паункові{'{c}}, Нікола та Соуто, Андр{'{e}}}, журнал = {{Quantum}}, issn = {2521-327X}, видавець = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, обсяг = {8}, сторінки = {1230}, місяць = січ, рік = {2024} }

► Список літератури

[1] Л. Антунес, А. Матос, А. Пінту, А. Соуто та А. Тейшейра. Односторонні функції з використанням алгоритмічної та класичної теорій інформації. Теорія обчислювальних систем, 52 (1): 162–178, січень 2013 р. ISSN 1433-0490. 10.1007/s00224-012-9418-z.
https: / / doi.org/ 10.1007 / s00224-012-9418-z

[2] Д. Азеведо, А. М. Родрігес, Х. Каньяо, А. М. Карвалью та А. Соуто. Zgli: конвеєр для кластеризації шляхом стиснення із застосуванням до стратифікації пацієнтів при спондилоартрозі. Sensors, 23 (3), 2023. ISSN 1424-8220. 10.3390/s23031219.
https:///doi.org/10.3390/s23031219

[3] Ф. Бенатті, Т. Крюгер, М. Мюллер, Р. Зігмунд-Шульце та А. Школа. Ентропія та квантова складність Колмогорова: квантова теорема Брудно. Комун. математика Phys., 265 (1): 437–461, 2006. 10.1007/s00220-006-0027-z.
https: / / doi.org/ 10.1007 / s00220-006-0027-z

[4] Ч. Х. Беннетт і Г. Брассард. Квантова криптографія: розподіл відкритих ключів і підкидання монет. У матеріалах міжнародної конференції IEEE з комп’ютерів, систем і обробки сигналів, сторінка 175, 1984. 10.1016/j.tcs.2014.05.025.
https:///doi.org/10.1016/j.tcs.2014.05.025

[5] Е. Бернштейн і У. Вазірані. Квантова теорія складності. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[6] А. Бертіоме, В. Дам і С. Лаплант. Квантова колмогоровська складність. 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] Г. Чайтін. Про довжину програм для обчислення кінцевих двійкових послідовностей. J. ACM, 13 (4), 1966. 10.1145/321356.321363.
https: / / doi.org/ 10.1145 / 321356.321363

[8] Д. Дойч. Квантова теорія, принцип Черча-Тюрінга та універсальний квантовий комп'ютер. Королівське товариство Лондона, серія A, 400 (1818): 97–117, 1985. 10.1098/rspa.1985.0070.
https: / / doi.org/ 10.1098 / rspa.1985.0070

[9] П. Гач. Квантова алгоритмічна ентропія. 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] Петер Грюнвальд і Пауль Вітаньї. Алгоритмічна теорія інформації, сторінки 289–325. E, січень 2008 р.
arXiv: 0809.2754

[11] Ришард Городецький, Павло Городецький, Міхал Городецький та Кароль Городецький. Квантова заплутаність. Огляди сучасної фізики, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https: / / doi.org/ 10.1103 / RevModPhys.81.865

[12] А. Колмогорова. Три підходи до кількісного визначення інформації. Проблеми передачі інформації, 1 (1), 1965. 10.1080/00207166808803030.
https: / / doi.org/ 10.1080 / 00207166808803030

[13] Т. Лі та А. Ромащенко. Переглянуто обмежену ресурсом симетрію інформації. Теоретична інформатика, 345 (2): 386–405, 2005. ISSN 0304-3975. 10.1016/j.tcs.2005.07.017. Математичні основи інформатики 2004.
https:///doi.org/10.1016/j.tcs.2005.07.017

[14] Мін Лі та Пол М. Б. Вітаньї. Вступ до складності Колмогорова та її застосування, 4-е видання. Тексти з інформатики. 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] Ной Лінден і Санду Попеску. Проблема зупинки для квантових комп'ютерів. Препринт 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] П. Матеус, А. Сернадас і А. Соуто. Універсальність квантових машин Тюрінга з детермінованим керуванням. Journal of Logic and Computation, 27 (1): 1–19, 2017. 10.1093/logcom/exv008.
https:///doi.org/10.1093/logcom/exv008

[17] Т. Міядера. Квантова складність Колмогорова та теорема інформаційних збурень. Ентропія, 13 (4): 778–789, 2011. ISSN 1099-4300. 10.3390/e13040778.
https:///doi.org/10.3390/e13040778

[18] Т. Міядера та Х. Імаї. Квантова колмогоровська складність і квантовий розподіл ключів. фіз. Rev. A, 79: 012324, січень 2009 р. 10.1103/PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Такаюкі Міядера і Масанорі Ох'я. Про процес зупинки квантової машини Тьюринга. 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] Каван Моді, Аарон Бродатч, Г’юго Кейбл, Томаш Патерек і Влатко Ведрал. Класично-квантовий кордон для кореляцій: розбіжності та пов’язані заходи. Огляди сучасної фізики, 84 (4): 1655, 2012. 10.1103/RevModPhys.84.1655.
https: / / doi.org/ 10.1103 / RevModPhys.84.1655

[21] К. Мора і Х. Брігель. Алгоритмічна складність і заплутаність квантових станів. Physical Review Letters, 95: 200503, 2005. 10.1103/PhysRevLett.95.200503.
https: / / doi.org/ 10.1103 / PhysRevLett.95.200503

[22] К. Мора, Х. Брігель і Б. Краус. Квантова колмогоровська складність та її застосування. Міжнародний журнал квантової інформації, 2007. 10.1142/S0219749907003171.
https: / / doi.org/ 10.1142 / S0219749907003171

[23] Мюллер. Квантова складність Колмогорова і квантова машина Тьюрінга. доктор філософії Дисертація, Технічний університет Берліна, 2007. 10.48550/arXiv.0712.4377.
https:///doi.org/10.48550/arXiv.0712.4377

[24] М. Мюллер. Сильно універсальні квантові машини Тюрінга та інваріантність колмогоровської складності. 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] Джон М Майерс. Чи може універсальний квантовий комп'ютер бути повністю квантовим? Physical Review Letters, 78 (9): 1823, 1997. 10.1103/PhysRevLett.78.1823.
https: / / doi.org/ 10.1103 / PhysRevLett.78.1823

[26] М. Нільсен та І. Чуанг. Квантові обчислення та квантова інформація. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https:///doi.org/10.1017/CBO9780511976667

[27] А Растегін. Нижня межа відносної похибки клонування зі змішаним станом і пов’язаних операцій. 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] А. Саркар, З. Аль-Арс, К. Бертельс. Оцінка алгоритмічної інформації за допомогою квантових обчислень для застосування в геноміці. Прикладні науки, 11 (6), 2021. ISSN 2076-3417. 10.3390/додаток11062696.
https:///doi.org/10.3390/app11062696

[29] Клод Елвуд Шеннон. Математична теорія спілкування. Технічний журнал системи Bell, 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] Р. Соломонов. Формальна теорія індуктивного висновку, частина i. Інформація та контроль, 7 (1), 1964. 10.1016/S0019-9958(64)90223-2.
https://doi.org/10.1016/S0019-9958(64)90223-2

[31] А. Суто, Л. Антунес, П. Матеус і А. Тейшейра. Переховування свідків без екстракторів і симуляторів. У F. Manea, R. Miller і D. Nowotka, редактори, Sailing Routes in the World of Computation, сторінки 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] К. Свозіл. Квантова алгоритмічна теорія інформації. Journal of Universal Computer Science, 2 (5): 311–346, травень 1996 р. 10.3217/jucs-002-05-0311.
https:///doi.org/10.3217/jucs-002-05-0311

[33] Андрея Тейшейра, Армандо Матос, Андре Соуто та Луїс Антунес. Міри ентропії проти складності Колмогорова. Ентропія, 13 (3): 595–611, 2011. ISSN 1099-4300. 10.3390/e13030595.
https:///doi.org/10.3390/e13030595

[34] П. Вітаньї. Квантова колмогоровська складність на основі класичних описів. IEEE Transactions on Information Theory, 47 (6): 2464–2479, 2001. 10.1109/18.945258.
https: / / doi.org/ 10.1109 / 18.945258

[35] Павло Вітаній. Три підходи до кількісного визначення інформації в індивідуальному чистому квантовому стані. У матеріалах 15-ї щорічної конференції IEEE з обчислювальної складності, сторінки 263–270. IEEE, 2000. 10.1109/CCC.2000.856757.
https:///doi.org/10.1109/CCC.2000.856757

[36] А. К. Звонкін і Л. А. Левін. Складність кінцевих об'єктів і розвиток понять інформації та випадковості за допомогою теорії алгоритмів. Російські математичні огляди, 25 (6): 83, грудень 1970. 10.1070/RM1970v025n06ABEH001269.
https://doi.org/10.1070/RM1970v025n06ABEH001269

Цитується

[1] Енн Бродбент, Мартті Карвонен і Себастьєн Лорд, «Uncloneable Quantum Advice», arXiv: 2309.05155, (2023).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2024-01-18 23:13:56). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2024-01-18 23:13:55).

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.