Configuração de parâmetros na otimização quântica aproximada de problemas ponderados

Configuração de parâmetros na otimização quântica aproximada de problemas ponderados

Nó Fonte: 3070550

Shree Hari Suresh Babu1, Dylan Herman1, Ruslan Shaydulin1, João Basso2, Shouvanik Chakrabarti1, Yue Sun1e Marco Pistoia1

1Pesquisa Aplicada em Tecnologia Global, JPMorgan Chase, Nova York, NY 10017
2Departamento de Matemática, Universidade da Califórnia, Berkeley, CA 94720

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

Sumário

O Algoritmo de Otimização Aproximada Quântica (QAOA) é um algoritmo candidato líder para resolver problemas de otimização combinatória em computadores quânticos. No entanto, em muitos casos, o QAOA requer otimização de parâmetros computacionalmente intensiva. O desafio da otimização de parâmetros é particularmente agudo no caso de problemas ponderados, para os quais os autovalores do operador de fase são não inteiros e o cenário energético QAOA não é periódico. Neste trabalho, desenvolvemos heurísticas de parametrização para QAOA aplicadas a uma classe geral de problemas ponderados. Primeiro, derivamos parâmetros ótimos para QAOA com profundidade $p=1$ aplicados ao problema MaxCut ponderado sob diferentes suposições sobre os pesos. Em particular, provamos rigorosamente a sabedoria convencional de que, no caso médio, o primeiro ótimo local próximo de zero fornece parâmetros QAOA globalmente ótimos. Em segundo lugar, para $pgeq 1$ provamos que o cenário energético QAOA para MaxCut ponderado se aproxima do caso não ponderado sob um simples reescalonamento de parâmetros. Portanto, podemos utilizar parâmetros obtidos anteriormente para MaxCut não ponderado para problemas ponderados. Finalmente, provamos que para $p=1$ o objetivo QAOA concentra-se nitidamente em torno de sua expectativa, o que significa que nossas regras de definição de parâmetros são válidas com alta probabilidade para uma instância ponderada aleatoriamente. Validamos numericamente esta abordagem em gráficos ponderados gerais e mostramos que, em média, a energia QAOA com os parâmetros fixos propostos está a apenas $ 1.1 $ pontos percentuais de distância daquela com parâmetros otimizados. Terceiro, propomos um esquema de reescalonamento heurístico geral inspirado nos resultados analíticos para MaxCut ponderado e demonstramos sua eficácia usando QAOA com o misturador de preservação de peso XY Hamming aplicado ao problema de otimização de portfólio. Nossa heurística melhora a convergência dos otimizadores locais, reduzindo o número de iterações em 7.4x, em média.

Este trabalho investiga regras de parametrização para QAOA, um algoritmo heurístico quântico líder, aplicado a uma classe geral de problemas de otimização combinatória. A otimização de parâmetros é um gargalo significativo para a aplicação no curto prazo. Uma heurística geral de escalonamento de parâmetros para transferência de parâmetros QAOA entre instâncias de problemas ponderados é proposta e resultados rigorosos mostrando a eficácia deste procedimento no MaxCut são apresentados. Além disso, os números mostram que este procedimento reduz significativamente o tempo de treinamento do QAOA para otimização de portfólio, o que é um problema importante na engenharia financeira

► dados BibTeX

► Referências

[1] Michael A Nielsen e Isaac L Chuang. “Computação quântica e informação quântica”. Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[2] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia e Yuri Alexeev. “Uma pesquisa sobre computação quântica para finanças” (2022). URL: https://​/​doi.org/​10.48550/​arXiv.2201.02773.
https://​/​doi.org/​10.48550/​arXiv.2201.02773

[3] Tad Hogg e Dmitriy Portnov. “Otimização quântica”. Ciências da Informação 128, 181–197 (2000).
https:/​/​doi.org/​10.1016/​s0020-0255(00)00052-9

[4] Edward Farhi, Jeffrey Goldstone e Sam Gutmann. “Um algoritmo de otimização aproximada quântica” (2014). url: https:/​/​doi.org/​10.48550/​arXiv.1411.4028.
https://​/​doi.org/​10.48550/​arXiv.1411.4028

[5] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli e Rupak Biswas. “Do algoritmo de otimização quântica aproximada a um operador quântico alternado ansatz”. Algoritmos 12, 34 (2019). url: https:///​/​doi.org/​10.3390/​a12020034.
https: / / doi.org/ 10.3390 / a12020034

[6] Sami Boulebnane e Ashley Montanaro. “Resolvendo problemas de satisfatibilidade booleana com o algoritmo de otimização quântica aproximada” (2022). URL: https://​/​doi.org/​10.48550/​arXiv.2208.06909.
https://​/​doi.org/​10.48550/​arXiv.2208.06909

[7] João Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga e Leo Zhou. “O algoritmo de otimização quântica aproximada em alta profundidade para maxcut em gráficos regulares de grande circunferência e o modelo Sherrington-Kirkpatrick”. Anais da Conferência sobre a Teoria da Computação, Comunicação e Criptografia Quântica 7, 1–21 (2022).
https://​/​doi.org/​10.4230/​LIPICS.TQC.2022.7

[8] Mateus B. Hastings. “Um algoritmo clássico que também supera $ frac{1}{2}+ frac{2}{pi}frac{1}{sqrt{d}}$ para corte máximo de circunferência alta” (2021). URL: https://​/​doi.org/​10.48550/​arXiv.2111.12641.
https://​/​doi.org/​10.48550/​arXiv.2111.12641

[9] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski e Travis S. Humble. “Transferência de parâmetros para otimização quântica aproximada de MaxCut ponderado”. Transações ACM em Computação Quântica 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[10] Sami Boulebnane, Xavier Lucas, Agnes Meyder, Stanislaw Adaszewski e Ashley Montanaro. “Amostragem conformacional de peptídeos usando o algoritmo de otimização quântica aproximada”. npj Informação Quântica 9, 70 (2023). URL: https://​/​doi.org/​10.1038/​s41534-023-00733-5.
https:/​/​doi.org/​10.1038/​s41534-023-00733-5

[11] Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia e Thomas Wellens. “Benchmarking do desempenho da otimização de portfólio com qaoa”. Processamento de Informação Quântica 22, 25 (2022).
https:/​/​doi.org/​10.1007/​s11128-022-03766-5

[12] Sami Boulebnane e Ashley Montanaro. “Predição de parâmetros para o algoritmo de otimização quântica aproximada para corte máximo do limite de tamanho infinito” (2021). URL: https://​/​doi.org/​10.48550/​arXiv.2110.10685.
https://​/​doi.org/​10.48550/​arXiv.2110.10685

[13] Edward Farhi, Jeffrey Goldstone, Sam Gutmann e Leo Zhou. “O algoritmo de otimização quântica aproximada e o modelo Sherrington-Kirkpatrick em tamanho infinito”. Quântico 6, 759 (2022).
https:/​/​doi.org/​10.22331/​q-2022-07-07-759

[14] Amir Dembo, Andrea Montanari e Subhabrata Sen. “Cortes extremos de gráficos aleatórios esparsos”. Os Anais da Probabilidade 45 (2017).
https://​/​doi.org/​10.1214/​15-aop1084

[15] Gavin E Crooks. “Desempenho do algoritmo de otimização quântica aproximada no problema de corte máximo” (2018). url: https://​/​doi.org/​10.48550/​arXiv.1811.08419.
https://​/​doi.org/​10.48550/​arXiv.1811.08419

[16] Michael Streif e Martin Leib. “Treinando o algoritmo de otimização aproximada quântica sem acesso a uma unidade de processamento quântico”. Ciência e Tecnologia Quântica 5, 034008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8c2b

[17] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler e Mikhail D. Lukin. “Algoritmo de otimização aproximada quântica: desempenho, mecanismo e implementação em dispositivos de curto prazo”. Revisão Física X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[18] Ruslan Shaydulin, Ilya Safro e Jeffrey Larson. “Métodos Multistart para otimização quântica aproximada”. Na Conferência IEEE de Computação Extrema de Alto Desempenho. Páginas 1–8. (2019).
https://​/​doi.org/​10.1109/​hpec.2019.8916288

[19] Xinwei Lee, Yoshiyuki Saito, Dongsheng Cai e Nobuyoshi Asai. “Estratégia de fixação de parâmetros para algoritmo de otimização quântica aproximada”. 2021 Conferência Internacional IEEE sobre Computação e Engenharia Quântica (QCE) (2021).
https://​/​doi.org/​10.1109/​qce52317.2021.00016

[20] Stefan H. Sack e Maksym Serbyn. “Inicialização de recozimento quântico do algoritmo de otimização aproximada quântica”. Quântico 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[21] Ohad Amosy, Tamuz Danzig, Ely Porat, Gal Chechik e Adi Makmal. “Algoritmo de otimização aproximada quântica livre de iterativo usando redes neurais” (2022). URL: https://​/​doi.org/​10.48550/​arXiv.2208.09888.
https://​/​doi.org/​10.48550/​arXiv.2208.09888

[22] Danylo Lykov, Roman Schutski, Alexey Galda, Valeri Vinokur e Yuri Alexeev. “Simulador quântico de rede tensor com paralelização dependente de etapas”. Em 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Páginas 582–593. (2022).
https: / / doi.org/ 10.1109 / QCE53715.2022.00081

[23] Matija Medvidović e Giuseppe Carleo. “Simulação variacional clássica do algoritmo de otimização quântica aproximada”. npj Informação Quântica 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[24] Ruslan Shaydulin e Stefan M. Wild. “Explorar a simetria reduz o custo de treinamento do QAOA”. Transações IEEE em Engenharia Quântica 2, 1–9 (2021).
https://​/​doi.org/​10.1109/​tqe.2021.3066275

[25] Ruslan Shaydulin e Yuri Alexeev. “Avaliando algoritmo de otimização aproximada quântica: um estudo de caso”. Décima Conferência Internacional de Computação Verde e Sustentável (2019).
https: / / doi.org/ 10.1109 / IGSC48788.2019.8957201

[26] Fernando GSL Brandão, Michael Broughton, Edward Farhi, Sam Gutmann e Hartmut Neven. “Para parâmetros de controle fixos, o valor da função objetivo do algoritmo de otimização aproximada quântica concentra-se para instâncias típicas” (2018). URL: https://​/​doi.org/​10.48550/​arXiv.1812.04170.
https://​/​doi.org/​10.48550/​arXiv.1812.04170

[27] V. Akshay, D. Rabinovich, E. Campos e J. Biamonte. “Concentrações de parâmetros na otimização quântica aproximada”. Revisão Física A 104 (2021).
https://​/​doi.org/​10.1103/​physreva.104.l010401

[28] Phillip C. Lotshaw, Travis S. Humble, Rebekah Herrman, James Ostrowski e George Siopsis. “Limites de desempenho empírico para otimização quântica aproximada”. Processamento de Informação Quântica 20, 403 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03342-3

[29] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev e Ilya Safro. “Transferibilidade de parâmetros qaoa ótimos entre gráficos aleatórios”. Em 2021, Conferência Internacional IEEE sobre Computação e Engenharia Quântica (QCE). Páginas 171–180. (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00034

[30] Xinwei Lee, Ningyi Xie, Dongsheng Cai, Yoshiyuki Saito e Nobuyoshi Asai. “Uma estratégia de inicialização progressiva em profundidade para algoritmo de otimização quântica aproximada”. Matemática 11, 2176 (2023).
https://​/​doi.org/​10.3390/​math11092176

[31] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev e Prasanna Balaprakash. “Aprender a otimizar circuitos quânticos variacionais para resolver problemas combinatórios”. Anais da Conferência AAAI sobre Inteligência Artificial 34, 2367–2375 (2020).
https: / / doi.org/ 10.1609 / aaai.v34i03.5616

[32] Guillaume Verdon, Michael Broughton, Jarrod R. McClean, Kevin J. Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven e Masoud Mohseni. “Aprendendo a aprender com redes neurais quânticas por meio de redes neurais clássicas” (2019). URL: https://​/​doi.org/​10.48550/​arXiv.1907.05415.
https://​/​doi.org/​10.48550/​arXiv.1907.05415

[33] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev e Prasanna Balaprakash. “Otimização de circuitos quânticos variacionais baseados em aprendizagem por reforço para problemas combinatórios” (2019). URL: https://​/​doi.org/​10.48550/​arXiv.1911.04574.
https://​/​doi.org/​10.48550/​arXiv.1911.04574

[34] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng e Giuseppe E. Santoro. “Otimização quântica assistida por aprendizagem por reforço”. Pesquisa de Revisão Física 2 (2020).
https: / / doi.org/ 10.1103 / physrevresearch.2.033446

[35] Mahabubul Alam, Abdullah Ash-Saki e Swaroop Ghosh. “Acelerando algoritmo de otimização aproximada quântica usando aprendizado de máquina”. Conferência e Exposição de Design, Automação e Teste 2020 na Europa (DATA) (2020).
https://​/​doi.org/​10.23919/​date48585.2020.9116348

[36] Jiahao Yao, Lin Lin e Marin Bukov. “Aprendizagem por reforço para preparação do estado fundamental de muitos corpos inspirada na direção contradiabática”. Revisão Física X 11 (2021).
https: / / doi.org/ 10.1103 / physrevx.11.031070

[37] Zhihui Wang, Stuart Hadfield, Zhang Jiang e Eleanor G. Rieffel. “Algoritmo de otimização aproximada quântica para MaxCut: uma visão fermiônica”. Revisão Física A 97 (2018).
https: / / doi.org/ 10.1103 / physreva.97.022304

[38] Jonathan Wurtz e Danylo Lykov. “A conjectura de ângulo fixo para QAOA em gráficos MaxCut regulares” (2021). URL: https://​/​doi.org/​10.48550/​arXiv.2107.00677.
https://​/​doi.org/​10.48550/​arXiv.2107.00677

[39] Stuart Hadfield. “Algoritmos quânticos para computação científica e otimização aproximada” (2018). url: https:///​/​doi.org/​10.48550/​1805.03265.
https: / / doi.org/ 10.48550 / 1805.03265

[40] Paul Glasserman. “Métodos de Monte Carlo em engenharia financeira”. Volume 53. Springer. (2004).
https:/​/​doi.org/​10.1007/​978-0-387-21617-1

[41] Walter Rudin. “Análise real e complexa”. McGraw-Hill. (1974).

[42] Walter Rudin. “Princípios de análise matemática”. McGraw-hill. (1976).

[43] Colin McDiarmid. “Sobre o método das diferenças limitadas”. Página 148–188. Série de notas de palestras da London Mathematical Society. Cambridge University Press. (1989).
https: / / doi.org/ 10.1017 / CBO9781107359949.008

[44] Lutz Warnke. “Sobre o método das diferenças limitadas típicas”. Combinatória, Probabilidade e Computação 25, 269–299 (2016).
https: / / doi.org/ 10.1017 / S0963548315000103

[45] Roman Vershinin. “Probabilidade de alta dimensão: uma introdução às aplicações em ciência de dados”. Série Cambridge em Matemática Estatística e Probabilística. Cambridge University Press. (2018).
https: / / doi.org/ 10.1017 / 9781108231596

[46] João Basso, David Gamarnik, Song Mei e Leo Zhou. “Desempenho e limitações do QAOA em níveis constantes em grandes hipergráficos esparsos e modelos de spin glass”. 2022 63º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS) (2022).
https://​/​doi.org/​10.1109/​focs54457.2022.00039

[47] G Parisi. “Uma sequência de soluções aproximadas para o modelo sk para óculos de spin”. Journal of Physics A: Matemática e Geral 13, L115 (1980).
https:/​/​doi.org/​10.1088/​0305-4470/​13/​4/​009

[48] Michel Talagrand. “A fórmula parisiense”. Anais de Matemática (2006).
https: / / doi.org/ 10.4007 / annals.2006.163.221

[49] Dmitry Panchenko. “O modelo Sherrington-Kirkpatrick”. Springer Ciência e Mídia de Negócios. (2013).
https:/​/​doi.org/​10.1007/​978-1-4614-6289-7

[50] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz e Phillip C Lotshaw. “QAOAKit: Um kit de ferramentas para estudo reproduzível, aplicação e verificação de QAOA”. Segundo Workshop Internacional sobre Software de Computação Quântica (2021).
https://​/​doi.org/​10.1109/​QCS54837.2021.00011

[51] João Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga e Leo Zhou. “O algoritmo de otimização quântica aproximada em alta profundidade para maxcut em gráficos regulares de grande circunferência e o modelo sherrington-kirkpatrick” (2021). URL: https://​/​doi.org/​10.48550/​arXiv.2110.14206.
https://​/​doi.org/​10.48550/​arXiv.2110.14206

[52] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky e Marco Pistoia. “Otimização restrita via dinâmica quântica zeno”. Física das Comunicações 6, 219 (2023).
https:/​/​doi.org/​10.1038/​s42005-023-01331-9

[53] N. Slate, E. Matwiejew, S. Marsh e JB Wang. “Otimização de portfólio baseada em caminhada quântica”. Quântico 5, 513 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-28-513

[54] Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin e Stefan Dulman. “Experiências de reequilíbrio de portfólio usando o operador de alternância quântica ansatz” (2019). url: https://​/​doi.org/​10.48550/​arXiv.1911.05296.
https://​/​doi.org/​10.48550/​arXiv.1911.05296

[55] Tianyi Hao, Ruslan Shaydulin, Marco Pistoia e Jeffrey Larson. “Explorando energia com restrição na otimização quântica variacional restrita”. 2022 Terceiro Workshop Internacional IEEE/ACM sobre Software de Computação Quântica (QCS) (2022).
https://​/​doi.org/​10.1109/​qcs56647.2022.00017

[56] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun e Marco Pistoia. “O alinhamento entre o estado inicial e o mixer melhora o desempenho do qaoa para otimização restrita”. npj Informação Quântica 9, 121 (2023).
https:/​/​doi.org/​10.1038/​s41534-023-00787-5

[57] “Financiamento Qiskit”. https://​/​qiskit.org/​documentation/​finance/​.
https://​/​qiskit.org/​documentation/​finance/​

[58] Steven G. Johnson. “O pacote de otimização não linear NLopt” (2022). http://​/​github.com/​stevengj/​nlopt.
http://​/​github.com/​stevengj/​nlopt

[59] Michael JD Powell. “O algoritmo BOBYQA para otimização com restrições limitadas sem derivadas”. Relatório Cambridge NA NA2009/​06 26 (2009).

[60] Ruslan Shaydulin e Stefan M. Wild. “Importância da largura de banda do kernel no aprendizado de máquina quântica”. Revisão Física A 106 (2022).
https: / / doi.org/ 10.1103 / physreva.106.042407

[61] Abdulkadir Canatar, Evan Peters, Cengiz Pehlevan, Stefan M. Wild e Ruslan Shaydulin. “A largura de banda permite generalização em modelos de kernel quântico” (2022). url: https://​/​doi.org/​10.48550/​arXiv.2206.06686.
https://​/​doi.org/​10.48550/​arXiv.2206.06686

[62] Kaining Zhang, Liu Liu, Min-Hsiu Hsieh e Dacheng Tao. “Escapando do platô árido por meio de inicializações gaussianas em circuitos quânticos variacionais profundos”. Em Avanços em Sistemas de Processamento de Informação Neural. Volume 35, páginas 18612–18627. (2022).

Citado por

[1] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia e Yuri Alexeev, “Computação quântica para finanças”, Nature Reviews Física 5 8, 450 (2023).

[2] Abid Khan, Bryan K. Clark e Norm M. Tubman, “Pré-otimizando autosolventes quânticos variacionais com redes tensores”, arXiv: 2310.12965, (2023).

[3] Igor Gaidai e Rebekah Herrman, “Análise de desempenho de QAOA multiângulo para p> 1”, arXiv: 2312.00200, (2023).

[4] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky e Marco Pistoia, “Otimização restrita via dinâmica Zeno quântica”, Física das Comunicações 6 1, 219 (2023).

[5] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman , Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky e Marco Pistoia, “Evidência de vantagem de escala para o algoritmo de otimização quântica aproximada em um problema classicamente intratável”, arXiv: 2308.02342, (2023).

[6] Filip B. Maciejewski, Stuart Hadfield, Benjamin Hall, Mark Hodson, Maxime Dupont, Bram Evert, James Sud, M. Sohaib Alam, Zhihui Wang, Stephen Jeffrey, Bhuvanesh Sundar, P. Aaron Lott, Shon Grabbe, Eleanor G Rieffel, Matthew J. Reagor e Davide Venturelli, “Projeto e execução de circuitos quânticos usando dezenas de qubits supercondutores e milhares de portas para problemas densos de otimização de Ising”, arXiv: 2308.12423, (2023).

[7] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele e Procolo Lucignano, “Convergência de QAOA digitalizado-contradiabático: profundidade do circuito versus parâmetros livres”, arXiv: 2307.14079, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2024-01-19 00:28:46). 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 2024-01-19 00:28:44).

Carimbo de hora:

Mais de Diário Quântico