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

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

Мітка часу: 18 січня 2024 р., 6:07 ранку
Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Маріано Лемус1,2, Рікардо Фалейро1,2, Пауло Матеус1,2, Нікола Паункович1,2 та Андре Соуто2,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 Лісабон, Португалія
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

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

абстрактний

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

► Дані BibTeX

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

[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 11:13:07). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

Не вдалося отримати Перехресне посилання, наведене за даними під час останньої спроби 2024-01-18 11:13:05: Не вдалося отримати цитовані дані для 10.22331/q-2024-01-18-1230 з Crossref. Це нормально, якщо DOI був зареєстрований нещодавно.

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

Часова мітка:

Більше від Квантовий журнал