Квантові постійні ідентифікатори

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

читають: 0

Улісс Шабо¹, Абхінав Дешпанде¹ та Саїд Мехрабан²

¹Інститут квантової інформації та матерії, Каліфорнійський технологічний інститут, Пасадена, Каліфорнія 91125, США
²Інформатика, Університет Тафтса, Медфорд, Массачусетс 02155, США

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

абстрактний

Перманент має ключове значення як для теорії складності, так і для комбінаторики. У квантових обчисленнях перманент з’являється у виразі вихідних амплітуд лінійних оптичних обчислень, наприклад у моделі бозонної вибірки. Використовуючи переваги цього зв’язку, ми надаємо квантові докази багатьох існуючих, а також нових видатних постійних ідентичностей. Зокрема, ми надаємо квантовий доказ головної теореми МакМагона, а також докази нових узагальнень цієї теореми. Попередні докази цієї теореми використовували зовсім інші ідеї. Окрім суто комбінаторних застосувань, наші результати демонструють класичну жорсткість точної та наближеної вибірки лінійних оптичних квантових обчислень із вхідними котячими станами.

Рекомендоване зображення: натхненні квантовими доказами ведуть до нових складних результатів щодо квантових обчислень із введенням котячих станів (абстрактне зображення, створене за допомогою DALL.E).

► Дані BibTeX

@article{Chabaud2022quantuminspired, doi = {10.22331/q-2022-12-19-877}, url = {https://doi.org/10.22331/q-2022-12-19-877}, title = {Постійні ідентичності, натхненні квантовими}, автор = {Шабо, Улісс і Дешпанде, Абхінав і Мехрабан, Саїд}, журнал = {{Quantum}}, issn = {2521-327X}, видавець = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, обсяг = {6}, сторінок = {877}, місяць = грудень, рік = {2022} }

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

[1] H. Minc, “Permanents”, vol. 6. Cambridge University Press, 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] ER Caianiello, “Про квантову теорію поля—I: явне розв’язання рівняння Дайсона в електродинаміці без використання графів Фейнмана”, Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659

[5] S. Scheel, «Постійні елементи в лінійних оптичних мережах», quant-ph/0406127.
arXiv: quant-ph / 0406127

[6] С. Ааронсон і А. Архіпов, «Обчислювальна складність лінійної оптики», Теорія обчислень 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv:arXiv:1011.3245

[7] С. Ааронсон, «Лінійно-оптичний доказ того, що перманент # P-твердий», Праці Королівського товариства A: Математичні, фізичні та інженерні науки 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232

[8] S. Rahimi-Keshari, AP Lund і TC Ralph, «Що квантова оптика може сказати про теорію складності обчислень?», Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501

[9] D. Grier і L. Schaeffer, «Нові результати твердості для перманенту за допомогою лінійної оптики», arXiv:1610.04670.
arXiv:arXiv:1610.04670

[10] PP Rohde, DW Berry, KR Motes і JP Dowling, «A Quantum Optics Argument for the $#$P-hardness of a Class of Multidimensional Integrals», 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] PA MacMahon, “Combinatory Analysis, Volume I and II”, vol. 137. American Mathematical Soc., 2001.

[14] І. Гуд, «Докази деяких «біноміальних» тотожностей за допомогою «Головної теореми» МакМагона», у Математичних матеріалах Кембриджського філософського товариства, том. 58, стор. 161–162, Cambridge University Press. 1962 рік.
https:///doi.org/10.1017/S030500410003632X

[15] L. Carlitz, “An application of MacMahon's master theorem,” SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040

[16] Л. Карлітц, «Деякі розкладання та формули згортки, пов’язані з головною теоремою Мак-Магона», Журнал SIAM про математичний аналіз 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023

[17] Г. Дж. Райзер, “Комбінаторна математика”, том. 14. Американське математичне товариство, 1963.

[18] К. Баласубраманян, Комбінаторика та діагоналі матриць. Докторська дисертація, Індійський статистичний інститут, Колката, 1980.

[19] Е.Т. Бакс, Скінченно-різничні алгоритми для задач підрахунку. Докторська дисертація, Каліфорнійський технологічний інститут, 1998.

[20] DG Glynn, “Перманент квадратної матриці”, 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] C. Weedbrook, S. Pirandola, R. García-Patron, NJ Cerf, TC Ralph, JH Shapiro, and S. Lloyd, “Gaussian quantum information”, Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621

[23] A. Leverrier, “$SU(p, q)$ coherent states and a Gaussian de Finetti theorem”, Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334

[24] Т. Цзян і Ю. Ма, «Відстані між випадковими ортогональними матрицями та незалежними нормалями», arXiv:1704.05205.
arXiv:arXiv:1704.05205

[25] AC Dixon, “Про суму кубів коефіцієнтів у певному розкладі за біноміальною теоремою”, Messenger of mathematics 20, 79–80 (1891).

[26] І. Гуд, «Короткий доказ «Головної теореми» МакМагона», у Математичних матеріалах Кембриджського філософського товариства, том. 58, стор. 160–160, Cambridge University Press. 1962 рік.
https: / / doi.org/ 10.1017 / S0305004100036318

[27] S. Garoufalidis, TT Lê, and D. Zeilberger, “The quantum MacMahon master theorem,” Proceedings of the National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103

[28] M. Konvalinka and I. Pak, “Non-commutative extensions of the MacMahon Master Theorem”, Advances in Mathematics 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020

[29] MP Tuite, “Some generalizations of the MacMahon Master Theorem,” Journal of Combinatorial Theory, Series A 120, 92–101 (2013).
https:///doi.org/10.1016/j.jcta.2012.07.007

[30] В. В. Кочаровський, В. В. Кочаровський і С. В. Тарасов, “The Hafnian Master Theorem”, Linear Algebra and its Applications 144–161 (2022).
https:///doi.org/10.1016/j.laa.2022.06.021

[31] WY Chen, H. Galbraith, and J. Louck, “Angular momentum Theory, umbral calculus, and combinatorics,” Computers & Mathematics with Applications 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] D. Spivak, MY Niu, BC Sanders і H. de Guise, «Узагальнена інтерференція ферміонів і бозонів», Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013

[35] Е.-Ж. Kuo, Y. Xu, D. Hangleiter, A. Grankin і M. Hafezi, «Відбір бозонів для узагальнених бозонів», arXiv:2204.08389.
https: / / doi.org/ 10.1103 / PhysRevResearch.4.043096
arXiv:arXiv:2204.08389

[36] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix і B. Valiron, “LO$_text{v}$-Calculus: A Graphical Language for Linear Optical Quantum Circuits”, 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] B. Peropadre, GG Guerreschi, J. Huh та A. Aspuru-Guzik, “Proposal for microwave boson sampling”, Physical review letters 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505

[39] S. Girvin, “Schrödinger cat states in circuit 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] Дж. Ху, «Швидкий квантовий алгоритм для обчислення перманенту матриці», arXiv:2205.01328.
arXiv:arXiv:2205.01328

[42] С. Ааронсон і Т. Хенс, «Узагальнення та дерандомізація алгоритму апроксимації Гурвітса для постійного», Квантова інформація. обчис. 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] М.-Х. Yung, X. Gao, and J. Huh, “Universal bound on sempling bosons in linear optics and its computational implications”, National science review 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] AP Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, JL O'Brien, and TC Ralph, “Boson sempling from a Gaussian state,” Physical review letters 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] CS Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, “Gaussian boson sampling”, 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] U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi, and G. Ferrini, “Continuous-variable sempling from photon added or photon subtracted squeezed states”, 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] A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert та ін., «Квантова обчислювальна перевага через високий рівень -вимірна дискретизація бозона Гаусса», Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894

Цитується

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