1IBM Quantum, IBM TJ Watson Research Center
2Escola de Matemática, Universidade de Bristol
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Apresentamos algoritmos clássicos e quânticos para aproximar funções de partição de Hamiltonianos clássicos a uma dada temperatura. Nosso trabalho tem duas contribuições principais: primeiro, modificamos o algoritmo clássico de Stefankovic, Vempala e Vigoda (J. ACM, 56(3), 2009) para melhorar sua complexidade amostral; segundo, quantizamos esse novo algoritmo, aprimorando o algoritmo quântico anteriormente mais rápido para esse problema, devido a Harrow e Wei (SODA 2020).
A abordagem convencional para estimar funções de partição requer aproximar as médias das distribuições de Gibbs em um conjunto de temperaturas inversas que formam o chamado cronograma de resfriamento. A duração do cronograma de resfriamento afeta diretamente a complexidade do algoritmo. Combinando nossa versão aprimorada do algoritmo de Stefankovic, Vempala e Vigoda com o estimador de produto pareado de Huber (Ann. Appl. Probab., 25(2), 2015), nosso novo algoritmo quântico usa um cronograma de resfriamento mais curto do que o conhecido anteriormente. Este comprimento corresponde ao comprimento ideal conjecturado por Stefankovic, Vempala e Vigoda. O algoritmo quântico também alcança uma vantagem quadrática no número de amostras quânticas necessárias em comparação com o número de amostras aleatórias extraídas
pelo melhor algoritmo clássico, e sua complexidade computacional tem dependência quadrática melhor do gap espectral das cadeias de Markov usadas para produzir as amostras quânticas.
Resumo popular
Aqui apresentamos algoritmos clássicos e quânticos para este problema. Nosso trabalho tem duas contribuições principais: primeiro, modificamos o algoritmo clássico de Stefankovic, Vempala e Vigoda (J. ACM, 56(3), 2009) para melhorar sua complexidade amostral; segundo, quantizamos esse novo algoritmo, aprimorando o algoritmo quântico anteriormente mais rápido para esse problema, devido a Harrow e Wei (SODA 2020).
A abordagem usual para a estimativa de funções de partição requer a aproximação das médias das distribuições de Gibbs em um conjunto de temperaturas inversas que formam o chamado esquema de resfriamento. A duração do cronograma de resfriamento afeta diretamente a complexidade do algoritmo. Combinando nossa versão aprimorada do algoritmo de Stefankovic, Vempala e Vigoda com o estimador de produto pareado de Huber (Ann. Appl. Probab., 25(2), 2015), nosso novo algoritmo quântico usa um cronograma de resfriamento mais curto do que o conhecido anteriormente. Este comprimento corresponde ao comprimento ideal conjecturado por Stefankovic, Vempala e Vigoda. O algoritmo quântico também alcança uma vantagem quadrática no número de amostras quânticas necessárias em comparação com o número de amostras aleatórias extraídas pelo melhor algoritmo clássico, e sua complexidade computacional tem dependência quadrática melhor na lacuna espectral das cadeias de Markov usadas para produzir o algoritmo quântico. amostras.
► dados BibTeX
► Referências
[1] Ivona Bezáková, Daniel Štefankovič, Vijay V Vazirani, and Eric Vigoda. Acelerando o recozimento simulado para os problemas de contagem permanente e combinatória. SIAM Journal on Computing, 37(5):1429–1454, 2008. doi:10.1137/050644033.
https: / / doi.org/ 10.1137 / 050644033
[2] Kurt Binder e Dieter W. Heermann. Simulação de Monte Carlo em Física Estatística: Uma Introdução (Textos de Graduação em Física). Springer, 2019.
[3] Gilles Brassard, Peter Hoyer, Michele Mosca e Alain Tapp. Amplificação e estimativa de amplitude quântica. Matemática Contemporânea, 305:53-74, 2002.
[4] Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang e Xiaodi Wu. Algoritmo quântico para estimar volumes de corpos convexos. arXiv:1908.03903, 2019.
arXiv: 1908.03903
[5] Guillaume Desjardins, Yoshua Bengio e Aaron C Courville. Ao rastrear a função de partição. Em Advances in neural information processing systems, páginas 2501–2509. Citeseer, 2011.
[6] Martin Dyer e Alan Frieze. Calculando o volume de corpos convexos: um caso em que a aleatoriedade comprovadamente ajuda. Combinatória probabilística e suas aplicações, 44:123-170, 1991.
[7] Martin Dyer, Alan Frieze e Ravi Kannan. Um algoritmo de tempo polinomial aleatório para aproximar o volume de corpos convexos. Journal of the ACM (JACM), 38(1):1–17, 1991. doi:10.1145/102782.102783.
https: / / doi.org/ 10.1145 / 102782.102783
[8] Andrew Gelman e Xiao-Li Meng. Simulando constantes de normalização: Da amostragem de importância à amostragem de ponte e à amostragem de caminho. Ciência estatística, páginas 163-185, 1998. doi:10.1214/ss/1028905934.
https:///doi.org/10.1214/ss/1028905934
[9] Paul Glasserman. Métodos de Monte Carlo em engenharia financeira, volume 53. Springer Science & Business Media, 2013.
[10] Ian Goodfellow, Yoshua Bengio e Aaron Courville. Aprendizado Profundo. MIT Press, 2016. http://www.deeplearningbook.org.
http://www.deeplearningbook.org
[11] Yassine Hamoudi e Frédéric Magniez. Desigualdade e Aplicações de Quantum Chebyshev. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, páginas 69:1–69:16, 2019. doi:10.4230/LIPIcs.ICALP.2019.69.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.69
[12] Aram W Harrow e Annie Y Wei. Recozimento simulado quântico adaptativo para inferência bayesiana e estimativa de funções de partição. In Proceedings of the XIV Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193–212, 2020. doi:10.1137/1.9781611975994.12.
https: / / doi.org/ 10.1137 / 1.9781611975994.12
[13] Geoffrey E Hinton, Simon Osindero e Yee-Whye Teh. Um algoritmo de aprendizado rápido para redes de crenças profundas. Computação neural, 18(7):1527–1554, 2006. doi:10.1162/neco.2006.18.7.1527.
https:///doi.org/10.1162/neco.2006.18.7.1527
[14] Marco Huber. Algoritmos de aproximação para a constante de normalização de distribuições de Gibbs. The Annals of Applied Probability, 25(2):974–985, 2015. doi:10.1214/14-AAP1015.
https:///doi.org/10.1214/14-AAP1015
[15] Mark Huber e Sarah Schott. Usando TPA para inferência Bayesiana. Estatísticas Bayesianas, 9:257–282, 2010. doi:10.1093/acprof:oso/9780199694587.003.0009.
https: / / doi.org/ 10.1093 / acprof: oso / 9780199694587.003.0009
[16] Mark Jerrum e Alistair Sinclair. Aproximando o permanente. SIAM Journal On Computing, 18(6):1149–1178, 1989. doi:10.1137/0218077.
https: / / doi.org/ 10.1137 / 0218077
[17] Mark R. Jerrum, Leslie G. Valiant e Vijay V. Vazirani. Geração aleatória de estruturas combinatórias a partir de uma distribuição uniforme. Theoretical Computer Science, 43:169 – 188, 1986. doi:10.1016/0304-3975(86)90174-X.
https://doi.org/10.1016/0304-3975(86)90174-X
[18] Vladimir Kolmogorov. Um algoritmo de aproximação mais rápido para a função de partição Gibbs. Em Proceedings of the 31st Conference On Learning Theory, volume 75 de Proceedings of Machine Learning Research, páginas 228–249. PMLR, 2018.
[19] Qiang Liu e Alexander T. Ihler. Limitando a função de partição usando a desigualdade de titular. In Proceedings of the 28th International Conference on Machine Learning, ICML, páginas 849–856. Omnipress, 2011.
[20] F. Magniez, A. Nayak, J. Roland e M. Santha. Pesquisa via caminhada quântica. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/090745854.
https: / / doi.org/ 10.1137 / 090745854
[21] Ashley Montanaro. Aceleração quântica de métodos de Monte Carlo. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015.
[22] Elchanan Mossel e Allan Sly. Limiares exatos para amostradores ising–gibbs em gráficos gerais. Ana Probab., 41(1):294–328, 01 2013. doi:10.1214/11-AOP737.
https:///doi.org/10.1214/11-AOP737
[23] Daniel Štefankovic, Santosh Vempala, and Eric Vigoda. Recozimento simulado adaptativo: Uma conexão quase ideal entre amostragem e contagem. Journal of the ACM (JACM), 56(3):1–36, 2009. doi:10.1145/1516512.1516520.
https: / / doi.org/ 10.1145 / 1516512.1516520
[24] Mário Szegedy. Aceleração quântica de algoritmos baseados em cadeia de Markov. No 45º Simpósio Anual do IEEE sobre Fundamentos da Ciência da Computação, páginas 32–41. IEEE, 2004.
[25] Cartão JP Valleau e DN. Estimativa Monte carlo da energia livre por amostragem multiestágio. The Journal of Chemical Physics, 57(12):5457-5462, 1972.
[26] Eric Vigoda. Limites aprimorados para amostras de cores. Journal of Mathematical Physics, 41(3):1555–1569, 2000. doi:10.1063/1.533196.
https: / / doi.org/ 10.1063 / 1.533196
[27] Marc Vuffray, Sidhant Misra, Andrey Lokhov e Michael Chertkov. Triagem de interação: Aprendizagem eficiente e ótima de modelos de ising. Em Advances in Neural Information Processing Systems, páginas 2595–2603, 2016.
[28] Pawel Wocjan e Anura Abeyesinghe. Aceleração via amostragem quântica. Physical Review A, 78(4):042336, 2008. doi:10.1103/PhysRevA.78.042336.
https: / / doi.org/ 10.1103 / PhysRevA.78.042336
Citado por
[1] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", arXiv: 2103.09717.
[2] Chen-Fu Chiang, Anirban Chowdhury e Pawel Wocjan, "Método de quantização com eficiência de espaço para cadeias de Markov reversíveis", arXiv: 2206.06886.
[3] Garrett T. Floyd, David P. Landau e Michael R. Geller, “Algoritmo quântico para amostragem de Wang-Landau”, arXiv: 2208.09543.
[4] Pawel Wocjan e Kristan Temme, “Szegedy Walk Unitaries for Quantum Maps”, arXiv: 2107.07365.
[5] Patrick Rall e Bryce Fuller, "Estimativa de amplitude do processamento de sinal quântico", arXiv: 2207.08628.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-09-02 12:01:44). 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 2022-09-02 12:01:43).
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.
