Considerações de latência para otimizadores estocásticos em algoritmos quânticos variacionais

Considerações de latência para otimizadores estocásticos em algoritmos quânticos variacionais

Registro de data e hora: 16 de março de 2023, 2:28
Nó Fonte: 2015562

Matt Menickelly1, Yunsoo Ha2e Matthew Otten3

1Divisão de Matemática e Ciência da Computação, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Departamento de Engenharia Industrial e de Sistemas, North Carolina State University, 915 Partners Way, Raleigh, NC 27601
3Laboratórios HRL, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

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

Sumário

Algoritmos quânticos variacionais, que ganharam destaque na configuração quântica ruidosa de escala intermediária, requerem a implementação de um otimizador estocástico em hardware clássico. Até o momento, a maioria das pesquisas empregou algoritmos baseados na iteração de gradiente estocástico como o otimizador clássico estocástico. Neste trabalho, propomos, em vez disso, o uso de algoritmos de otimização estocástica que geram processos estocásticos emulando a dinâmica de algoritmos determinísticos clássicos. Esta abordagem resulta em métodos com complexidades de iteração de pior caso teoricamente superiores, às custas de maiores complexidades de amostra (shot) de peri-iteração. Investigamos essa compensação teórica e empiricamente e concluímos que as preferências para a escolha do otimizador estocástico devem depender explicitamente de uma função da latência e dos tempos de execução do tiro.

Imagem em destaque: Latências e precisão do alvo afetam a escolha de otimizadores estocásticos para algoritmos quânticos variacionais.

Resumo popular

Algoritmos quânticos variacionais são candidatos promissores para resolver problemas práticos em computadores quânticos de curto prazo. No entanto, o processo de otimização desses algoritmos pode ser computacionalmente caro devido às duas necessidades de 1) realizar medições repetidas (shots) no computador quântico e 2) ajustar os parâmetros do circuito quântico. Aqui, propomos um novo algoritmo de otimização estocástica chamado SHOALS (SHOt Adaptive Line Search) que é projetado sob a suposição de que o tempo gasto na otimização realizando disparos é dominado pelo tempo gasto na otimização realizando ajustes no circuito. Demonstramos que o SHOALS supera outros algoritmos de otimização estocástica nessa configuração. Pelo contrário, quando o tempo de disparo é comparável ao tempo de comutação do circuito, os algoritmos estocásticos de descida do gradiente são mais eficientes. Ao considerar as compensações entre o tempo de disparo, o tempo de comutação do circuito e a eficiência do algoritmo de otimização, mostramos que o tempo total de execução dos algoritmos quânticos variacionais pode ser significativamente reduzido.

► dados BibTeX

► Referências

[1] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. “Rumo à química quântica em um computador quântico”. Nature Chemistry 2, 106–111 (2010).
https://​/​doi.org/​10.1038/​nchem.483

[2] Ian C Cloët, Matthew R Dietrich, John Arrington, Alexei Bazavov, Michael Bishof, Adam Freese, Alexey V Gorshkov, Anna Grassellino, Kawtar Hafidi, Zubin Jacob, et al. “Oportunidades para física nuclear e ciência da informação quântica” (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann e Johannes Knolle. “Simulando a dinâmica quântica de muitos corpos em um computador quântico digital atual”. npj Quantum Information 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Benjamin Nachman, Davide Provasoli, Wibe A de Jong e Christian W Bauer. “Algoritmo quântico para simulações de física de alta energia”. Cartas de Revisão Física 126, 062001 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.062001

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe e Seth Lloyd. “Aprendizado de máquina quântica”. Natureza 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Roman Orus, Samuel Mugel e Enrique Lizaso. “Computação quântica para finanças: visão geral e perspectivas”. Avaliações em Física 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[7] John Preskill. “Computação quântica na era NISQ e além”. Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek e IA Walmsley. “Estimativa de fase quântica ótima”. Cartas de Revisão Física 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] John Preskill. “Computação quântica tolerante a falhas”. Em Introdução à computação quântica e informação. Páginas 213–269. Mundial Científico (1998).

[10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. “Algoritmos quânticos variacionais”. Nature Reviews PhysicsPages 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] Peter JJ O'Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, et al. “Simulação quântica escalável de energias moleculares”. Revisão Física X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li e Simon C Benjamin. “Teoria da simulação quântica variacional”. Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Matthew Otten, Cristian L Cortes e Stephen K Gray. “Dinâmica quântica resiliente ao ruído usando ansatzes com preservação de simetria” (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow e Jay M Gambetta. “Eigensolver quântico variacional eficiente em hardware para pequenas moléculas e ímãs quânticos”. Natureza 549, 242-246 (2017).
https: / / doi.org/ 10.1038 / nature23879

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa e Keisuke Fujii. “Aprendizado de circuitos quânticos”. Physical Review A 98, 032309 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.032309

[16] Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline e Michael D Schneider. “Aprendizado de máquina quântica usando processos gaussianos com núcleos quânticos de alto desempenho” (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon e Todd J Martínez. “Cálculo quântico de transições eletrônicas usando um autosolver quântico variacional”. Cartas de revisão física 122, 230401 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.230401

[18] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush e Jarrod R McClean. “Usando modelos para melhorar otimizadores para algoritmos quânticos variacionais”. Ciência e Tecnologia Quântica 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin e RJ Schoelkopf. “Protocolos para leitura ideal de qubits usando uma medição contínua de não demolição quântica”. Physical Review A 76, 012325 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.012325

[20] Susan M Clark, Daniel Lobser, Melissa C Revelle, Christopher G Yale, David Bossert, Ashlyn D Burch, Matthew N Chow, Craig W Hogle, Megan Ivory, Jessica Pehr, et al. “Engenharia do banco de teste de usuário aberto da computação científica quântica”. IEEE Transactions on Quantum Engineering 2, 1–32 (2021).
https: / / doi.org/ 10.1109 / TQE.2021.3096480

[21] Colin D Bruzewicz, John Chiaverini, Robert McConnell e Jeremy M Sage. “Computação quântica de íons aprisionados: progresso e desafios”. Applied Physics Reviews 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio e Patrick J Coles. “Um otimizador adaptativo para algoritmos variacionais de medição frugal”. Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma e Jimmy Ba. “Adam: Um método para otimização estocástica” (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jorgensen e Jeppe Olsen. “Teoria da estrutura eletrônica molecular”. John Wiley & Filhos. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

[25] Tom Schaul, Ioannis Antonoglou e David Silver. “Testes unitários para otimização estocástica”. Em Yoshua Bengio e Yann LeCun, editores, 2ª Conferência Internacional sobre Representações de Aprendizagem, ICLR 2014, Banff, AB, Canadá, 14 a 16 de abril de 2014, Anais da Conferência. (2014). url: http:/​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi e John C Duchi. “A importância de melhores modelos na otimização estocástica”. Proceedings of the National Academy of Sciences 116, 22924–22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

[27] Billy Jin, Katya Scheinberg e Miaolan Xie. “Limites de complexidade de alta probabilidade para pesquisa de linha baseada em oráculos estocásticos” (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly e Katya Scheinberg. “Análise da taxa de convergência de um método estocástico de região de confiança via supermartingales”. INFORMS Journal on Optimization 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette e Katya Scheinberg. “Um método de busca de linha estocástica com análise de complexidade esperada”. SIAM Journal on Optimization 30, 349–376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

[30] Albert S Berahas, Liyuan Cao e Katya Scheinberg. “Análise da taxa de convergência global de um algoritmo genérico de busca linear com ruído”. SIAM Journal on Optimization 31, 1489–1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

[31] Coralia Cartis, Nicholas IM Gould e Ph L Toint. “Sobre a complexidade da descida mais íngreme, os métodos de Newton e de Newton regularizados para problemas de otimização não convexa sem restrições”. Siam Journal on Optimization 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Coralia Cartis, Nicholas IM Gould e Philippe L Toint. “Sobre a complexidade do oráculo de algoritmos de primeira ordem e livres de derivados para minimização não convexa suave”. SIAM Journal on Optimization 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder e Aaron Sidford. “Limites inferiores para encontrar pontos estacionários I”. Programação matemática 184, 71–120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder e Aaron Sidford. ““convexo até que se prove o contrário”: Aceleração sem dimensão da descida do gradiente em funções não convexas”. Na Conferência Internacional sobre Aprendizado de Máquina. Páginas 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Chi Jin, Praneeth Netrapalli e Michael I Jordan. “A descida de gradiente acelerada escapa dos pontos de sela mais rapidamente do que a descida de gradiente”. Em Conferência sobre a Teoria da Aprendizagem. Páginas 1042–1085. PMLR (2018). url: https:/​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi e Guanghui Lan. “Métodos estocásticos de ordem zero e primeira para programação estocástica não convexa”. SIAM Journal on Optimization 23, 2341–2368 (2013).
https: / / doi.org/ 10.1137 / 120880811

[37] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro e Blake Woodworth. “Limites inferiores para otimização estocástica não convexa” (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin e Tong Zhang. "Spider: Otimização não convexa quase ótima via estimador diferencial integrado de caminho estocástico". Em S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi e R. Garnett, editores, Advances in Neural Information Processing Systems. Volume 31. Curran Associates, Inc. (2018). url: https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

[39] Shiro Tamiya e Hayata Yamasaki. “Otimização bayesiana da linha de gradiente estocástico: reduzindo tiros de medição na otimização de circuitos quânticos parametrizados” (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan e Eugene Paul Wigner. “über das paulische äquivalenzverbot”. Em As Obras Completas de Eugene Paul Wigner. Páginas 109–129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac e Nathan Killoran. “Avaliando gradientes analíticos em hardware quântico”. Revisão Física A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon e K Birgitta Whaley. “Funções de onda de cluster acopladas unitárias generalizadas para computação quântica”. Journal of Chemical Theory and Computation 15, 311–324 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b01004

[43] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik e Jeremy L O'brien. “Um solucionador de autovalor variacional em um processador quântico fotônico”. Nature Communications 5, 1–7 (2014). url: https:/​/​doi.org/​10.1038/​ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

[44] Ilya G Ryabinkin, Tzu-Ching Yen, Scott N Genin e Artur F Izmaylov. “Método de cluster acoplado Qubit: uma abordagem sistemática à química quântica em um computador quântico”. Journal of Chemical Theory and Computation 14, 6317-6326 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b00932

[45] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes e Sophia E Economou. “qubit-ADAPT-VQE: Um algoritmo adaptativo para a construção de ansätze com eficiência de hardware em um processador quântico”. PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray e Matthew Otten. “Método de Acoplamento Seletivo Unitário”. Quantum 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi e Frederic T Chong. “$ o (n^3) $ custo de medição para autosolver quântico variacional em hamiltonianos moleculares”. IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly e Katya Scheinberg. “Otimização estocástica usando um método de região de confiança e modelos aleatórios”. Programação Matemática 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis e Jorge Nocedal. “Métodos de otimização para aprendizado de máquina em larga escala”. Siam Review 60, 223–311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

[50] Yoel Drori e Ohad Shamir. “A complexidade de encontrar pontos estacionários com descida de gradiente estocástico”. Na Conferência Internacional sobre Aprendizado de Máquina. Páginas 2658–2667. PMLR (2020). url: https:/​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin e Tong Zhang. “Análise precisa para SGD não convexo escapando de pontos de sela”. Em Conferência sobre Teoria da Aprendizagem. Páginas 1192–1234. PMLR (2019). url: https:/​/​proceedings.mlr.press/​v99/​fang19a.html.
https://​/​proceedings.mlr.press/​v99/​fang19a.html

[52] S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale e Sanjiv Kumar. “Métodos adaptativos para otimização não convexa”. Nos Anais da 32ª Conferência sobre Sistemas de Processamento de Informações Neurais (NIPS 2018). (2018). url: https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Léon Bottou e Olivier Bousquet. “As compensações da aprendizagem em larga escala”. Em J. Platt, D. Koller, Y. Singer e S. Roweis, editores, Advances in Neural Information Processing Systems. Volume 20. Curran Associates, Inc. (2007). url: https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

[54] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva e Robert S Smith. “Uma plataforma de nuvem clássica quântica otimizada para algoritmos híbridos variacionais”. Ciência e Tecnologia Quântica 5, 024003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7559

[55] HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac e Peter Zoller. “Computação quântica com átomos neutros”. Journal of Modern Optics 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo e Kristan Temme. “Reduzindo qubits para simular hamiltonianos fermiônicos” (2017). arXiv:1701.08213.
arXiv: 1701.08213

[57] MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, Gabriele Agliardi, Merav Aharoni, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Sashwat Anagolum, Eli Arbel, Abraham Asfaw, Anish Athalye, Artur Avkhadiev, et al. “Qiskit: uma estrutura de código aberto para computação quântica” (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu e Jorge Nocedal. “Algoritmo 778: L-BFGS-B: Sub-rotinas Fortran para otimização limitada em larga escala”. ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

[59] Raghu Bollapragada, Richard Byrd e Jorge Nocedal. “Estratégias de amostragem adaptáveis ​​para otimização estocástica”. SIAM Journal on Optimization 28, 3312–3343 (2018).
https: / / doi.org/ 10.1137 / 17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi e Ping Tak Peter Tang. “Um método L-BFGS de lote progressivo para aprendizado de máquina”. Na Conferência Internacional sobre Aprendizado de Máquina. Páginas 620–629. PMLR (2018). url: https:/​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html

[61] Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh e Fatemeh S Hashemi. “Sobre taxas de amostragem em recursões baseadas em simulação”. SIAM Journal on Optimization 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma e Patrick J Coles. “Amostragem de operadores para otimização frugal em algoritmos variacionais” (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu e Wotao Yin. “Iteração de gradiente estocástico de blocos para otimização convexa e não convexa”. SIAM Journal on Optimization 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Citado por

[1] Matt Menickelly, Stefan M. Wild e Miaolan Xie, “A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers”, arXiv: 2302.09128, (2023).

[2] Kosuke Ito, “Alocação de tiro adaptável com reconhecimento de latência para algoritmos quânticos variacionais eficientes em tempo de execução”, arXiv: 2302.04422, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-03-16 18:30:45). 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 2023-03-16 18:30:43: Não foi possível buscar os dados citados por 10.22331 / q-2023-03-16-949 do Crossref. Isso é normal se o DOI foi registrado recentemente.

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.

Carimbo de hora:

Mais de Diário Quântico