1Instytut Informacji Kwantowej i Materii, California Institute of Technology, Pasadena, CA 91125, USA
2Informatyka, Tufts University, Medford, MA 02155, USA
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Trwałość jest kluczowa zarówno dla teorii złożoności, jak i dla kombinatoryki. W obliczeniach kwantowych permanent pojawia się w wyrażeniu wyjściowych amplitud liniowych obliczeń optycznych, takich jak model Boson Sampling. Korzystając z tego połączenia, przedstawiamy inspirowane kwantami dowody wielu istniejących, jak również nowych niezwykłych trwałych tożsamości. Przede wszystkim podajemy inspirowany kwantami dowód twierdzenia MacMahona, a także dowody nowych uogólnień tego twierdzenia. Poprzednie dowody tego twierdzenia wykorzystywały zupełnie inne idee. Oprócz ich czysto kombinatorycznych zastosowań, nasze wyniki pokazują klasyczną twardość dokładnego i przybliżonego próbkowania liniowych optycznych obliczeń kwantowych z wejściowymi stanami kota.
Wyróżniony obraz: Dowody inspirowane kwantami prowadzą do nowych wyników złożoności obliczeń kwantowych z wprowadzaniem stanów kota (abstrakcyjne przedstawienie wygenerowane przy użyciu DALL.E).
Popularne podsumowanie
Wykorzystując relacje między trwałością a amplitudami liniowych optycznych obwodów kwantowych, pokazujemy, że techniki inspirowane kwantami dostarczają szybkich dowodów wielu ważnych twierdzeń dotyczących trwałości, takich jak twierdzenie MacMahona.
Nasze dowody inspirowane kwantami dostarczają naukowcom zajmującym się kwantami nowego wglądu w twierdzenia kombinatoryczne i odkrywają nowe wyniki w złożoności kwantowej.
► Dane BibTeX
► Referencje
[1] H. Minc, „Permanenty”, tom. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, „Metody kombinatoryczne”, tom. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, „Złożoność obliczeń stałych”, Informatyka teoretyczna 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, „O kwantowej teorii pola - I: wyraźne rozwiązanie równania Dysona w elektrodynamice bez użycia wykresów Feynmana”, Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, „Permanenty w liniowych sieciach optycznych”, quant-ph/0406127.
arXiv: quant-ph / 0406127
[6] S. Aaronson i A. Arkhipov, „Złożoność obliczeniowa optyki liniowej”, Theory of Computing 9, 143 (2013), arXiv: 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, „Liniowo-optyczny dowód, że permanent jest # P-twardy”, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
[8] S. Rahimi-Keshari, AP Lund i TC Ralph, „Co optyka kwantowa może powiedzieć o teorii złożoności obliczeniowej?”, Fizyczne listy przeglądowe 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier i L. Schaeffer, „Nowe wyniki twardości dla trwałej optyki liniowej”, arXiv: 1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes i JP Dowling, „Argument optyki kwantowej dla twardości P $ # $ klasy całek wielowymiarowych”, arXiv: 1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf i R. Garcia-Patron, „Algorytm inspirowany kwantami do szacowania trwałości dodatnich macierzy półokreślonych”, Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, „Niezbliżenie dodatnich półokreślonych stałych i kwantowej tomografii państwowej”, arXiv: 2111.03142.
arXiv: arXiv: 2111.03142
[13] PA MacMahon, „Analiza kombinacyjna, tomy I i II”, tom. 137. American Mathematical Soc., 2001.
[14] I. Good, „Dowody niektórych„ dwumianowych ”tożsamości za pomocą „Master Theorem” MacMahona, w Mathematical Proceedings of the Cambridge Philosophical Society, tom. 58, s. 161–162, Cambridge University Press. 1962.
https: // doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, „Zastosowanie twierdzenia głównego MacMahona”, SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, „Niektóre rozwinięcia i formuły splotu związane z twierdzeniem głównym MacMahona”, SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, „Matematyka kombinatoryczna”, tom. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Kombinatoryka i przekątne macierzy. Praca doktorska, Indyjski Instytut Statystyczny-Kalkuta, 1980.
[19] ET Bax, Algorytmy różnic skończonych w problemach zliczania. Praca doktorska, California Institute of Technology, 1998.
[20] DG Glynn, „The permanent of a square matrix”, 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 i JP Dowling, „Dowody na przypuszczenie, że próbkowanie uogólnionych stanów kotów za pomocą optyki liniowej jest trudne”, 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 i 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) $ spójne stany i twierdzenie Gaussa de Finettiego”, Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang i Y. Ma, „Odległości między losowymi macierzami ortogonalnymi a niezależnymi normalnymi”, arXiv: 1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, „O sumie sześcianów współczynników w pewnym rozwinięciu przez twierdzenie dwumianowe”, Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, „Krótki dowód „Master Theorem” MacMahona, w Mathematical Proceedings of the Cambridge Philosophical Society, tom. 58, s. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, TT Lê i D. Zeilberger, „Kwantowe twierdzenie MacMahona”, Proceedings of the National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[28] M. Konvalinka i 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, „Niektóre uogólnienia twierdzenia MacMahona Master”, Journal of Combinatorial Theory, Series A 120, 92–101 (2013).
https:///doi.org/10.1016/j.jcta.2012.07.007
[30] VV Kocharovsky, VV Kocharovsky i SV Tarasov, „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 i J. Louck, „Teoria momentu pędu, rachunek umbralny i kombinatoryka”, Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal i DP DiVincenzo, „Klasyczna symulacja nieoddziałujących obwodów kwantowych fermionów”, Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, „Teoria częściowej nierozróżnialności dla eksperymentów wielofotonowych w urządzeniach wieloportowych”, Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders i H. de Guise, „Uogólniona interferencja fermionów i bozonów”, Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin i M. Hafezi, „Pobieranie próbek bozonu dla uogólnionych bozonów”, 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 i B. Valiron, „LO $ _text{v} $-Calculus: język graficzny dla liniowych optycznych obwodów kwantowych”, arXiv: 2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787
[37] G. De Felice i B. Coecke, „Kwantowa optyka liniowa za pomocą diagramów strun”, arXiv: 2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh i A. Aspuru-Guzik, „Propozycja próbkowania bozonu mikrofalowego”, listy z przeglądem fizycznym 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] S. Girvin, „Stany kota Schrödingera w obwodzie qed”, arXiv: 1710.03179.
arXiv: arXiv: 1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu i F. Nori, „Fotonika mikrofalowa z nadprzewodzącymi obwodami kwantowymi”, Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, „Szybki algorytm kwantowy do obliczania stałej macierzy”, arXiv: 2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson i T. Hance, „Uogólnianie i derandomizacja algorytmu aproksymacji Gurvitsa na stałe”, Quantum Info. Oblicz. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin i J. Huh, „Uogólniona zbieżność w próbkowaniu bozonu”, Raporty naukowe 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao i J. Huh, „Uniwersalne wiązanie bozonów próbkowania w optyce liniowej i ich implikacje obliczeniowe”, National Science Review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, „O klasycznej złożoności próbkowania z interferencji kwantowej nieodróżnialnych bozonów”, International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, „Ujednolicenie pewnych problemów wyliczania dla sekwencji”, Journal of Combinatorial Theory, Series A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins i CJ Villas-Boas, „Superpozycja stanów ściśniętych w dwóch trybach do przetwarzania informacji kwantowych i wykrywania kwantowego”, Przegląd fizyczny 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 i TC Ralph, „Próbkowanie bozonu ze stanu Gaussa”, listy z przeglądem fizycznym 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde i JP Dowling, „Próbkowanie dowolnych stanów ściśniętych z dodanymi lub odjętymi fotonami jest w tej samej klasie złożoności, co próbkowanie bozonu”, 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 i I. Jex, „Pobieranie próbek bozonów Gaussa”, Fizyczne listy przeglądowe 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari i T. Ralph, „Dokładne próbkowanie bozonu za pomocą pomiarów ciągłej zmiennej Gaussa”, Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan i NJ Cerf, „Pobieranie próbek bozonów z pomiarami Gaussa”, 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 i G. Ferrini, „Ciągłe pobieranie próbek z dodanych lub odjętych fotonów w stanach ściśniętych”, Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola i N. Killoran, „Próbkowanie bozonu gaussowskiego za pomocą detektorów progowych”, 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 i in., „Kwantowa przewaga obliczeniowa dzięki wysokiej -wymiarowe próbkowanie bozonu Gaussa”, Science progresss 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Cytowany przez
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
