Проверка идентичности наборов квантовых состояний: анализ сложности выборки

Проверка идентичности наборов квантовых состояний: анализ сложности выборки

Отметка времени: 11 сентября 2023 г., 8:05

Марко Фаницца1, Раффаэле Сальвиа2и Витторио Джованнетти3

1Теорическая физика: Информация и квантовые феномены, Департамент физики, Автономный университет Барселоны, 08193 Беллатерра, Испания.
2Scuola Normale Superiore, I-56127 Пиза, Италия.
3NEST, Scuola Normale Superiore и Istituto Nanoscienze-CNR, I-56127 Пиза, Италия.

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

Абстрактные

Мы изучаем проблему проверки идентичности набора неизвестных квантовых состояний при наличии выборочного доступа к этому набору, причем каждое состояние появляется с некоторой известной вероятностью. Мы показываем, что для набора $d$-мерных квантовых состояний мощности $N$ выборочная сложность равна $O(sqrt{N}d/epsilon^2)$ с соответствующей нижней границей с точностью до мультипликативной константы. . Тест получается путем оценки среднеквадратического расстояния Гильберта-Шмидта между состояниями благодаря подходящему обобщению оценки расстояния Гильберта-Шмидта между двумя неизвестными состояниями Бэдеску, О'Доннелла и Райта [13].

Проверка идентичности наборов квантовых состояний: анализ сложности выборки PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Рекомендованное изображение: две настройки, к которым применима наша модель. В а) независимые источники создают случайное число копий состояния, распределенное по Пуассону, за время $T$. В б) процедура измерения подготавливает помеченные состояния, причем каждая метка появляется с некоторой вероятностью.

► Данные BibTeX

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

[1] Херардо Адессо, Томас Р. Бромли и Марко Чианчиарусо, «Меры и приложения квантовых корреляций», Журнал физики A: Mathematical and Theoretical 49, 473001 (2016).
https:/​/​doi.org/​10.1088/​1751-8113/​49/​47/​473001
Arxiv: 1605.00806

[2] Джаядев Ачарья, Ибрагим Исса, Нирмал В. Шенде и Аарон Б. Вагнер, «Оценка квантовой энтропии», Журнал IEEE по избранным областям теории информации 1, 454–468 (2020).
https: / / doi.org/ 10.1109 / JSAIT.2020.3015235
https://​/​ieeexplore.ieee.org/​document/​9163139/​

[3] Джаядев Ачарья и Константинос Даскалакис «Тестирование биномиальных распределений Пуассона» Материалы двадцать шестого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 1829–1840 (2015).
https: / / doi.org/ 10.1137 / 1.9781611973730.122
Arxiv: 1507.05952

[4] Дайки Акимото и Масахито Хаяси «Дискриминация точки изменения в квантовой обстановке» Physical Review A 83, 052328 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.052328
Arxiv: 1102.2555

[5] Роберт Алицкий, Славомир Рудницкий и Славомир Садовский, «Свойства симметрии состояний-продуктов для системы N атомов n-уровня», Журнал математической физики 29, 1158–1162 (1988).
https: / / doi.org/ 10.1063 / 1.527958

[6] Ге Бай, Я-Донг Ву, Ян Чжу, Масахито Хаяши и Джулио Чирибелла, «Квантовое причинное распутывание» npj Quantum Information 8, 69 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00578-4
Arxiv: 2109.13166

[7] Тугкан Бату, Эльдар Фишер, Лэнс Фортноу, Рави Кумар, Ронитт Рубинфельд и Патрик Уайт, «Тестирование случайных величин на независимость и идентичность», Труды 42-го симпозиума IEEE по основам компьютерных наук 442–451 (2001).
https: / / doi.org/ 10.1109 / SFCS.2001.959920
https://​/​ieeexplore.ieee.org/​document/​959920/​

[8] Дэйв Бэкон, Исаак Л. Чуанг и Арам В. Харроу, «Эффективные квантовые схемы для преобразований Шура и Клебша-Гордана», Physical Review Letters 97, 170502 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.170502
Arxiv: 0407082

[9] Себастьян Бубек, Ситан Чен и Джерри Ли, «Запутывание необходимо для оптимального тестирования квантовых свойств», 2020-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS), 61 г., 692–703 (2020 г.).
https: / / doi.org/ 10.1109 / FOCS46700.2020.00070
Arxiv: 2004.07869

[10] Чарльз Х. Беннетт, Игорь Деветак, Арам В. Харроу, Питер В. Шор и Андреас Винтер, «Квантовая обратная теорема Шеннона и компромисс между ресурсами для моделирования квантовых каналов», Транзакции IEEE по теории информации 60, 2926–2959 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2309968
http://​/​ieeexplore.ieee.org/​document/​6757002/​

[11] Э. Баган, С. Иблисдир и Р. Муньос-Тапия, «Относительные состояния, квантовые оси и квантовые ссылки», Physical Review A 73, 022341 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022341
Arxiv: 0508187

[12] Стефан Бушерон, Габор Лугоши и Паскаль Массар, «Неравенство концентрации», Oxford University Press (2013).
https: / / doi.org/ 10.1093 / acprof: осо / 9780199535255.001.0001

[13] Костин Бэдеску, Райан О'Доннелл и Джон Райт, «Квантовая государственная сертификация». Материалы 51-го ежегодного симпозиума ACM SIGACT по теории вычислений 503–514 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316344
Arxiv: 1708.06002

[14] Стивен Д. Бартлетт, Терри Рудольф и Роберт В. Спеккенс, «Оптимальные измерения относительной квантовой информации», Physical Review A 70, 032321 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.032321
Arxiv: 0310009

[15] Гарри Бурман, Ричард Клив, Джон Уотрус и Рональд де Вольф, «Квантовый отпечаток пальца», Physical Review Letters 87, 167902 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.87.167902
Arxiv: 0102001

[16] Клемент Л. Кэннон «Опрос по тестированию распределения: ваши данные большие. Но это Блю? Теория вычислений 1, 1–100 (2020).
https: / / doi.org/ 10.4086 / toc.gs.2020.009
http://www.theoryofcomputing.org/articles/gs009

[17] Сиу-Он Чан, Илиас Диакониколас, Пол Валиант и Грегори Валиант, «Оптимальные алгоритмы для проверки близости дискретных распределений», Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 1193–1203 (2014).
https: / / doi.org/ 10.1137 / 1.9781611973402.88
Arxiv: 1308.3946

[18] Маттиас Кристандл «Структура двудольных квантовых состояний – идеи теории групп и криптографии» (2006).
Arxiv: 0604183

[19] Ситан Чен, Джерри Ли и Райан О'Доннелл, «На пути к сертификации оптимального состояния с помощью некогерентных измерений», Материалы тридцать пятой конференции по теории обучения 178, 2541–2596 (2022) https:/​/​proceedings.mlr.press /v178/chen22b.html.
Arxiv: 2102.13098

[20] Томас М. Ковер и Джой А. Томас «Элементы теории информации» (2005).
https: / / doi.org/ 10.1002 / 047174882X

[21] Илиас Диакониколас и Дэниел М. Кейн «Новый подход к тестированию свойств дискретных распределений», 2016 г., 57-й ежегодный симпозиум IEEE по основам информатики (FOCS) 685–694 (2016 г.).
https: / / doi.org/ 10.1109 / FOCS.2016.78
Arxiv: 1601.05557
http://​/​ieeexplore.ieee.org/​document/​7782983/​

[22] Илиас Диакониколас, Дэниел М. Кейн и Владимир Никишкин, «Проверка идентичности структурированных распределений», Материалы двадцать шестого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 2015 г. – январь, 1841–1854 гг. (2015 г.).
https: / / doi.org/ 10.1137 / 1.9781611973730.123

[23] М. Фаницца, М. Розати, М. Скотиниотис, Дж. Калсамилья и В. Джованнетти, «За пределами теста подкачки: оптимальная оценка перекрытия квантовых состояний», Physical Review Letters 124, 060503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.060503
Arxiv: 1906.10639

[24] Марко Фаницца, Кристоф Хирче и Джон Кальсамилья, «Предельные пределы для самого быстрого обнаружения точки квантового изменения», Phys. Преподобный Летт. 131, 020602 (2023).
https: / / doi.org/ 10.1103 / PhysRevLett.131.020602
Arxiv: 2208.03265

[25] Марко Фаницца, Фарзад Кианваш и Витторио Джованнетти, «Квантовые флаги и новые границы квантовой емкости деполяризующего канала», Physical Review Letters 125, 020503 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.020503
Arxiv: 1911.01977

[26] Марко Фаницца, Фарзад Кианваш и Витторио Джованнетти, «Оценка квантовой и частной пропускной способности гауссовских каналов с помощью деградируемых расширений», Phys. Преподобный Летт. 127, 210501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.210501
Arxiv: 2103.09569

[27] Н. Гизинанд С. Иблисдир «Квантовые относительные состояния» The European Physical Journal D 39, 321–327 (2006).
https: / / doi.org/ 10.1140 / epjd / e2006-00097-y
Arxiv: 0507118

[28] Одед Гольдрейх «Введение в тестирование недвижимости», издательство Кембриджского университета (2017).
https: / / doi.org/ 10.1017 / 9781108135252

[29] Одед Голдрейханд Дана Рон «О тестировании разложения в графах ограниченной степени» (2011).
https:/​/​doi.org/​10.1007/​978-3-642-22670-0_9

[30] Чонван Хаах, Арам В. Харроу, Чжэнфэн Цзи, Сяоди Ву и Ненгкун Ю, «Выборочно-оптимальная томография квантовых состояний» IEEE Transactions on Information Theory 63, 1–1 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2719044
Arxiv: 1508.01797
http://​/​ieeexplore.ieee.org/​document/​7956181/​

[31] Арам В. Харроу «Применение когерентной классической коммуникации и преобразования Шура к квантовой теории информации» (2005).
Arxiv: 0512255

[32] Масахито Хаяси, Бао-Сен Ши, Акихиса Томита, Кейджи Мацумото, Ёсиюки Цуда и Юн-Кун Цзян, «Проверка гипотезы запутанного состояния, возникающего в результате спонтанного параметрического понижающего преобразования», Phys. Ред. А 74, 062321 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Масахито Хаяси «Теоретико-групповой подход к квантовой информации» Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-45241-8

[34] Масахито Хаяси «Групповое представление квантовой теории» Springer International Publishing (2017).
https:/​/​doi.org/​10.1007/​978-3-319-44906-7

[35] Масахито Хаяси «Квантовая теория информации» Springer Berlin Heidelberg (2017).
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Масахито Хаяши и Кейджи Мацумото «Квантовое универсальное исходное кодирование переменной длины» Physical Review A 66, 022311 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.66.022311
Arxiv: 0202001

[37] Масахито Хаяши и Марко Томамичел «Обнаружение корреляции и оперативная интерпретация взаимной информации Реньи» Журнал математической физики 57, 102201 (2016).
https: / / doi.org/ 10.1063 / 1.4964755
Arxiv: 1408.6894

[38] Масахито Хаяси, Акихиса Томита и Кейджи Мацумото, «Статистический анализ тестирования запутанного состояния на основе структуры распределения Пуассона», New Journal of Physics 10, 043029 (2008).
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] Л. Хендерсон и В. Ведрал «Классические, квантовые и полные корреляции» Физический журнал A: Mathematical and General 34, 6899–6905 (2001).
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​315
Arxiv: 0105028

[40] М. Кейл «Оценка квантового состояния и большие уклонения» Обзоры по математической физике 18, 19–60 (2006).
https: / / doi.org/ 10.1142 / S0129055X06002565

[41] Фарзад Кианваш, Марко Фаницца и Витторио Джованнетти, «Ограничение квантовой емкости с помощью помеченных расширений» Quantum 6, 647 (2022).
https:/​/​doi.org/​10.22331/​q-2022-02-09-647
Arxiv: 2008.02461

[42] Мартин Клишанд Инго Рот «Теория сертификации квантовых систем» PRX Quantum 2, 010201 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010201
Arxiv: 2010.05925

[43] Хари Крови «Эффективное многомерное квантовое преобразование Шура» Quantum 3, 122 (2019).
https:/​/​doi.org/​10.22331/​q-2019-02-14-122
Arxiv: 1804.00055
https: / / quantum-journal.org/ бумаги / д-2019-02-14-122 /

[44] М. Кейланд Р.Ф. Вернер «Оценка спектра оператора плотности» Physical Review A 64, 052311 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.052311
Arxiv: 0102027

[45] Люсьен Ле Кам «Аппроксимационная теорема для биномиального распределения Пуассона». Тихоокеанский математический журнал 10, 1181–1197 (1960).

[46] Феликс Ледицки, Ниланджана Датта и Грэм Смит, «Полезные состояния и дистилляция запутанности», Транзакции IEEE по теории информации 64, 4689–4708 (2018).
https: / / doi.org/ 10.1109 / TIT.2017.2776907
Arxiv: 1701.03081

[47] Эрих Л. Леманнанд Джозеф П. Романо «Проверка статистических гипотез» Springer Science & Business Media (2006).

[48] Реут Леви, Дана Рон и Ронитт Рубинфельд, «Тестирование свойств наборов распределений» Теория вычислений 9, 295–347 (2013).
https: / / doi.org/ 10.4086 / toc.2013.v009a008
https://theoryofcomputing.org/articles/v009a008

[49] Нетанель Х. Линднер, Петра Ф. Скудо и Дагмар Брус, «Квантовая оценка относительной информации», Международный журнал квантовой информации 4, 131–149 (2006).
https: / / doi.org/ 10.1142 / S0219749906001657
Arxiv: 0506223

[50] Эшли Монтанаро и Рональд де Вольф «Обзор тестирования квантовых свойств» Теория вычислений 1, 1–81 (2016).
https: / / doi.org/ 10.4086 / toc.gs.2016.007
Arxiv: 1310.2035
http://www.theoryofcomputing.org/articles/gs007

[51] Райан О'Доннелланд Джон Райт «Тестирование квантового спектра» Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений, 14–17 июня, 529–538 (2015).
https: / / doi.org/ 10.1145 / 2746539.2746582
Arxiv: 1501.05028

[52] Райан О'Доннелланд Джон Райт «Эффективная квантовая томография» Труды сорок восьмого ежегодного симпозиума ACM по теории вычислений 19-21 июня, 899–912 (2016).
https: / / doi.org/ 10.1145 / 2897518.2897544
Arxiv: 1508.01907

[53] Райан О'Доннелланд Джон Райт «Эффективная квантовая томография II» Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений 962–974 (2017).
https: / / doi.org/ 10.1145 / 3055399.3055454
Arxiv: 1612.00034

[54] Гарольд Оливье и Войцех Зурек «Квантовый диссонанс: мера квантовости корреляций» Physical Review Letters 88, 017901 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.88.017901
Arxiv: 0105072

[55] Лиам Панински «Тест на однородность, основанный на совпадениях, с учетом очень редко выборочных дискретных данных» IEEE Transactions on Information Theory 54, 4750–4755 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928987
http://​/​ieeexplore.ieee.org/​document/​4626074/​

[56] Гаэль Сентис, Джон Кальсамилья и Рамон Муньос-Тапия, «Точная идентификация точки квантового изменения», Physical Review Letters 119 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.140506
Arxiv: 1707.07769

[57] Гаэль Сентис, Эмилио Баган, Джон Кальсамилья, Джулио Чирибелла и Рамон Муньос-Тапия, «Точка квантового изменения», Physical Review Letters 117 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.150502
Arxiv: 1605.01916

[58] Гаэль Сентис, Эстебан Мартинес-Варгас и Рамон Муньос-Тапия, «Онлайн-стратегии для точного определения точки квантового изменения», Physical Review A 98, 052305 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.052305
Arxiv: 1802.00280

[59] Грэм Смит, Джон А. Смолин и Андреас Винтер, «Квантовая емкость с симметричными боковыми каналами», IEEE Transactions on Information Theory 54, 4208–4217 (2008).
https: / / doi.org/ 10.1109 / TIT.2008.928269
Arxiv: 0607039

[60] Игаль Сасон и Серджио Верду «$f$-дивергентные неравенства» Транзакции IEEE по теории информации 62, 5973–6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151
Arxiv: 1508.00335
https://​/​ieeexplore.ieee.org/​document/​7552457/​

[61] Грегори Валиант и Пол Валиант «Автоматическое средство доказательства неравенства и оптимальное тестирование идентичности экземпляров», 2014 г., 55-й ежегодный симпозиум IEEE по основам информатики 51–60 (2014 г.).
https: / / doi.org/ 10.1109 / FOCS.2014.14
https://​/​ieeexplore.ieee.org/​document/​6978989/​

[62] Синь Ван «В поисках фундаментальных ограничений квантовой связи» IEEE Transactions on Information Theory 67, 4524–4532 (2021).
https: / / doi.org/ 10.1109 / TIT.2021.3068818
Arxiv: 1912.00931
https://​/​ieeexplore.ieee.org/​document/​9386074/​

[63] Ненгкун Ю. «Выборочная эффективная проверка идентичности и проверка независимости квантовых состояний» 12-я конференция «Инновации в теоретической информатике» (ITCS 2021) 185, 11:1–11:20 (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.11
Arxiv: 1904.03218
https: / / drops.dagstuhl.de/ opus / volltexte / 2021/13550

[64] Ненгкун Ю. «Анализ сложности почти точной выборки при проверке квантовой идентичности с помощью измерений Паули» IEEE Transactions on Information Theory 69, 5060–5068 (2023).
https: / / doi.org/ 10.1109 / TIT.2023.3271206
Arxiv: 2009.11518

Цитируется

[1] Ли Гао и Ненгкунь Ю, «Выборочная оптимальная томография квантовых цепей Маркова», Arxiv: 2209.02240, (2022).

[2] Марко Фаницца, Михалис Скотиниотис, Джон Калсамилья, Рамон Муньос-Тапия и Гаэль Сентис, «Универсальные алгоритмы обучения квантовых данных», EPL (Письма Еврофизики) 140 2, 28001 (2022).

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-09-13 12:15:37).

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

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

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