Estação Q, Microsoft Research, Santa Barbara, CA 93106-6105, EUA
Microsoft Quantum e Microsoft Research, Redmond, WA 98052, EUA
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Apresentamos algoritmos clássicos e quânticos baseados em métodos espectrais para um problema de análise de componentes principais de tensores. O algoritmo quântico atinge uma aceleração $quartic$ enquanto usa um espaço exponencialmente menor do que o algoritmo espectral clássico mais rápido e uma aceleração superpolinomial sobre algoritmos clássicos que usam apenas espaço polinomial. Os algoritmos clássicos que apresentamos estão relacionados, mas um pouco diferentes daqueles apresentados recentemente na Ref. [1]. Em particular, temos um limite aprimorado para recuperação e os algoritmos que apresentamos funcionam para tensores de ordem par e ímpar. Esses resultados sugerem que problemas de inferência em larga escala são uma aplicação futura promissora para computadores quânticos.
► dados BibTeX
► Referências
[1] Alexander S Wein, Ahmed El Alaoui e Cristopher Moore. A hierarquia kikuchi e o tensor pca. 2019. arXiv:1904.03858.
arXiv: 1904.03858
[2] Andrea Montanari e Emile Richard. Um modelo estatístico para tensor pca. Em Advances in Neural Information Processing Systems, páginas 2897–2905, 2014.
[3] Thibault Lesieur, Leo Miolane, Marc Lelarge, Florent Krzakala e Lenka Zdeborova. Transições de fase estatísticas e computacionais na estimação de tensores cravados. Em 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, jun 2017. doi:10.1109/isit.2017.8006580.
https: / / doi.org/ 10.1109 / isit.2017.8006580
[4] Samuel B Hopkins, Jonathan Shi e David Steurer. Análise de componentes principais do tensor através de provas de soma de quadrados. Na Conferência sobre Teoria da Aprendizagem, páginas 956–1006, 2015.
[5] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi e David Steurer. Algoritmos espectrais rápidos de provas de soma de quadrados: decomposição tensorial e vetores esparsos plantados. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing – STOC 2016. ACM Press, 2016. doi:10.1145/2897518.2897529.
https: / / doi.org/ 10.1145 / 2897518.2897529
[6] Vijay VSP Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami e Madhur Tulsiani. Aproximações multiplicativas para otimização polinomial sobre a esfera unitária. CoRR, abs/1611.05998, 2016. URL: http://arxiv.org/abs/1611.05998, arXiv:1611.05998.
arXiv: 1611.05998
[7] Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee e Madhur Tulsiani. Desacoplamento fraco, dobras polinomiais e otimização aproximada sobre a esfera. Em 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, out 2017. doi:10.1109/focs.2017.97.
https: / / doi.org/ 10.1109 / focs.2017.97
[8] RF Werner. Grandes desvios e sistemas quânticos de campo médio. Em Probabilidade Quântica e Tópicos Relacionados, páginas 349–381. WORLD SCIENTIFIC, jul 1992. doi:10.1142/9789814354783_0024.
https: / / doi.org/ 10.1142 / 9789814354783_0024
[9] Christina V. Kraus, Maciej Lewenstein e J. Ignacio Cirac. Estados fundamentais de hamiltonianos de rede fermiônica com simetria de permutação. Physical Review A, 88(2), agosto de 2013. doi:10.1103/physreva.88.022335.
https: / / doi.org/ 10.1103 / physreva.88.022335
[10] Fernando GSL Brandão e Aram W. Harrow. Aproximações produto-estado para estados quânticos. Communications in Mathematical Physics, 342(1):47–80, jan 2016. doi:10.1007/s00220-016-2575-1.
https://doi.org/10.1007/s00220-016-2575-1
[11] Scott Aaronson e Lijie Chen. Fundamentos da teoria da complexidade de experimentos de supremacia quântica. Na 32ª Conferência de Complexidade Computacional (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. arXiv:1612.05903.
arXiv: 1612.05903
[12] Madan Lal Mehta. Matrizes aleatórias, volume 142. Elsevier, 2004.
[13] James Demmel, Ioana Dumitriu e Olga Holtz. Álgebra linear rápida é estável. Numerische Mathematik, 108(1):59–91, outubro de 2007. doi:10.1007/s00211-007-0114-x.
https: / / doi.org/ 10.1007 / s00211-007-0114-x
[14] Guang Hao Low e Isaac L. Chuang. Simulação hamiltoniana ótima por processamento de sinal quântico. Física Rev. Lett., 118:010501, 2017. arXiv:1606.02685v2, doi:10.1103/PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685v2
[15] Guang Hao Low e Isaac L Chuang. Simulação hamiltoniana por qubitização. 2016. arXiv:1610.06546 https://doi.org/10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
arXiv: 1610.06546
[16] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari e Rolando D. Somma. Melhoria exponencial na precisão para simular Hamiltonianos esparsos. páginas 283–292, 2014. arXiv:1312.1414, doi:10.1145/2591796.2591854.
https: / / doi.org/ 10.1145 / 2591796.2591854
arXiv: 1312.1414
[17] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari e Rolando D. Somma. Simulando a dinâmica hamiltoniana com uma série de Taylor truncada. Física Rev. Lett., 114:090502, 2015. arXiv:1412.4687, doi:10.1103/PhysRevLett.114.090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687
[18] DW Berry, AM Childs e R. Kothari. Simulação hamiltoniana com dependência quase ótima de todos os parâmetros. Em 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, páginas 792–809, out 2015. arXiv:1501.01715, doi:10.1109/FOCS.2015.54.
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[19] Alexei Yu Kitaev, Alexander Shen e Mikhail N Vyalyi. Computação clássica e quântica, volume 47. American Mathematical Society Providence, 2002. doi:10.1090/gsm/047.
https: / / doi.org/ 10.1090 / gsm / 047
[20] Gilles Brassard, Peter Hoyer, Michele Mosca e Alain Tapp. Amplificação e estimativa de amplitude quântica. Contemporary Mathematics, 305:53–74, 2002. doi:10.1090/conm/305.
https: / / doi.org/ 10.1090 / conm / 305
[21] Anthony Carbery e James Wright. Desigualdades distribucionais e de norma ${L^q}$ para polinômios sobre corpos convexos em ${R^n}$. Mathematical Research Letters, 8(3):233–248, 2001. doi:10.4310/mrl.2001.v8.n3.a1.
https://doi.org/10.4310/mrl.2001.v8.n3.a1
[22] Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak e Matthias Troyer. Resolvendo modelos de elétrons fortemente correlacionados em um computador quântico. Physical Review A, 92(6), dez 2015. doi:10.1103/physreva.92.062318.
https: / / doi.org/ 10.1103 / physreva.92.062318
<p class="quebrar">[23] Matthew B. Hastings. A assintótica do corte mínimo de fluxo máximo quântico. Communications in Mathematical Physics, 351(1):387–418, nov 2016. doi:10.1007/s00220-016-2791-8.
https://doi.org/10.1007/s00220-016-2791-8
Citado por
[1] Alexander S. Wein, Ahmed El Alaoui e Cristopher Moore, “A Hierarquia Kikuchi e o Tensor PCA”, arXiv: 1904.03858.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2020-02-28 01:28:52). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2020-02-28 01:28:50).
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.
