Квантовая колмогоровская сложность и квантовые корреляции в квантовых машинах Тьюринга с детерминированным управлением

Квантовая колмогоровская сложность и квантовые корреляции в квантовых машинах Тьюринга с детерминированным управлением

Отметка времени: 18 января 2024 г., 6:07
Исходный узел: 3070552

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

1Департамент математики, Высший технический институт, Университет Лиссабона, Av.Rovisco Pais, 1049-001 Лиссабон, Португалия
2Институт телекоммуникаций, Av.Rovisco Pais, 1049-001 Лиссабон, Португалия
3Ласиж, Факультет наук Университета Лиссабона, Кампу-Гранде, 1749-016 Лиссабон, Португалия
4Департамент информатики, Факультет наук Университета Лиссабона, Кампу-Гранде, 1749-016 Лиссабон, Португалия

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

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

► Данные BibTeX

► Рекомендации

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

[2] Д. Азеведо, А.М. Родригеш, Х. Каньян, А.М. Карвалью и А. Соуто. Zgli: Конвейер для кластеризации путем сжатия с применением для стратификации пациентов при спондилоартрите. Сенсоры, 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-г

[4] CH Bennett и G. Brassard. Квантовая криптография: распределение открытых ключей и подбрасывание монет. В материалах Международной конференции 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] А. Бертьом, В. Дам и С. Лаплант. Квантовая колмогоровская сложность. Журнал компьютерных и системных наук, 63 (2): 201–221, 2001. 10.1006/​jcss.2001.1765.
https: / / doi.org/ 10.1006 / jcss.2001.1765

[7] Г. Чайтин. О длине программ вычисления конечных двоичных последовательностей. Дж. 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] П. Гач. Квантовая алгоритмическая энтропия. Журнал физики 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. Э, январь 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-е издание. Тексты по информатике. Спрингер, 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: колич-фот / 9806054

[16] П. Матеус, А. Сернадас и А. Соуто. Универсальность квантовых машин Тьюринга с детерминированным управлением. Журнал логики и вычислений, 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] Т. Миядера и Х. Имаи. Квантовая колмогоровская сложность и квантовое распределение ключей. Физ. Ред. А, 79: 012324, январь 2009 г. 10.1103/​PhysRevA.79.012324.
https: / / doi.org/ 10.1103 / PhysRevA.79.012324

[19] Такаюки Миядера и Масанори Оя. Об остановке квантовой машины Тьюринга. Открытые системы и информационная динамика, 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 по теории информации, 54 (2): 763–780, 2008. ISSN 0018-9448. 10.1109/​ТИТ.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] М. Нильсен и И. Чуанг. Квантовые вычисления и квантовая информация. Издательство Кембриджского университета, 2010. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

[27] Растегин. Нижняя граница относительной ошибки клонирования в смешанном состоянии и связанных с ним операций. Журнал оптики B: Квантовая и полуклассическая оптика, 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/app11062696.
https://​/​doi.org/​10.3390/​app11062696

[29] Клод Элвуд Шеннон. Математическая теория связи. Технический журнал Bell System, 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] А. Соуто, Л. Антунес, П. Матеуш и А. Тейшейра. Свидетель скрывается без экстракторов и симуляторов. В книге Ф. Манеа, Р. Миллера и Д. Новотка, редакторов, «Плавающие маршруты в мире вычислений», страницы 397–409, Чам, 2018. Springer International Publishing. 10.1007/​978-3-319-94418-0_40.
https:/​/​doi.org/​10.1007/​978-3-319-94418-0_40

[32] К. Свозил. Квантовая алгоритмическая теория информации. Журнал 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] Энн Бродбент, Мартти Карвонен и Себастьен Лорд, «Неклонируемый квантовый совет», Arxiv: 2309.05155, (2023).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2024-01-18 23:13:56). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2024-01-18 23:13:55).

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

Отметка времени:

Больше от Квантовый журнал