1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, ΗΠΑ
2Computer Science, Tufts University, Medford, MA 02155, Η.Π.Α
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Το μόνιμο είναι ζωτικής σημασίας τόσο για τη θεωρία πολυπλοκότητας όσο και για τη συνδυαστική. Στον κβαντικό υπολογισμό, το μόνιμο εμφανίζεται στην έκφραση των πλατών εξόδου των γραμμικών οπτικών υπολογισμών, όπως στο μοντέλο δειγματοληψίας μποζονίων. Εκμεταλλευόμενοι αυτή τη σύνδεση, δίνουμε κβαντικές αποδείξεις για πολλές υπάρχουσες καθώς και νέες αξιόλογες μόνιμες ταυτότητες. Το πιο αξιοσημείωτο είναι ότι δίνουμε μια κβαντική απόδειξη του κύριου θεωρήματος MacMahon καθώς και αποδείξεις για νέες γενικεύσεις αυτού του θεωρήματος. Οι προηγούμενες αποδείξεις αυτού του θεωρήματος χρησιμοποιούσαν εντελώς διαφορετικές ιδέες. Πέρα από τις καθαρά συνδυαστικές εφαρμογές τους, τα αποτελέσματά μας καταδεικνύουν την κλασική σκληρότητα της ακριβούς και κατά προσέγγιση δειγματοληψίας γραμμικών οπτικών κβαντικών υπολογισμών με καταστάσεις γάτας εισόδου.
Προτεινόμενη εικόνα: Οι αποδείξεις εμπνευσμένες από κβαντικά οδηγούν σε νέα αποτελέσματα πολυπλοκότητας σχετικά με τους κβαντικούς υπολογισμούς με την εισαγωγή καταστάσεων γάτας (αφηρημένη απεικόνιση που δημιουργείται χρησιμοποιώντας το DALL.E).
Δημοφιλή περίληψη
Εκμεταλλευόμενοι τις σχέσεις μεταξύ των μόνιμων και των πλάτη των γραμμικών οπτικών κβαντικών κυκλωμάτων, δείχνουμε ότι οι εμπνευσμένες από κβαντικές τεχνικές παρέχουν γρήγορες αποδείξεις πολλών σημαντικών θεωρημάτων σχετικά με το μόνιμο, όπως το Κύριο Θεώρημα MacMahon.
Οι εμπνευσμένες από κβαντικές αποδείξεις μας παρέχουν νέα γνώση για τον κβαντικό επιστήμονα σχετικά με τα συνδυαστικά θεωρήματα και αποκαλύπτουν νέα αποτελέσματα στην κβαντική πολυπλοκότητα.
► Δεδομένα BibTeX
► Αναφορές
[1] H. Minc, “Permanents,”, τόμ. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, «Συνδυαστικές μέθοδοι», τόμ. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, «Η πολυπλοκότητα του υπολογισμού του μόνιμου», Theoretical computer science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, «On quantum field theory—I: ρητή λύση της εξίσωσης του Dyson στην ηλεκτροδυναμική χωρίς χρήση γραφημάτων Feynman», 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] S. Aaronson και 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, «A linear-optical proof that the permanent is# P-hard», 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 και TC Ralph, «Τι μπορεί να πει η κβαντική οπτική για τη θεωρία υπολογιστικής πολυπλοκότητας;», Επιστολές φυσικής ανασκόπησης 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier και L. Schaeffer, «New hardness results for the permanent using linear optics», 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] L. Chakhmakhchyan, NJ Cerf και R. Garcia-Patron, «Κβαντικός αλγόριθμος για την εκτίμηση της μόνιμης θετικών ημικαθοριστικών πινάκων», 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, «Combinatory Analysis, Volumes I and II», τομ. 137. American Mathematical Soc., 2001.
[14] I. Good, «Proofs of some 'binomial'identities by through the MacMahon's Master Theorem'», στο Mathematical Proceedings of the Cambridge Philosophical Society, τόμ. 58, σελ. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, «Application of MacMahon's master theorem», SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, «Μερικοί τύποι επέκτασης και συνέλιξης που σχετίζονται με το κύριο θεώρημα του MacMahon», SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, «Combinatorial mathematics», τομ. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Συνδυαστική και διαγώνιοι πινάκων. Διδακτορική διατριβή, Ινδικό Στατιστικό Ινστιτούτο-Καλκούτα, 1980.
[19] ET Bax, Αλγόριθμοι πεπερασμένων διαφορών για μέτρηση προβλημάτων. Διδακτορική διατριβή, 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 και JP Dowling, «Απόδειξη για την εικασία ότι η δειγματοληψία γενικευμένων καταστάσεων γάτας με γραμμική οπτική είναι δύσκολη», 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 και S. Lloyd, “Gaussian quantum information,” Κριτικές of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, «$SU(p, q)$ συνεκτικές καταστάσεις και θεώρημα Gaussian de Finetti», Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang και Y. Ma, «Αποστάσεις μεταξύ τυχαίων ορθογωνικών πινάκων και ανεξάρτητων κανονικών», arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, «Στο άθροισμα των κύβων των συντελεστών σε μια ορισμένη επέκταση από το διωνυμικό θεώρημα», Messenger of mathematics 20, 79–80 (1891).
[26] I. Good, «A short proof of MacMahon's 'Master Theorem'», στο Mathematical Proceedings of the Cambridge Philosophical Society, vol. 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 και I. Pak, «Μη αντιμεταθετικές επεκτάσεις του Master Theorem MacMahon», 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 και 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 και J. Louck, «Θεωρία γωνιακής ορμής, λογισμός ομφαλικού λογισμού και συνδυαστική», 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] V. Shchesnovich, «Μερική αδιάκριτη θεωρία για πειράματα πολλαπλών φωτονίων σε συσκευές πολλαπλών θυρών», 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] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin, and 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 και 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 και B. Coecke, «Quantum Linear Optics via String Diagrams», arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh, and 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. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu, και F. Nori, «Φωτονική μικροκυμάτων με υπεραγώγιμα κβαντικά κυκλώματα», 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] S. Aaronson και T. Hance, «Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent», Quantum Info. Υπολογιστής. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin και J. Huh, «Γενικευμένη σύμπτωση στη δειγματοληψία μποζονίων», Επιστημονικές αναφορές 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] Μ.-Η. Yung, X. Gao και J. Huh, «Universal bound on sampling bosons in linear optics and its computational implications», National Science Review 6, 719–729 (2019).
https://doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, «Σχετικά με την κλασική πολυπλοκότητα της δειγματοληψίας από κβαντική παρεμβολή δυσδιάκριτων μποζονίων», International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, «Η ενοποίηση ορισμένων προβλημάτων απαρίθμησης για ακολουθίες», 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 και CJ Villas-Boas, «Superposition of two-mode squeezed states for quantum information processing and quantum sensing», 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 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 και JP Dowling, "Η δειγματοληψία αυθαίρετων συμπιεσμένων καταστάσεων με προσθήκη φωτονίων ή με αφαίρεση φωτονίων βρίσκεται στην ίδια κατηγορία πολυπλοκότητας με τη δειγματοληψία μποζονίων", 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. Jex, "Gaussian boson sampling," Φυσική επισκόπηση επιστολών 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari και T. Ralph, «Ακριβής δειγματοληψία μποζονίων με χρήση μετρήσεων συνεχούς μεταβλητής Gaussian», Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan και NJ Cerf, «Δειγματοληψία μποζονίων με μετρήσεις Gaussian», 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, «Συνεχής-μεταβλητή δειγματοληψία από καταστάσεις συμπιεσμένων καταστάσεων με προσθήκη φωτονίων ή με αφαίρεση φωτονίων», Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola και N. Killoran, «Δειγματοληψία μποζονίων Gauss using threshold detectors», 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 plus via high -διάστατη δειγματοληψία μποζονίων Gauss," Science advances 8, 7894 (2022).
https://doi.org/10.1126/sciadv.abi7894
Αναφέρεται από
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
