1Institut für Quanteninformation und Materie, California Institute of Technology, Pasadena, CA 91125, USA
2Informatik, Tufts University, Medford, MA 02155, USA
Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.
Abstrakt
Das Permanente ist sowohl für die Komplexitätstheorie als auch für die Kombinatorik von zentraler Bedeutung. In der Quanteninformatik erscheint das Permanente im Ausdruck von Ausgangsamplituden linearer optischer Berechnungen, wie z. B. im Boson-Sampling-Modell. Unter Ausnutzung dieser Verbindung liefern wir quanteninspirierte Beweise für viele bestehende sowie neue bemerkenswerte dauerhafte Identitäten. Vor allem geben wir einen quanteninspirierten Beweis des MacMahon-Master-Theorems sowie Beweise für neue Verallgemeinerungen dieses Theorems. Frühere Beweise dieses Theorems verwendeten völlig andere Ideen. Über ihre rein kombinatorischen Anwendungen hinaus demonstrieren unsere Ergebnisse die klassische Härte des exakten und approximativen Samplings von linearen optischen Quantenberechnungen mit eingegebenen Katzenzuständen.
Ausgewähltes Bild: Von Quanten inspirierte Beweise führen zu neuen Komplexitätsergebnissen über Quantenberechnungen mit Eingabe von Katzenzuständen (abstrakte Darstellung, generiert mit DALL.E).
Populäre Zusammenfassung
Indem wir die Beziehungen zwischen der Permanenten und den Amplituden linearer optischer Quantenschaltkreise ausnutzen, zeigen wir, dass quanteninspirierte Techniken schnelle Beweise für viele wichtige Theoreme über die Permanenten liefern, wie z. B. das MacMahon-Master-Theorem.
Unsere quanteninspirierten Beweise bieten dem Quantenwissenschaftler neue Einblicke in kombinatorische Theoreme und decken neue Ergebnisse in der Quantenkomplexität auf.
► BibTeX-Daten
► Referenzen
[1] H. Minc, "Permanents", vol. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, „Kombinatorische Methoden“, vol. 4. Springer Wissenschafts- und Wirtschaftsmedien, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, „Die Komplexität der Berechnung des Permanenten“, Theoretische Informatik 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, „Zur Quantenfeldtheorie – I: explizite Lösung der Dyson-Gleichung in der Elektrodynamik ohne Verwendung von Feynman-Graphen“, Il Nuovo Cimento (1943–1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, „Permanente in linearen optischen Netzwerken“, quant-ph/0406127.
arXiv: quant-ph / 0406127
[6] S. Aaronson und A. Arkhipov, „Die Rechenkomplexität der linearen Optik“, Theory of Computing 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, „Ein linear-optischer Beweis, dass das Permanente # P-hart ist“, 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 und TC Ralph, „Was kann die Quantenoptik über die Berechnungskomplexitätstheorie sagen?“, Physical Review Letters 114, 060501 (2015).
https://doi.org/ 10.1103/PhysRevLett.114.060501
[9] D. Grier und L. Schaeffer, „Neue Härteergebnisse für die Dauerhafte mit linearer Optik“, arXiv:1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes und JP Dowling, „Ein Quantenoptik-Argument für die $#$P-Härte einer Klasse mehrdimensionaler Integrale“, arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf und R. Garcia-Patron, „Quanteninspirierter Algorithmus zur Schätzung der Dauerhaftigkeit positiver semidefiniter Matrizen“, 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, "Kombinatorische Analyse, Bände I und II", vol. 137. American Mathematical Soc., 2001.
[14] I. Good, „Beweise einiger ‚binomialer' Identitäten mittels MacMahons ‚Master Theorem‘“, in 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 MacMahon's master theorem“, SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, „Einige Erweiterungen und Faltungsformeln im Zusammenhang mit MacMahons Hauptsatz“, SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, „Kombinatorische Mathematik“, vol. 14. American Mathematical Society, 1963.
[18] K. Balasubramanian, Kombinatorik und Diagonalen von Matrizen. Doktorarbeit, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, Finite-Differenzen-Algorithmen für Zählprobleme. Doktorarbeit, 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 und JP Dowling, „Beweise für die Vermutung, dass das Abtasten verallgemeinerter Katzenzustände mit linearer Optik schwierig ist“, 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 und S. Lloyd, „Gaußsche Quanteninformation“, Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, „$SU(p, q)$ kohärente Zustände und ein Satz von Gaussian de Finetti“, Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang und Y. Ma, „Abstände zwischen zufälligen orthogonalen Matrizen und unabhängigen Normalen“, arXiv: 1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, „Über die Summe der Kuben der Koeffizienten in einer bestimmten Erweiterung durch den Binomialsatz“, Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, „Ein kurzer Beweis von MacMahons ‚Meistersatz'“, in 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ê und 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 und 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, „Einige Verallgemeinerungen des MacMahon-Master-Theorems“, Journal of Combinatorial Theory, Serie A 120, 92–101 (2013).
https: // doi.org/ 10.1016 / j.jcta.2012.07.007
[30] VV Kocharovsky, VV Kocharovsky und 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 und J. Louck, „Winkelimpulstheorie, Umbralrechnung und Kombinatorik“, Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal und DP DiVincenzo, „Klassische Simulation von nicht wechselwirkenden Fermion-Quantenschaltungen“, Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, „Partielle Ununterscheidbarkeitstheorie für Multiphotonenexperimente in Multiport-Geräten“, Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders und H. de Guise, „Allgemeine Interferenz von Fermionen und Bosonen“, Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin und 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 und 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 und B. Coecke, „Quantum Linear Optics via String Diagrams“, arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh und 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-Katzenzustände im Schaltkreis qed“, arXiv:1710.03179.
arXiv: arXiv: 1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu und F. Nori, „Mikrowellenphotonik mit supraleitenden Quantenschaltkreisen“, Physics Reports 718, 1–102 (2017).
https://doi.org/ 10.1016/j.physrep.2017.10.002
[41] J. Huh, „Ein schneller Quantenalgorithmus zur Berechnung der permanenten Matrix“, arXiv:2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson und T. Hance, „Verallgemeinerung und Derandomisierung des Approximationsalgorithmus von Gurvits für das Permanente“, Quantum Info. Berechnung. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin und J. Huh, „Generalized concurrence in bosonsampling“, Wissenschaftliche Berichte 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao und J. Huh, „Universal gebunden an das Abtasten von Bosonen in der linearen Optik und ihre rechnerischen Implikationen“, National Science Review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, „Zur klassischen Komplexität der Abtastung durch Quanteninterferenz nicht unterscheidbarer Bosonen“, International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, „Die Vereinheitlichung bestimmter Aufzählungsprobleme für Folgen“, Journal of Combinatorial Theory, Reihe A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins und CJ Villas-Boas, „Überlagerung von Zwei-Moden-Squeeze-States für Quanteninformationsverarbeitung und Quantensensorik“, 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 und TC Ralph, „Boson Sampling 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 und JP Dowling, „Sampling willkürlicher Photon-addierter oder Photon-subtrahierter gequetschter Zustände ist in der gleichen Komplexitätsklasse wie Boson-Sampling“, 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 und 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 und T. Ralph, „Exaktes Boson-Sampling mit Gaussian Continuous-Variable-Messungen“, Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan und NJ Cerf, „Boson-Sampling mit Gaußschen Messungen“, 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 und G. Ferrini, „Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeeze States“, Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola und N. Killoran, „Gaußsches Boson-Sampling mit Schwellendetektoren“, 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 -dimensionales Gaußsches Boson-Sampling“, Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Zitiert von
Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.
