1Institute for Quantum Information and Matter, Kalifornien Institute of Technology, Pasadena, CA 91125, USA
2Datavetenskap, Tufts University, Medford, MA 02155, USA
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Den permanenta är central för både komplexitetsteori och kombinatorik. Vid kvantberäkning uppträder det permanenta i uttrycket av utgångsamplituder för linjära optiska beräkningar, såsom i Boson Sampling-modellen. Genom att dra fördel av denna koppling ger vi kvantinspirerade bevis på många befintliga såväl som nya anmärkningsvärda permanenta identiteter. Framför allt ger vi ett kvantinspirerat bevis på MacMahons mastersats samt bevis för nya generaliseringar av denna sats. Tidigare bevis för detta teorem använde helt andra idéer. Utöver deras rent kombinatoriska applikationer visar våra resultat den klassiska hårdheten för exakt och ungefärlig sampling av linjära optiska kvantberäkningar med inmatade katttillstånd.
Utvald bild: Kvantinspirerade bevis leder till nya komplexitetsresultat om kvantberäkningar med indata för katttillstånd (abstrakt skildring genererad med DALL.E).
Populär sammanfattning
Genom att utnyttja relationerna mellan de permanenta och amplituderna hos linjära optiska kvantkretsar visar vi att kvantinspirerade tekniker ger snabba bevis på många viktiga satser om det permanenta, såsom MacMahon Master Theorem.
Våra kvantinspirerade bevis ger ny insikt för kvantforskaren om kombinatoriska teorem och avslöjar nya resultat i kvantkomplexitet.
► BibTeX-data
► Referenser
[1] H. Minc, "Permanents", vol. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, "Kombinatoriska metoder", vol. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, "The complexity of computing the permanent", Theoretical computer science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, "Om kvantfältteori - I: explicit lösning av Dysons ekvation i elektrodynamik utan användning av Feynman-grafer," Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, "Permanenter i linjära optiska nätverk," quant-ph/0406127.
arXiv: kvant-ph / 0406127
[6] S. Aaronson och A. Arkhipov, "The computational Complexity of Linear Optics," Theory of Computing 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, "Ett linjärt-optiskt bevis på att det permanenta är # P-hårt," 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 och TC Ralph, "Vad kan kvantoptik säga om beräkningskomplexitetsteori?" Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier och L. Schaeffer, "Ny hårdhet resulterar för permanent med linjär optik," arXiv:1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes och JP Dowling, "A Quantum Optics Argument for the $#$P-hardness of a Class of Multidimensional Integrals," arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf och R. Garcia-Patron, "Kvantinspirerad algoritm för att uppskatta permanenta positiva semidefinita matriser," Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, "Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography," arXiv:2111.03142.
arXiv: arXiv: 2111.03142
[13] PA MacMahon, "Kombinatorisk analys, volymer I och II", vol. 137. American Mathematical Soc., 2001.
[14] I. Good, "Bevis för vissa 'binomial' identiteter med hjälp av MacMahons 'Master Theorem'," i Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, s. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, "An application of MacMahons master theorem," SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, "Några expansioner och faltningsformler relaterade till MacMahons mastersats," SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, "Kombinatorisk matematik", vol. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Combinatorics and diagonals of matrices. Doktorsavhandling, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, algoritmer med ändlig skillnad för räkneproblem. Doktorsavhandling, 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 och JP Dowling, "Bevis för gissningen att provtagning av generaliserade katttillstånd med linjär optik är svårt," Physical Review A 91, 012342 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.012342
[22] C. Weedbrook, S. Pirandola, R. García-Patrón, NJ Cerf, TC Ralph, JH Shapiro och S. Lloyd, ”Gaussian quantum information,” Recensioner av modern fysik 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, "$SU(p, q)$ koherenta tillstånd och ett Gaussian de Finetti-teorem," Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang och Y. Ma, "Avstånd mellan slumpmässiga ortogonala matriser och oberoende normaler," arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, "Om summan av kuberna av koefficienterna i en viss expansion av binomialsatsen," Messenger of Mathematics 20, 79–80 (1891).
[26] I. Bra, "Ett kort bevis på MacMahons 'Master Theorem'," i Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, s. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, TT Lê och 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 och 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] VV Kocharovsky, VV Kocharovsky och SV Tarasov, "The Hafnian Master Theorem," Linjär algebra och dess tillämpningar 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[31] WY Chen, H. Galbraith och 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 och DP DiVincenzo, ”Klassisk simulering av icke interagerande fermion kvantkretsar,” Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, "Delvis omöjlighetsteori för multifotonexperiment i multiportenheter," Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders och H. de Guise, "Generalized interference of fermions and bosons," Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin och M. Hafezi, "Boson Sampling for Generalized Bosons," 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 och 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] G. De Felice och B. Coecke, "Quantum Linear Optics via String Diagrams," arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh och A. Aspuru-Guzik, "Förslag till mikrovågsbosonprovtagning," 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. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu och F. Nori, "Mikrovågsfotonik med supraledande kvantkretsar," Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, "En snabb kvantalgoritm för beräkning av permanent matris," arXiv:2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson och T. Hance, "Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent," Quantum Info. Comput. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin och J. Huh, "Generalized concurrence in boson sampling," Scientific reports 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao och J. Huh, "Universal bound on sampling bosons in linear optics and its computational implikations," National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, "Om den klassiska komplexiteten av sampling från kvantinterferens av oskiljbara bosoner," International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, "Förenandet av vissa uppräkningsproblem för sekvenser", 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 och CJ Villas-Boas, "Superposition av tvåläges pressade tillstånd för kvantinformationsbehandling och kvantavkänning," 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 och TC Ralph, "Bosonsampling from a Gaussian state," Physical review letters 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde och JP Dowling, "Sampling av godtyckliga foton-adderade eller foton-subtraherade pressade tillstånd är i samma komplexitetsklass som bosonsampling," 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 och I. Jex, ”Gaussian boson sampling,” Physical review letters 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari och T. Ralph, "Exakt bosonprovtagning med Gaussiska kontinuerliga variabla mätningar," Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan och NJ Cerf, "Bosonsampling with Gaussian measurements," 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 och G. Ferrini, "Continuous-variable sampling from photon-added or photon-subtracted squeezed states," Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola och N. Killoran, "Gaussisk bosonsampling med hjälp av tröskeldetektorer," 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, et al., "Quantum computational advantage via high -dimensionell Gaussisk bosonsampling,” Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Citerad av
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
