Zephyrnet Logo

Aproximando a dinâmica hamiltoniana com o método Nyström

Data:

Alessandro Rudi1, Leonard Wossnig2,3, Carlos Ciliberto2, Andrea Rocha2,4,5, Massimiliano Pontil6e Simone Severini2

1INRIA - Equipe do projeto Sierra, Paris, França
2Departamento de Ciência da Computação, University College London, Londres, Reino Unido
3Rahko Ltd., Londres, Reino Unido
4Departamento de Ciência da Computação, Universidade do Texas em Austin, Austin, Estados Unidos
5Departamento de Ciência da Computação, University of Oxford, Oxford, Reino Unido
6Estatística Computacional e Aprendizado de Máquina, IIT, Gênova, Itália

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Simular a evolução no tempo de sistemas mecânicos quânticos é difícil para o BQP e espera-se que seja uma das principais aplicações dos computadores quânticos. Consideramos algoritmos clássicos para a aproximação da dinâmica hamiltoniana usando métodos de subamostragem da álgebra linear numérica aleatória. Derivamos uma técnica de simulação cujo tempo de execução escala polinomialmente no número de qubits e a norma de Frobenius do hamiltoniano. Como uma aplicação imediata, mostramos que a simulação quântica baseada em amostra, um tipo de evolução em que o Hamiltoniano é uma matriz de densidade, pode ser simulada de forma clássica de forma eficiente em condições estruturais específicas. Nossa principal contribuição técnica é um algoritmo aleatório para aproximar as exponenciais da matriz Hermitiana. A prova alavanca uma aproximação simétrica de baixo posto por meio do método de Nyström. Nossos resultados sugerem que sob fortes suposições de amostragem existem simulações de tempo poligarítmico clássicas de cálculos quânticos.

► dados BibTeX

► Referências

[1] Aharonov e Ta-Shma "Adiabatic Quantum State Generation and Statistical Zero Knowledge" Proceedings of the Trinta-quinto Simpósio Anual ACM em Teoria da Computação 20-29 (2003).
https: / / doi.org/ 10.1145 / 780542.780546

[2] Aleksandrov e Peller "Operator Lipschitz functions" Russian Mathematical Surveys 71, 605 (2016).
https: / / doi.org/ 10.1070 / RM9729

[3] Belabbas e Wolfe “Fast low-rank aproximation for covariance matrices” 2o IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2007. 293-296 (2007).
https: / / doi.org/ 10.1109 / CAMSAP.2007.4498023

[4] Belabbas e Wolfe “Sobre representações esparsas de operadores lineares e a aproximação de produtos de matriz” 42ª Conferência Anual em Ciências e Sistemas da Informação 258-263 (2008).
https: / / doi.org/ 10.1109 / CISS.2008.4558532

[5] Berry, Childs e Kothari, “Simulação hamiltoniana com dependência quase ótima de todos os parâmetros” IEEE 56º Simpósio Anual sobre Fundamentos de Ciência da Computação (FOCS) 792-809 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54

[6] Biamonte, Wittek, Pancotti, Rebentrost, Wiebe e Lloyd, “Quantum machine learning” Nature 549, 195 (2017).
https: / / doi.org/ 10.1038 / nature23474

[7] Bravyi, Browne, Calpin, Campbell, Gosset e Howard, "Simulação de circuitos quânticos por decomposições de estabilizador de baixa classificação" arXiv pré-impressão arXiv: 1808.00128 (2018).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[8] Chia, Gilyén, Li, Lin, Tang e Wang, "Estrutura aritmética de matriz de baixa classificação sublinear baseada em amostragem para dequantização de aprendizado de máquina quântica" arXiv pré-impressão arXiv: 1910.06151 (2019).

[9] Childs e Kothari "Simulando Hamiltonianos esparsos com Decomposições de Estrelas" Proceedings of the 5th Conference on Theory of Quantum Computation, Communication, and Cryptography 94-103 (2011).
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_8

[10] Childs e Wiebe “Simulação Hamiltoniana Usando Combinações Lineares de Operações Unitárias” Quantum Info. Comput. 12, 901-924 (2012).
https: / / doi.org/ 10.5555 / 2481569.2481570

[11] Childs, Cleve, Deotto, Farhi, Gutmann e Spielman, “Exponential Algorithmic Speedup by a Quantum Walk” Proceedings of the Trinta-quinto Simpósio Anual ACM em Teoria da Computação 59-68 (2003).
https: / / doi.org/ 10.1145 / 780542.780552

[12] Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini e Wossnig, “Quantum machine learning: a classical perspective” Proc. R. Soc. A 474, 20170551 (2018).
https: / / doi.org/ 10.1098 / rspa.2017.0551

[13] Drineas, Kannan e Mahoney, “Fast Monte Carlo algoritmos for matrices I: Approximating matrix multiplation” SIAM Journal on Computing 36, 132-157 (2006).
https: / / doi.org/ 10.1137 / S0097539704442684

[14] Drineas, Kannan e Mahoney, “Fast Monte Carlo algoritms for matrices II: Computing a low-rank aproximation to a matrix” SIAM Journal on computing 36, 158-183 (2006).
https: / / doi.org/ 10.1137 / S0097539704442696

[15] Drineas e Mahoney “Sobre o Método Nyström para Aproximar uma Matriz de Gram para Aprendizagem Baseada em Kernel Melhorada” J. Mach. Aprender. Res. 6, 2153-2175 (2005).
https: / / doi.org/ 10.5555 / 1046920.1194916

[16] Drineas e Mahoney “Lectures on randomized numical linear algebra” The Mathematics of Data 25, 1 (2018).

[17] Drineas, Mahoney, Muthukrishnan e Sarlós, “Faster Least Squares Approximation” Numer. Matemática. 117, 219-249 (2011).
https:/​/​doi.org/​10.1007/​s00211-010-0331-6

[18] Fowlkes, Belongie, Chung e Malik, “Spectral Grouping Using the Nyström Method” IEEE Trans. Pattern Anal. Mach. Intell. 26, 214-225 (2004).
https: / / doi.org/ 10.1109 / TPAMI.2004.1262185

[19] Frieze, Kannan e Vempala, "Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations" J. ACM 51, 1025-1041 (2004).
https: / / doi.org/ 10.1145 / 1039488.1039494

[20] Haegeman, Cirac, Osborne, Pižorn, Verschelde e Verstraete, “Princípio variacional dependente do tempo para redes quânticas” Physical review letters 107, 070601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.070601

[21] Higham “O método de escalonamento e quadratura para a matriz exponencial revisitada” SIAM J. Matrix Anal. Appl. 26, 1179-1193 (2005).
https: / / doi.org/ 10.1137 / 04061101X

[22] Higham “O Método de Escala e Quadratura para a Matriz Exponencial Revisitada” SIAM Rev. 51, 747-764 (2009).
https: / / doi.org/ 10.1137 / 090768539

[23] Hsu “Amostragem ponderada de produtos externos” arXiv preprint arXiv: 1410.4429 (2014).

[24] Huang, Newman e Szegedy, "Limites inferiores explícitos na simulação quântica forte" arXiv pré-impressão arXiv: 1804.10368 (2018).

[25] Jónsson, Bauer e Carleo, "Estados da rede neural para a simulação clássica de computação quântica" arXiv preprint arXiv: 1808.05232 (2018).

[26] Kerenidis e Prakash “Sistemas de recomendação quântica” arXiv preprint arXiv: 1603.08675 (2016).

[27] Kimmel, Lin, Low, Ozols e Yoder, "simulação Hamiltoniana com complexidade de amostra ideal" npj Quantum Information 3, 13 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[28] Kumar, Mohri e Talwalkar, “On Sampling-Based Approximate Spectral Decomposition” Proceedings of the
26ª Conferência Internacional Anual sobre Machine Learning 553-560 (2009).
https: / / doi.org/ 10.1145 / 1553374.1553446

[29] Kumar, Mohri e Talwalkar, "Métodos de amostragem para o método Nyström" Journal of Machine Learning Research 13, 981-1006 (2012).
https: / / doi.org/ 10.5555 / 2188385.2343678

[30] Li, Kwok e Lu, "Making Large Scale Nyström Approximation Possible" Proceedings of the 27th International Conference on International Conference on Machine Learning 631-638 (2010).
https: / / doi.org/ 10.5555 / 3104322.3104403

[31] Lloyd "Universal Quantum Simulators" Science 273, 1073-1078 (1996).
https: / / doi.org/ 10.1126 / science.273.5278.1073

[32] Lloyd, Mohseni e Rebentrost, “Quantum principal component analysis” Nature Physics 10, 631 (2014).
https: / / doi.org/ 10.1038 / nphys3029

[33] Lowand Chuang "Simulação Hamiltoniana por Amplificação Espectral Uniforme" arXiv pré-impressão arXiv: 1707.05391 (2017).

[34] Mackey, Talwalkar e Jordan, “Divide-and-Conquer Matrix Factorization” Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142 (2011).
https: / / doi.org/ 10.5555 / 2986459.2986586

[35] Mahoney “Algoritmos randomizados para matrizes e dados” Foundations and Trends® 3, 123-224 (2011).
https: / / doi.org/ 10.1561 / 2200000035

[36] Mathias “Approximation of matrix-valued functions” jornal SIAM sobre análise de matriz e aplicações 14, 1061-1063 (1993).
https: / / doi.org/ 10.1137 / 0614070

[37] Al-Mohyand Higham “Um novo algoritmo de escalonamento e quadratura para a matriz exponencial” SIAM Journal on Matrix Analysis and Applications 31, 970-989 (2009).
https: / / doi.org/ 10.1137 / 09074721X

[38] Al-Mohyand Higham “Calculando a ação da matriz exponencial, com um aplicativo para integradores exponenciais” Revista SIAM sobre computação científica 33, 488-511 (2011).
https: / / doi.org/ 10.1137 / 100788860

[39] Nakamoto “Uma desigualdade de norma para operadores Hermitianos” The American Matemático Mensal 110, 238 (2003).
https: / / doi.org/ 10.1080 / 00029890.2003.11919961

[40] Nyström “Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben” Acta Mathematica 54, 185-204 (1930).
https: / / doi.org/ 10.1007 / BF02547521

[41] Orecchia, Sachdeva e Vishnoi, "Aproximando o Exponencial, o Método Lanczos e um Õ (m) -Time Spectral Algorithm for Balanced Separator" Proceedings of the Quadragésimo Quarto Simpósio Anual ACM on Theory of Computing 1141-1160 (2012).
https: / / doi.org/ 10.1145 / 2213977.2214080

[42] Orús “Uma introdução prática às redes de tensores: estados de produtos matriciais e estados de pares emaranhados projetados” Annals of Physics 349, 117-158 (2014).
https: / / doi.org/ 10.1016 / j.aop.2014.06.013

[43] Rebentrost, Mohseni e Lloyd, “Quantum support vector machine for big data rating” Physical review letters 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[44] Rebentrost, Schuld, Wossnig, Petruccione, and Lloyd, "Quantum gradiente descida e método de Newton para otimização polinomial restrita" New Journal of Physics 21, 073023 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e

[45] Rudi, Camoriano e Rosasco, "Less is More: Nyström Computational Regularization" Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1 1657-1665 (2015).
https: / / doi.org/ 10.5555 / 2969239.2969424

[46] Rudi, Camoriano e Rosasco, "Less is More: Nyström Computational Regularization" arXiv preprint arXiv: 1507.04717 (2015).

[47] Schuld, Sinayskiy e Petruccione, "Predição por regressão linear em um computador quântico" Physical Review A 94, 022342 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022342

[48] Schwarz e Nest “Simulando circuitos quânticos com distribuições de saída esparsas” arXiv preprint arXiv: 1310.6749 (2013).

[49] Spielman e Teng “Algoritmos de tempo quase linear para particionamento de grafos, esparsificação de grafos e solução de sistemas lineares” Proceedings of the Trinta e sexto Simpósio Anual ACM em Teoria da Computação 81-90 (2004).
https: / / doi.org/ 10.1145 / 1007352.1007372

[50] Spielman e Teng "Spectral sparsification of graphs" SIAM Journal on Computing 40, 981-1025 (2011).
https: / / doi.org/ 10.1137 / 08074489X

[51] Suzuki "Fórmula de Trotter generalizada e aproximações sistemáticas de operadores exponenciais e derivações internas com aplicações para problemas de muitos corpos" Communications in Mathematical Physics 51, 183-190 (1976).
https: / / doi.org/ 10.1007 / BF01609348

[52] Talwalkar, Kumar e Rowley, “Large-scale manifold learning” IEEE Conference on Computer Vision and Pattern Recognition 1-8 (2008).
https: / / doi.org/ 10.1109 / CVPR.2008.4587670

[53] Tang “A Quantum-Inspired Classical Algorithm for Recommendation Systems” Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing 217-228 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316310

[54] Tropp “Limites de cauda amigáveis ​​ao usuário para somas de matrizes aleatórias” encontrado. Comput. Matemática. 12, 389-434 (2012).
https: / / doi.org/ 10.1007 / s10208-011-9099-z

[55] Trotter “Sobre o produto de semi-grupos de operadores” Proceedings of the American Mathematical Society 10, 545-551 (1959).
https:/​/​doi.org/​10.1090/​S0002-9939-1959-0108732-6

[56] Van Den Nest “Simulação clássica de computação quântica, o Gottesman” Quantum Information & Computation 10, 258-271 (2010).
https: / / doi.org/ 10.5555 / 2011350.2011356

[57] Verstraete, Garcia-Ripoll e Cirac, “Operadores de densidade de produto matricial: Simulação de sistemas dissipativos e de temperatura finita” Physical review letters 93, 207204 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.207204

[58] Verstraete, Murg e Cirac, “Estados de produto de matriz, estados de pares emaranhados projetados e métodos de grupo de renormalização variacional para sistemas de spin quântico” Advances in Physics 57, 143-224 (2008).
https: / / doi.org/ 10.1063 / 1.5026985

[59] Vidal “Simulação eficiente de sistemas quânticos unidimensionais de muitos corpos” Phys. Rev. Lett. 93, 040502 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.040502

[60] Williams e Seeger “Usando o Método Nyström para Acelerar Máquinas de Kernel” Avanços em Sistemas de Processamento de Informação Neural 13 682-688 (2001).
https: / / doi.org/ 10.5555 / 3008751.3008847

[61] Williams, Rasmussen, Schwaighofer e Tresp, relatório “Observações sobre o Método de Nyström para Previsão do Processo Gaussiano” (2002).

[62] Woodruff “Esboçar como ferramenta para álgebra linear numérica” Foundations and Trends® 10, 1-157 (2014).
https: / / doi.org/ 10.1561 / 0400000060

[63] Zhang e Kwok “Método de Nyström agrupado para aprendizado múltiplo em grande escala e redução de dimensão” IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
https: / / doi.org/ 10.1109 / TNN.2010.2064786

[64] Zhang, Tsang e Kwok, "Aproximação de baixo nível de Nyström melhorada e análise de erro" Proceedings of the 25th International Conference on Machine Learning 1232-1239 (2008).
https: / / doi.org/ 10.1145 / 1390156.1390311

Citado por

[1] Ewin Tang, "Algoritmos clássicos inspirados no quantum para análise de componentes principais e agrupamento supervisionado", arXiv: 1811.00414.

[2] Juan A. Acebron, “Um método de Monte Carlo para calcular a ação de uma matriz exponencial em um vetor”, arXiv: 1904.12759.

[3] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang e Chunhao Wang, "Estrutura aritmética de matriz de baixa classificação sublinear baseada em amostragem para desquantização de aprendizado de máquina quântica", arXiv: 1910.06151.

As citações acima são de SAO / NASA ADS (última atualização com êxito 2020-02-20 15:40:36). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

Não foi possível buscar Dados citados por referência cruzada durante a última tentativa 2020-02-20 15:40:34: Não foi possível buscar os dados citados por 10.22331 / q-2020-02-20-234 do Crossref. Isso é normal se o DOI foi registrado recentemente.

Fonte: https://quantum-journal.org/papers/q-2020-02-20-234/

local_img

Inteligência mais recente

local_img