1Instituto de Información y Materia Cuántica, Instituto de Tecnología de California, Pasadena, CA 91125, EE. UU.
2Informática, Universidad de Tufts, Medford, MA 02155, EE. UU.
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
El permanente es fundamental tanto para la teoría de la complejidad como para la combinatoria. En la computación cuántica, el permanente aparece en la expresión de las amplitudes de salida de los cálculos ópticos lineales, como en el modelo Boson Sampling. Aprovechando esta conexión, damos pruebas inspiradas en la cuántica de muchas identidades permanentes notables existentes y nuevas. En particular, damos una prueba inspirada en la cuántica del teorema maestro de MacMahon, así como pruebas para nuevas generalizaciones de este teorema. Las demostraciones anteriores de este teorema utilizaron ideas completamente diferentes. Más allá de sus aplicaciones puramente combinatorias, nuestros resultados demuestran la dureza clásica del muestreo exacto y aproximado de cálculos cuánticos ópticos lineales con estados cat de entrada.
Imagen destacada: las pruebas inspiradas en la cuántica conducen a nuevos resultados de complejidad sobre los cálculos cuánticos con entrada de estados cat (representación abstracta generada con DALL.E).
Resumen popular
Al explotar las relaciones entre el permanente y las amplitudes de los circuitos cuánticos ópticos lineales, mostramos que las técnicas inspiradas en los cuánticos proporcionan pruebas rápidas de muchos teoremas importantes sobre el permanente, como el Teorema Maestro de MacMahon.
Nuestras demostraciones inspiradas en la cuántica brindan nuevos conocimientos para los científicos cuánticos sobre los teoremas combinatorios y descubren nuevos resultados en la complejidad cuántica.
► datos BibTeX
► referencias
[ 1 ] H. Minc, “Permanentes”, vol. 6. Prensa de la Universidad de Cambridge, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[ 2 ] JK Percus, “Métodos combinatorios”, vol. 4. Medios de comunicación de ciencia y negocios de Springer, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[ 3 ] LG Valiant, "La complejidad de computar lo permanente", Informática teórica 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[ 4 ] ER Caianiello, "Sobre la teoría cuántica de campos: I: solución explícita de la ecuación de Dyson en electrodinámica sin el uso de gráficos de Feynman", Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[ 5 ] S. Scheel, "Permanentes en redes ópticas lineales", quant-ph/0406127.
arXiv: quant-ph / 0406127
[ 6 ] S. Aaronson y A. Arkhipov, "La complejidad computacional de la óptica lineal", Teoría de la computación 9, 143 (2013), arXiv: 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[ 7 ] S. Aaronson, "Una prueba óptica lineal de que el permanente es # P-duro", Actas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
[ 8 ] S. Rahimi-Keshari, AP Lund y TC Ralph, "¿Qué puede decir la óptica cuántica sobre la teoría de la complejidad computacional?", Cartas de revisión física 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[ 9 ] D. Grier y L. Schaeffer, "Nuevos resultados de dureza para el uso permanente de óptica lineal", arXiv: 1610.04670.
arXiv: arXiv: 1610.04670
[ 10 ] PP Rohde, DW Berry, KR Motes y JP Dowling, "Un argumento de óptica cuántica para la dureza $#$P de una clase de integrales multidimensionales", arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[ 11 ] L. Chakhmakhchyan, NJ Cerf y R. Garcia-Patron, "Algoritmo inspirado en Quantum para estimar el permanente de matrices semidefinidas positivas", Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[ 12 ] A. Meiburg, "Inaproximabilidad de permanentes semidefinidos positivos y tomografía de estado cuántico", arXiv: 2111.03142.
arXiv: arXiv: 2111.03142
[ 13 ] PA MacMahon, “Análisis Combinatorio, Volúmenes I y II”, vol. 137. Sociedad Matemática Estadounidense, 2001.
[ 14 ] I. Good, "Pruebas de algunas identidades 'binomiales' por medio del 'Teorema maestro' de MacMahon", en Actas matemáticas de la Sociedad Filosófica de Cambridge, vol. 58, págs. 161 y 162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[ 15 ] L. Carlitz, "Una aplicación del teorema maestro de MacMahon", SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[ 16 ] L. Carlitz, "Algunas fórmulas de expansión y convolución relacionadas con el teorema maestro de MacMahon", SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[ 17 ] HJ Ryser, "Matemáticas combinatorias", vol. 14. Sociedad Matemática Estadounidense, 1963.
[ 18 ] K. Balasubramanian, Combinatoria y diagonales de matrices. Tesis de doctorado, Instituto de Estadística de la India-Kolkata, 1980.
[ 19 ] ET Bax, Algoritmos de diferencias finitas para problemas de conteo. Tesis de doctorado, Instituto de Tecnología de California, 1998.
[ 20 ] DG Glynn, "El permanente de una matriz cuadrada", 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 y JP Dowling, "Evidencia de la conjetura de que el muestreo de estados de gatos generalizados con óptica lineal es difícil", 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 y S. Lloyd, “Información cuántica gaussiana”, Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[ 23 ] A. Leverrier, "$ SU (p, q) $ estados coherentes y un teorema de Gaussian de Finetti", Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[ 24 ] T. Jiang y Y. Ma, "Distancias entre matrices ortogonales aleatorias y normales independientes", arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[ 25 ] AC Dixon, "Sobre la suma de los cubos de los coeficientes en una cierta expansión por el teorema del binomio", Messenger of math 20, 79–80 (1891).
[ 26 ] I. Good, "Una prueba breve del 'Teorema del maestro' de MacMahon", en Actas matemáticas de la Sociedad Filosófica de Cambridge, vol. 58, págs. 160 y 160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[ 27 ] S. Garoufalidis, TT Lê y D. Zeilberger, "El teorema maestro cuántico de MacMahon", Actas de la Academia Nacional de Ciencias 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[ 28 ] M. Konvalinka e I. Pak, "Extensiones no conmutativas del teorema principal de MacMahon", Advances in Mathematics 216, 29–61 (2007).
https: / / doi.org/ 10.1016 / j.aim.2007.05.020
[ 29 ] MP Tuite, "Algunas generalizaciones del teorema principal de MacMahon", 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 y SV Tarasov, "El teorema maestro de Hafn", Álgebra lineal y sus aplicaciones 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[ 31 ] WY Chen, H. Galbraith y J. Louck, "Teoría del momento angular, cálculo umbral y combinatoria", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[ 32 ] BM Terhal y DP DiVincenzo, “Simulación clásica de circuitos cuánticos de fermiones que no interactúan”, Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[ 33 ] V. Shchesnovich, "Teoría de indistinguibilidad parcial para experimentos multifotónicos en dispositivos multipuerto", Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[ 34 ] D. Spivak, MY Niu, BC Sanders y H. de Guise, "Interferencia generalizada de fermiones y bosones", Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[ 35 ] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin y M. Hafezi, "Muestreo de bosones para bosones generalizados", 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 y 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 y B. Coecke, "Óptica lineal cuántica a través de diagramas de cuerdas", arXiv: 2204.12985.
arXiv: arXiv: 2204.12985
[ 38 ] B. Peropadre, GG Guerreschi, J. Huh y A. Aspuru-Guzik, "Propuesta para el muestreo de bosones de microondas", Cartas de revisión física 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[ 39 ] S. Girvin, "Estados del gato de Schrödinger en el circuito qed", arXiv:1710.03179.
arXiv: arXiv: 1710.03179
[ 40 ] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu y F. Nori, "Fotónica de microondas con circuitos cuánticos superconductores", Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[ 41 ] J. Huh, "Un algoritmo cuántico rápido para calcular la matriz permanente", arXiv: 2205.01328.
arXiv: arXiv: 2205.01328
[ 42 ] S. Aaronson y T. Hance, "Generalización y eliminación del azar del algoritmo de aproximación de Gurvits para lo permanente", Quantum Info. computar 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[ 43 ] S. Chin y J. Huh, "Concurrencia generalizada en el muestreo de bosones", Informes científicos 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[ 44 ] M.-H. Yung, X. Gao y J. Huh, "Límite universal en el muestreo de bosones en óptica lineal y sus implicaciones computacionales", National Science Review 6, 719–729 (2019).
https://doi.org/10.1093/nsr/nwz048
[ 45 ] VS Shchesnovich, "Sobre la complejidad clásica del muestreo de la interferencia cuántica de bosones indistinguibles", International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[ 46 ] DM Jackson, "La unificación de ciertos problemas de enumeración para secuencias", Journal of Combinatorial Theory, Serie A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[ 47 ] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins y CJ Villas-Boas, "Superposición de estados comprimidos de dos modos para el procesamiento de información cuántica y la detección cuántica", Revisión física 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 y TC Ralph, "Muestreo de bosones de un estado gaussiano", cartas de revisión física 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[ 49 ] JP Olson, KP Seshadreesan, KR Motes, PP Rohde y JP Dowling, "El muestreo arbitrario de estados exprimidos con fotones agregados o sustraídos está en la misma clase de complejidad que el muestreo de bosones", 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 e I. Jex, “Muestreo del bosón de Gauss”, Cartas de revisión física 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[ 51 ] A. Lund, S. Rahimi-Keshari y T. Ralph, "Muestreo exacto de bosones con mediciones de variables continuas gaussianas", Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[ 52 ] L. Chakhmakhchyan y NJ Cerf, "Muestreo de bosones con medidas gaussianas", 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 y G. Ferrini, “Muestreo variable continuo de estados comprimidos con fotones agregados o con fotones restados”, Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[ 54 ] N. Quesada, JM Arrazola y N. Killoran, "Muestreo de bosones gaussianos mediante detectores de umbral", Revisión física 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., “Ventaja computacional cuántica mediante alta Muestreo de bosones gaussianos bidimensionales”, Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Citado por
Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.
