1Институт квантовой информации и вещества, Калифорнийский технологический институт, Пасадена, Калифорния 91125, США
2Информатика, Университет Тафтса, Медфорд, Массачусетс 02155, США
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Перманент имеет ключевое значение как для теории сложности, так и для комбинаторики. В квантовых вычислениях перманент появляется в выражении выходных амплитуд линейных оптических вычислений, например, в модели Boson Sampling. Воспользовавшись этой связью, мы даем квантовые доказательства многих существующих, а также новых замечательных постоянных тождеств. В частности, мы даем квантовое доказательство основной теоремы Мак-Магона, а также доказательства новых обобщений этой теоремы. В предыдущих доказательствах этой теоремы использовались совершенно другие идеи. Помимо их чисто комбинаторных приложений, наши результаты демонстрируют классическую сложность точной и приблизительной выборки линейных оптических квантовых вычислений с входными состояниями кота.
Рекомендуемое изображение: Доказательства, вдохновленные квантовой механикой, приводят к новым результатам сложности квантовых вычислений с вводом состояний кошки (абстрактное изображение, созданное с помощью DALL.E).
Популярное резюме
Используя взаимосвязь между перманентом и амплитудами линейных оптических квантовых цепей, мы показываем, что методы, вдохновленные квантовой механикой, обеспечивают быстрые доказательства многих важных теорем о перманенте, таких как главная теорема Мак-Магона.
Наши основанные на квантовых вычислениях доказательства дают квантовым ученым новое представление о комбинаторных теоремах и раскрывают новые результаты в области квантовой сложности.
► Данные BibTeX
► Рекомендации
[1] Х. Минк, «Перманенты», том. 6. Издательство Кембриджского университета, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] Дж. К. Перкус, «Комбинаторные методы», том. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] Л. Г. Валиант, «Сложность вычисления перманента», Теоретическая информатика, 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] Э. Р. Кайаниелло, «Квантовая теория поля — I: явное решение уравнения Дайсона в электродинамике без использования графов Фейнмана», Il Nuovo Cimento (1943–1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] С. Шил, «Постоянные в линейных оптических сетях», quant-ph/0406127.
Arxiv: колич-фот / 0406127
[6] С. Ааронсон и А. Архипов, «Вычислительная сложность линейной оптики», Теория вычислений, 9, 143 (2013), arXiv: 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
Arxiv: Arxiv: 1011.3245
[7] С. Ааронсон, «Линейно-оптическое доказательство того, что перманент является # P-трудным», Труды Королевского общества A: Mathematical, Physical and Engineering Sciences 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
[8] С. Рахими-Кешари, А. П. Лунд и Т. С. Ральф, «Что квантовая оптика может сказать о теории сложности вычислений?», Письма с физическим обзором 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] Д. Гриер и Л. Шеффер, «Новые результаты твердости перманента с использованием линейной оптики», arXiv:1610.04670.
Arxiv: Arxiv: 1610.04670
[10] Роде П.П., Берри Д.В., Моутс К.Р. и Доулинг Дж.П., «Аргумент квантовой оптики в пользу $#$P-твердости класса многомерных интегралов», arXiv:1607.04960.
Arxiv: Arxiv: 1607.04960
[11] Л. Чахмахчян, Н. Дж. Серф и Р. Гарсия-Патрон, «Квантовый алгоритм для оценки перманента положительно-полуопределенных матриц», Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] А. Мейбург, «Неаппроксимируемость положительно полуопределенных перманентов и квантовая томография состояний», arXiv: 2111.03142.
Arxiv: Arxiv: 2111.03142
[13] П.А. МакМахон, «Комбинационный анализ, тома I и II», том. 137. Американская математическая ассоциация, 2001.
[14] И. Гуд, «Доказательства некоторых «биномиальных» тождеств с помощью «Основной теоремы» Мак-Магона», в Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, стр. 161–162, издательство Кембриджского университета. 1962 год.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] Л. Карлиц, «Применение основной теоремы Мак-Магона», SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] Л. Карлиц, «Некоторые формулы расширения и свертки, связанные с основной теоремой Мак-Магона», SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, «Комбинаторная математика», vol. 14. Американская математическая ассоциация, 1963.
[18] К. Баласубраманян, Комбинаторика и диагонали матриц. Кандидатская диссертация, Индийский статистический институт, Калькутта, 1980 г.
[19] ET Bax, Конечно-разностные алгоритмы для задач подсчета. Кандидатская диссертация, Калифорнийский технологический институт, 1998 г.
[20] Д. Глинн, «Перманент квадратной матрицы», European Journal of Combinatorics 31, 1887–1891 (2010).
https: // doi.org/ 10.1016 / j.ejc.2010.01.010
[21] PP Rohde, KR Motes, PA Knott, J. Fitzsimons, WJ Munro и JP Dowling, «Доказательства гипотезы о том, что выборка обобщенных состояний кошки с помощью линейной оптики сложна», Physical Review A 91, 012342 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.012342
[22] К. Видбрук, С. Пирандола, Р. Гарсия-Патрон, Н. Дж. Серф, Т. К. Ральф, Дж. Х. Шапиро и С. Ллойд, «Гауссова квантовая информация», Обзоры современной физики 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] А. Леверье, “Когерентные состояния $SU(p, q)$ и теорема Гаусса де Финетти”, Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] Т. Цзян и Ю. Ма, «Расстояния между случайными ортогональными матрицами и независимыми нормалями», arXiv:1704.05205.
Arxiv: Arxiv: 1704.05205
[25] А. С. Диксон, «О сумме кубов коэффициентов в некотором разложении по биномиальной теореме», Вестник математики, 20, 79–80 (1891).
[26] И. Гуд, «Краткое доказательство «Главной теоремы» Мак-Магона», в Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, стр. 160–160, издательство Кембриджского университета. 1962 год.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] С. Гаруфалидис, Т. Т. Ле и Д. Зейлбергер, «Основная квантовая теорема Мак-Магона», Труды Национальной академии наук, 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[28] М. Конвалинка и И. Пак, «Некоммутативные расширения основной теоремы Мак-Магона», Успехи в области математики, 216, 29–61 (2007).
https: / / doi.org/ 10.1016 / j.aim.2007.05.020
[29] MP Tuite, «Некоторые обобщения основной теоремы Мак-Магона», Journal of Combinatorial Theory, Series A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
[30] Кочаровский В.В., Кочаровский В.В., Тарасов С.В. Основная теорема Гафния // Линейная алгебра и ее приложения. 144. Т. 161–2022.
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[31] В. Я. Чен, Х. Гэлбрейт и Дж. Лук, «Теория углового момента, теневое исчисление и комбинаторика», Компьютеры и математика с приложениями 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal и DP DiVincenzo, "Классическое моделирование квантовых схем невзаимодействующих фермионов", Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] В. Щеснович, «Теория частичной неразличимости для многофотонных экспериментов в многопортовых устройствах», Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] Д. Спивак, М.Ю. Ниу, Б.С. Сандерс и Х. де Гиз, «Обобщенная интерференция фермионов и бозонов», Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] Э.-Дж. Куо, Ю. Сюй, Д. Ханглитер, А. Гранкин и М. Хафези, «Выборка бозонов для обобщенных бозонов», arXiv: 2204.08389.
https: / / doi.org/ 10.1103 / PhysRevResearch.4.043096
Arxiv: Arxiv: 2204.08389
[36] Клеман А., Хертель Н., Мэнсфилд С., Пердрикс С. и Валирон Б. «LO$_text{v}$-исчисление: графический язык для линейных оптических квантовых схем», arXiv:2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
Arxiv: Arxiv: 2204.11787
[37] Г. Де Феличе и Б. Коке, «Квантовая линейная оптика с помощью струнных диаграмм», arXiv: 2204.12985.
Arxiv: Arxiv: 2204.12985
[38] Б. Перопадре, Г.Г. Геррески, Дж. Хух и А. Аспуру-Гузик, «Предложение по выборке микроволновых бозонов», Письма с физическим обзором 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] С. Гирвин, «Состояния кота Шредингера в схеме qed», arXiv: 1710.03179.
Arxiv: Arxiv: 1710.03179
[40] X. Гу, А. Ф. Кокум, А. Миранович, Ю.-х. Лю и Ф. Нори, «Микроволновая фотоника со сверхпроводящими квантовыми схемами», Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, «Быстрый квантовый алгоритм для вычисления постоянной матрицы», arXiv: 2205.01328.
Arxiv: Arxiv: 2205.01328
[42] С. Ааронсон и Т. Ханс, «Обобщение и дерандомизация алгоритма приближения Гурвица для перманента», Quantum Info. вычисл. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] С. Чин и Дж. Ху, «Общее совпадение в выборке бозонов», Научные отчеты 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] М.-Х. Юнг, X. Гао и Дж. Ху, «Универсальная граница выборки бозонов в линейной оптике и ее вычислительные последствия», Национальный научный обзор 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] В. С. Щеснович, «О классической сложности выборки из квантовой интерференции неразличимых бозонов», Международный журнал квантовой информации 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] Д. М. Джексон, «Унификация некоторых задач перечисления последовательностей», Журнал комбинаторной теории, серия A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] Ф. Р. Кардосо, Д. З. Россатто, Г. П. Фернандес, Г. Хиггинс и С. Дж. Виллаш-Боас, «Суперпозиция двухрежимных сжатых состояний для обработки квантовой информации и квантового восприятия», Physical Review A 103, 062405 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.062405
[48] А. П. Лунд, А. Лэнг, С. Рахими-Кешари, Т. Рудольф, Дж. Л. О'Брайен и Т. С. Ральф, «Выборка бозонов из гауссовского состояния», Письма с физическим обзором 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] Дж. П. Олсон, К. П. Сешадрисан, К. Р. Мотес, П. П. Роде и Дж. П. Доулинг, «Выборка произвольных сжатых состояний с добавлением или вычитанием фотонов относится к тому же классу сложности, что и выборка бозонов», Physical Review A 91, 022317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.022317
[50] К.С. Гамильтон, Р. Круз, Л. Сансони, С. Баркхофен, К. Зильберхорн и И. Йекс, «Выборка гауссовских бозонов», Physical Review Letters 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] А. Лунд, С. Рахими-Кешари и Т. Ральф, «Точная выборка бозонов с использованием гауссовых измерений непрерывной переменной», Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] Л. Чахмахчян и Н. Дж. Серф, «Выборка бозонов с гауссовскими измерениями», Physical Review A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
[53] У. Шабо, Т. Дус, Д. Маркхэм, П. ван Лоок, Э. Кашефи и Г. Феррини, «Непрерывная выборка из сжатых состояний с добавлением или вычитанием фотонов», Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] Н. Кесада, Дж. М. Аррасола и Н. Киллоран, «Выборка гауссовых бозонов с использованием пороговых детекторов», Physical Review A 98, 062322 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.062322
[55] А. Дешпанде, А. Мехта, Т. Винсент, Н. Кесада, М. Хинше, М. Иоанну, Л. Мэдсен, Дж. Лавуа, Х. Ци, Дж. Эйзерт и др., «Квантовые вычислительные преимущества за счет высокой -мерная выборка гауссовых бозонов», Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Цитируется
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
