1Istituto per l'informazione e la materia quantistica, California Institute of Technology, Pasadena, CA 91125, USA
2Informatica, Tufts University, Medford, MA 02155, USA
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Il permanente è fondamentale sia per la teoria della complessità che per la combinatoria. Nel calcolo quantistico, il permanente appare nell'espressione delle ampiezze di output dei calcoli ottici lineari, come nel modello Boson Sampling. Approfittando di questa connessione, diamo prove di ispirazione quantistica di molte identità esistenti e nuove notevoli identità permanenti. In particolare, forniamo una dimostrazione ispirata ai quanti del teorema principale di MacMahon, nonché prove per nuove generalizzazioni di questo teorema. Le precedenti dimostrazioni di questo teorema usavano idee completamente diverse. Al di là delle loro applicazioni puramente combinatorie, i nostri risultati dimostrano la durezza classica del campionamento esatto e approssimativo di calcoli quantistici ottici lineari con stati cat di input.
Immagine di presentazione: le prove ispirate ai quanti portano a nuovi risultati di complessità sui calcoli quantistici con l'input degli stati del gatto (rappresentazione astratta generata utilizzando DALL.E).
Riepilogo popolare
Sfruttando le relazioni tra il permanente e le ampiezze dei circuiti quantistici ottici lineari, dimostriamo che le tecniche ispirate ai quanti forniscono dimostrazioni rapide di molti importanti teoremi sul permanente, come il MacMahon Master Theorem.
Le nostre dimostrazioni di ispirazione quantistica forniscono nuove informazioni per lo scienziato quantistico sui teoremi combinatori e scoprono nuovi risultati nella complessità quantistica.
► dati BibTeX
► Riferimenti
, H. Minc, "Permanenti", vol. 6. Pressa dell'Università di Cambridge, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
, JK Percus, “Metodi combinatori”, vol. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
, LG Valiant, "La complessità del calcolo del permanente", Informatica teorica 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
, ER Caianiello, “Sulla teoria quantistica dei campi—I: soluzione esplicita dell'equazione di Dyson in elettrodinamica senza uso di grafi di Feynman”, Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
, S. Scheel, "Permanents in linear optical networks", quant-ph/0406127.
arXiv: Quant-ph / 0406127
, S. Aaronson e A. Arkhipov, "La complessità computazionale dell'ottica lineare", Theory of Computing 9, 143 (2013), arXiv: 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682 mila
arXiv: arXiv: 1011.3245 mila
, S. Aaronson, "Una prova lineare-ottica che il permanente è # P-hard", Atti della Royal Society A: Scienze matematiche, fisiche e ingegneristiche 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
, S. Rahimi-Keshari, AP Lund e TC Ralph, "Cosa può dire l'ottica quantistica sulla teoria della complessità computazionale?", Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
, D. Grier e L. Schaeffer, "Nuovi risultati di durezza per il permanente utilizzando l'ottica lineare", arXiv: 1610.04670.
arXiv: arXiv: 1610.04670 mila
, PP Rohde, DW Berry, KR Motes e JP Dowling, "Un argomento di ottica quantistica per la durezza $ # $ P di una classe di integrali multidimensionali", arXiv: 1607.04960.
arXiv: arXiv: 1607.04960 mila
, L. Chakhmakhchyan, NJ Cerf e R. Garcia-Patron, "Algoritmo di ispirazione quantistica per la stima del permanente di matrici semidefinite positive", Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
, A. Meiburg, "Inapprossimabilità di permanenti semidefiniti positivi e tomografia quantistica dello stato", arXiv: 2111.03142.
arXiv: arXiv: 2111.03142 mila
, PA MacMahon, "Analisi combinatoria, volumi I e II", vol. 137. Società matematica americana, 2001.
, I. Good, “Prove di alcune identità 'binomiali' per mezzo del 'Teorema Maestro' di MacMahon”, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
, L. Carlitz, "Un'applicazione del teorema principale di MacMahon", SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040 mila
, L. Carlitz, "Alcune formule di espansione e convoluzione relative al teorema principale di MacMahon", SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023 mila
, HJ Ryser, "Matematica combinatoria", vol. 14. Società matematica americana, 1963.
, K. Balasubramanian, Combinatoria e diagonali di matrici. Tesi di dottorato, Indian Statistical Institute-Kolkata, 1980.
, ET Bax, Algoritmi alle differenze finite per problemi di conteggio. Tesi di dottorato, California Institute of Technology, 1998.
, DG Glynn, "Il permanente di una matrice quadrata", European Journal of Combinatorics 31, 1887–1891 (2010).
https: / / doi.org/ 10.1016 / j.ejc.2010.01.010
, PP Rohde, KR Motes, PA Knott, J. Fitzsimons, WJ Munro e JP Dowling, "Evidence for the conjecture that sample generalized cat states with linear optics is hard", Physical Review A 91, 012342 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.012342
, C. Weedbrook, S. Pirandola, R. García-Patrón, NJ Cerf, TC Ralph, JH Shapiro e S. Lloyd, "Informazioni quantistiche gaussiane", Recensioni di fisica moderna 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
, A. Leverrier, "$SU(p, q)$ stati coerenti e un teorema gaussiano di de Finetti", Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334 mila
, T. Jiang e Y. Ma, "Distanze tra matrici ortogonali casuali e normali indipendenti", arXiv: 1704.05205.
arXiv: arXiv: 1704.05205 mila
, AC Dixon, "Sulla somma dei cubi dei coefficienti in una certa espansione mediante il teorema binomiale", Messenger of mathematics 20, 79–80 (1891).
, I. Good, “Una breve dimostrazione del 'Maestro Teorema' di MacMahon”, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
, S. Garoufalidis, TT Lê e D. Zeilberger, "The quantum MacMahon master theorem", Atti della National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
, M. Konvalinka e I. Pak, "Estensioni non commutative del teorema principale di MacMahon", Advances in Mathematics 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020
, MP Tuite, "Alcune generalizzazioni del teorema principale di MacMahon", Journal of Combinatorial Theory, serie A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
, VV Kocharovsky, VV Kocharovsky e SV Tarasov, "The Hafnian Master Theorem", Algebra lineare e sue applicazioni 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
, WY Chen, H. Galbraith e J. Louck, "Teoria del momento angolare, calcolo umbrale e calcolo combinatorio", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
, BM Terhal e DP DiVincenzo, "Simulazione classica di circuiti quantistici di fermioni non interagenti", Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
, V. Shchesnovich, "Teoria dell'indistinguibilità parziale per esperimenti multifotone in dispositivi multiporta", Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
, D. Spivak, MY Niu, BC Sanders e H. de Guise, "Interferenza generalizzata di fermioni e bosoni", Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
, E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin e M. Hafezi, "Boson Sampling for Generalized Bosons", arXiv:2204.08389.
https: / / doi.org/ 10.1103 / PhysRevResearch.4.043096
arXiv: arXiv: 2204.08389 mila
, A. Clément, N. Heurtel, S. Mansfield, S. Perdrix e B. Valiron, "LO $ _text {v} $ - Calculus: un linguaggio grafico per circuiti quantistici ottici lineari", arXiv: 2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787 mila
, G. De Felice e B. Coecke, "Ottica quantistica lineare tramite diagrammi di stringhe", arXiv: 2204.12985.
arXiv: arXiv: 2204.12985 mila
, B. Peropadre, GG Guerreschi, J. Huh e A. Aspuru-Guzik, "Proposta per il campionamento di bosoni a microonde", Lettere di revisione fisica 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
, S. Girvin, "Gli stati del gatto di Schrödinger nel circuito qed", arXiv:1710.03179.
arXiv: arXiv: 1710.03179 mila
, X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu e F. Nori, "Fotonica a microonde con circuiti quantistici superconduttori", Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
, J. Huh, "Un algoritmo quantistico veloce per il calcolo permanente della matrice", arXiv: 2205.01328.
arXiv: arXiv: 2205.01328 mila
, S. Aaronson e T. Hance, "Generalizzazione e derandomizzazione dell'algoritmo di approssimazione di Gurvits per il permanente", Quantum Info. Calcola. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
, S. Chin e J. Huh, "Concorrenza generalizzata nel campionamento dei bosoni", Rapporti scientifici 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
, M.-H. Yung, X. Gao e J. Huh, "Universal legato al campionamento dei bosoni nell'ottica lineare e alle sue implicazioni computazionali", National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
, VS Shchesnovich, "Sulla complessità classica del campionamento dall'interferenza quantistica di bosoni indistinguibili", International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
, DM Jackson, "L'unificazione di alcuni problemi di enumerazione per sequenze", Journal of Combinatorial Theory, Serie A 22, 92-96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
, FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins e 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
, AP Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, JL O'Brien e TC Ralph, "Campionamento di bosoni da uno stato gaussiano", Lettere di revisione fisica 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
, JP Olson, KP Seshadreesan, KR Motes, PP Rohde e JP Dowling, "Il campionamento di stati compressi arbitrari con aggiunta di fotoni o sottrazione di fotoni è nella stessa classe di complessità del campionamento di bosoni", Physical Review A 91, 022317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.022317
, CS Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn e I. Jex, "Campionamento del bosone gaussiano", Lettere di revisione fisica 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
, A. Lund, S. Rahimi-Keshari e T. Ralph, "Campionamento esatto di bosoni mediante misurazioni gaussiane a variabile continua", Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
, L. Chakhmakhchyan e NJ Cerf, "Campionamento di boson con misurazioni gaussiane", Physical Review A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
, U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi e G. Ferrini, "Campionamento a variabile continua da stati compressi aggiunti o sottratti da fotoni", Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
, N. Quesada, JM Arrazola e N. Killoran, "Gaussian boson sampling using threshold detectors", Physical Review A 98, 062322 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.062322
, 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 campionamento di bosoni gaussiani dimensionali", Science Advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Citato da
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
