1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, EUA
2Ciência da Computação, Universidade Tufts, Medford, MA 02155, EUA
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
O permanente é fundamental tanto para a teoria da complexidade quanto para a combinatória. Na computação quântica, o permanente aparece na expressão das amplitudes de saída de cálculos ópticos lineares, como no modelo Boson Sampling. Aproveitando esta conexão, fornecemos provas de inspiração quântica de muitas identidades permanentes notáveis, existentes e também novas. Mais notavelmente, fornecemos uma prova de inspiração quântica do teorema mestre de MacMahon, bem como provas para novas generalizações deste teorema. As provas anteriores deste teorema usaram ideias completamente diferentes. Além de suas aplicações puramente combinatórias, nossos resultados demonstram a dureza clássica da amostragem exata e aproximada de cálculos quânticos ópticos lineares com estados cat de entrada.
Imagem em destaque: Provas inspiradas em quântica levam a novos resultados de complexidade sobre cálculos quânticos com entrada de estados cat (representação abstrata gerada usando DALL.E).
Resumo popular
Ao explorar as relações entre o permanente e as amplitudes dos circuitos quânticos ópticos lineares, mostramos que as técnicas inspiradas no quantum fornecem provas rápidas de muitos teoremas importantes sobre o permanente, como o Teorema Mestre de MacMahon.
Nossas provas inspiradas na quântica fornecem novos insights para o cientista quântico sobre teoremas combinatórios e revelam novos resultados na complexidade quântica.
► dados BibTeX
► Referências
[1] H. Minc, “Permanentes”, vol. 6. Imprensa da Universidade de Cambridge, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, “Métodos combinatórios”, vol. 4.Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, “A complexidade da computação do permanente”, Ciência da computação teórica 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, “Sobre a teoria quântica de campos - I: solução explícita da equação de Dyson em eletrodinâmica sem o 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 em redes ópticas lineares”, quant-ph/0406127.
arXiv: quant-ph / 0406127
[6] S. Aaronson e A. Arkhipov, “A complexidade computacional da óptica linear”, Theory of Computing 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, “Uma prova óptica-linear de que o permanente é# P-difícil”, 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 e TC Ralph, “O que a óptica quântica pode dizer sobre a teoria da complexidade computacional?”, Cartas de revisão física 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier e L. Schaeffer, “Novos resultados de dureza para o permanente usando óptica linear”, arXiv:1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes e JP Dowling, “Um argumento de óptica quântica para a dureza $#$P de uma classe de integrais multidimensionais”, arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf e R. Garcia-Patron, “Algoritmo inspirado em quântica para estimar a permanente de matrizes semidefinidas positivas”, Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, “Inaproximabilidade de Permanentes Semidefinidos Positivos e Tomografia de Estado Quântico”, arXiv:2111.03142.
arXiv: arXiv: 2111.03142
[13] PA MacMahon, “Análise Combinatória, Volumes I e II”, vol. 137. Sociedade Matemática Americana, 2001.
[14] I. Good, “Provas de algumas identidades ‘binomiais’ por meio do ‘Teorema Mestre’ de MacMahon”, em Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, “Uma aplicação do teorema mestre de MacMahon”, SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, “Algumas expansões e fórmulas de convolução relacionadas ao teorema mestre de MacMahon”, SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, “Matemática Combinatória”, vol. 14. Sociedade Matemática Americana, 1963.
[18] K. Balasubramaniano, Combinatória e diagonais de matrizes. Tese de doutorado, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, Algoritmos de diferenças finitas para problemas de contagem. Tese de doutorado, Instituto de Tecnologia da Califórnia, 1998.
[20] DG Glynn, “O permanente de uma matriz quadrada”, European Journal of Combinatorics 31, 1887–1891 (2010).
https: / / doi.org/ 10.1016 / j.ejc.2010.01.010
[21] P. P. Rohde, K. R. Motes, P. A. Knott, J. Fitzsimons, W. J. Munro e J. P. Dowling, “Evidência para a conjectura de que a amostragem de estados generalizados de gatos com óptica linear é 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 e S. Lloyd, “Informações quânticas gaussianas”, Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, “$SU(p, q)$ estados coerentes e um teorema gaussiano de Finetti,” Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang e Y. Ma, “Distâncias entre matrizes ortogonais aleatórias e normais independentes”, arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, “Sobre a soma dos cubos dos coeficientes em uma certa expansão pelo teorema binomial”, Messenger of math 20, 79–80 (1891).
[26] I. Good, “Uma breve prova do ‘Teorema Mestre’ de MacMahon”, em Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, T. T. Lê e D. Zeilberger, “O teorema mestre quântico de MacMahon”, Proceedings of the National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[28] M. Konvalinka e I. Pak, “Extensões não comutativas do Teorema Mestre de MacMahon”, Advances in Mathematics 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020
[29] MP Tuite, “Algumas generalizações do Teorema Mestre de MacMahon”, Journal of Combinatorial Theory, Série A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
[30] VV Kocharovsky, VV Kocharovsky e SV Tarasov, “O Teorema do Mestre Hafniano”, Álgebra Linear e suas Aplicações 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[31] WY Chen, H. Galbraith e J. Louck, “Teoria do momento angular, cálculo umbral e combinatória”, Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal e DP DiVincenzo, “Simulação clássica de circuitos quânticos de férmions sem interação”, Revisão Física A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, “Teoria da indistinguibilidade parcial para experimentos multifótons em dispositivos multiportas”, Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders e H. de Guise, “Interferência generalizada de férmions e bósons”, Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin e M. Hafezi, “Amostragem de bósons para bósons 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 e B. Valiron, “LO$_text{v}$-Calculus: Uma linguagem gráfica para circuitos quânticos ópticos lineares”, arXiv:2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787
[37] G. De Felice e B. Coecke, “Óptica Linear Quântica via Diagramas de Cordas”, arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, G. G. Guerreschi, J. Huh e A. Aspuru-Guzik, “Proposta para amostragem de bósons de microondas”, Cartas de revisão física 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] S. Girvin, “Estados de gato de Schrödinger no circuito qed”, arXiv:1710.03179.
arXiv: arXiv: 1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu e F. Nori, “Fotônica de micro-ondas com circuitos quânticos supercondutores”, Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, “Um algoritmo quântico rápido para computação de matriz permanente”, arXiv:2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson e T. Hance, “Generalizando e Desrandomizando o Algoritmo de Aproximação de Gurvits para o Permanente”, Quantum Info. Computação. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin e J. Huh, “Concorrência generalizada na amostragem de bósons”, Relatórios científicos 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao e J. Huh, “Limite universal na amostragem de bósons em óptica linear e suas implicações computacionais”, Revisão científica nacional 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, “Sobre a complexidade clássica da amostragem da interferência quântica de bósons indistinguíveis”, International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, “A unificação de certos problemas de enumeração para sequências”, Journal of Combinatorial Theory, Série A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins e CJ Villas-Boas, “Superposição de estados comprimidos de dois modos para processamento de informação quântica e detecção quântica”, 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 e TC Ralph, “Amostragem de bósons de um estado gaussiano”, Cartas de revisão física 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde e JP Dowling, “A amostragem arbitrária de estados comprimidos com adição de fótons ou subtração de fótons está na mesma classe de complexidade da amostragem de bósons”, 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, “Gaussian boson sampling”, Physical review letters 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari e T. Ralph, “Amostragem exata de bósons usando medições de variável contínua gaussiana”, Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan e NJ Cerf, “Amostragem de bósons com medições 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 e G. Ferrini, “Amostragem de variável contínua de estados comprimidos com adição de fótons ou subtração de fótons”, Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola e N. Killoran, “Amostragem de bósons gaussianos usando detectores de limite”, 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., “Vantagem computacional quântica via alta amostragem de bósons gaussianos multidimensionais”, Science advance 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Citado por
Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.
