QAOA iniciado a quente com mixers personalizados provavelmente converge e supera computacionalmente o corte máximo de Goemans-Williamson em profundidades de circuito baixas

QAOA iniciado a quente com mixers personalizados provavelmente converge e supera computacionalmente o corte máximo de Goemans-Williamson em profundidades de circuito baixas

Carimbo de data / hora: 26 de setembro de 2023 9:22

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3 e Swati Gupta4

1CCS-3 Ciências da Informação, Laboratório Nacional de Los Alamos, Los Alamos, NM 87544, EUA
2Instituto de Tecnologia da Geórgia, Atlanta, GA 30332, EUA
3Instituto de Pesquisa Tecnológica da Geórgia, Atlanta, GA 30332, EUA
4Sloan School of Management, Instituto de Tecnologia de Massachusetts, Cambridge, MA 02142, EUA

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

Sumário

Generalizamos o Algoritmo de Otimização Aproximada Quântica (QAOA) de Farhi et al. (2014) para permitir estados iniciais separáveis ​​arbitrários com misturadores correspondentes, de modo que o estado inicial seja o estado mais excitado do hamiltoniano de mistura. Demonstramos esta versão do QAOA, que chamamos de $QAOA-warmest$, simulando Max-Cut em gráficos ponderados. Inicializamos o estado inicial como $warm-start$ usando aproximações dimensionais $2$ e $3$ obtidas usando projeções aleatórias de soluções para o programa semidefinido do Max-Cut e definimos um $mixer customizado dependente de inicialização a quente$. Mostramos que essas partidas a quente inicializam o circuito QAOA com aproximações de fator constante de $ 0.658 $ para partidas a quente $ 2 $ dimensionais e $ 0.585 $ para $ 3 $ dimensionais para gráficos com pesos de aresta não negativos, melhorando o trivial anteriormente conhecido ( ou seja, $0.5$ para inicialização padrão) limites de pior caso em $p=0$. Na verdade, esses fatores limitam a aproximação alcançada para Max-Cut em profundidades de circuito mais altas, uma vez que também mostramos que QAOA-mais quente com qualquer estado inicial separável converge para Max-Cut sob o limite adiabático como $prightarrow infty$. No entanto, a escolha dos arranques a quente tem um impacto significativo na taxa de convergência para Max-Cut, e mostramos empiricamente que os nossos arranques a quente alcançam uma convergência mais rápida em comparação com as abordagens existentes. Além disso, nossas simulações numéricas mostram cortes de maior qualidade em comparação com o QAOA padrão, o algoritmo clássico de Goemans-Williamson e um QAOA iniciado a quente sem misturadores personalizados para uma biblioteca de instâncias de gráficos de $1148$ (até nós de $11$) e profundidade $p=8 $. Mostramos ainda que o QAOA mais quente supera o QAOA padrão de Farhi et al. em experimentos em hardware IBM-Q e Quantinuum atuais.

QAOA iniciado a quente com mixers personalizados provavelmente converge e supera computacionalmente o Max-Cut de Goemans-Williamson em baixas profundidades de circuito PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

Imagem em destaque: Desempenho do QAOA mais quente (com partidas a quente) e do QAOA padrão em função da profundidade do QAOA para uma simulação ideal (tracejada) e com ruído (pontilhada). Para o gráfico de 20 nós escolhido, GW atinge uma razão de aproximação de 0.912, enquanto no caso ideal, QAOA-warmest supera GW para $p geq 2$ enquanto QAOA padrão requer $p > 4$. A simulação de ruído é baseada em dados de calibração do dispositivo Guadalupe do IBM-Q.

Resumo popular

O algoritmo de otimização aproximada quântica (QAOA) é uma técnica híbrida quântica-clássica para otimização combinatória que promete ser mais poderosa do que qualquer otimizador clássico. Neste trabalho exemplificamos seu potencial em um problema fundamental de otimização combinatória, conhecido como Max-Cut, onde o melhor algoritmo clássico possível é o de Goemans e Williamson (GW). Conseguimos isso introduzindo partidas a quente obtidas classicamente no QAOA, com operadores de mistura modificados, e mostramos computacionalmente que isso supera o GW. Modificamos o algoritmo quântico de forma adequada para manter a conexão com a computação quântica adiabática; discutimos teoria e fornecemos evidências numéricas e experimentais que mostram a promessa de nossa abordagem.

► dados BibTeX

► Referências

[1] 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

[2] Aram W. Harrow e Ashley Montanaro. “Supremacia computacional quântica”. Natureza 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Edward Farhi, Jeffrey Goldstone e Sam Gutmann. “Um algoritmo de otimização quântica aproximada” (2014).

[4] Iain Dunning, Swati Gupta e John Silberholz. “O que funciona melhor quando? Uma avaliação sistemática de heurísticas para Max-Cut e QUBO”. INFORMA Revista de Computação 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Michel X Goemans e David P Williamson. “Algoritmos de aproximação melhorados para problemas de corte máximo e satisfatibilidade usando programação semidefinida”. Jornal do ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Samuel Burer e Renato DC Monteiro. “Um algoritmo de programação não linear para resolver programas semidefinidos via fatoração de baixo posto”. Programação Matemática 95, 329–357 (2003).
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

[7] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, e outros. “Qiskit: Uma estrutura de código aberto para computação quântica” (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard e Eugene Tang. “O QAOA fica preso a partir de uma boa corda clássica” (2022).

[9] Daniel J. Egger, Jakub Mareček e Stefan Woerner. “Otimização quântica de partida a quente”. Quântico 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng e Maksym Serbyn. “Inicialização gananciosa recursiva do algoritmo de otimização quântica aproximada com melhoria garantida”. Revisão Física A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

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

[12] 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

[13] 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

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

[15] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner e Daniel J Egger. “Escalonamento do algoritmo de otimização quântica aproximada em hardware supercondutor baseado em qubit”. Quântico 6, 870 (2022).
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

[16] Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis e Travis S Humble. “Escalonando a otimização aproximada quântica em hardware de curto prazo”. Relatórios Científicos 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[17] Gian Giacomo Guerreschi e Anne Y Matsuura. “QAOA para corte máximo requer centenas de qubits para aceleração quântica”. Relatórios científicos 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra e Vedran Dunjko. “Para quântico ou não quântico: rumo à seleção de algoritmos na otimização quântica de curto prazo”. Ciência e Tecnologia Quântica 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell e Edward Dahl. “QAOA da mais alta ordem”. Em 2022, 19ª Conferência Internacional IEEE sobre Software Architecture Companion (ICSA-C). Páginas 141–146. IEEE (2022).
https://​/​doi.org/​10.1109/​ICSA-C54293.2022.00035

[20] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble e George Siopsis. “Impacto das estruturas gráficas para QAOA no maxcut”. Processamento de Informação Quântica 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​e Daniel J Egger. “Compressão e otimização aproximada quântica” (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg e Ilya Safro. “Simetrias clássicas e o algoritmo de otimização quântica aproximada”. Processamento de Informação Quântica 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz e Peter Love. “Garantias de desempenho do algoritmo de otimização aproximada quântica Maxcut para p> 1”. Revisão Física A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone e Sam Gutmann. “Algoritmos quânticos para arquiteturas qubit fixas” (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig e Eugene Tang. “Obstáculos à otimização quântica variacional da proteção de simetria”. Cartas de Revisão Física 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik e Sam Gutmann. “O algoritmo de otimização quântica aproximada precisa ver o gráfico inteiro: um caso típico” (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig e Eugene Tang. “Algoritmos híbridos quânticos-clássicos para coloração aproximada de gráficos”. Quântico 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. “Algoritmos de aproximação de profundidade limitada clássica e quântica” (2019).

[29] Kunal Marwaha. “Algoritmo clássico local de corte máximo supera $ p = 2 $ QAOA em gráficos regulares de alta circunferência”. Quântico 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak e Kunal Marwaha. “Algoritmos clássicos e limitações quânticas para corte máximo em gráficos de alta circunferência” (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler e Swati Gupta. “Fazendo uma ponte entre clássico e quântico com partidas a quente inicializadas por SDP para QAOA”. Transações ACM em Computação Quântica (2022).
https: / / doi.org/ 10.1145 / 3549554

[32] 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 (2019).
https: / / doi.org/ 10.3390 / a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy e Eleanor G. Rieffel. “Misturadores $xy$: Resultados analíticos e numéricos para o operador quântico alternado ansatz”. Física. Rev.A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[34] Linghua Zhu, Ho Lun Tang, George S. Barron, FA Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes e Sophia E. Economou. “Algoritmo de otimização aproximada quântica adaptativa para resolver problemas combinatórios em um computador quântico”. Física. Rev. Pesquisa 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bartschi e Stephan Eidenbenz. “Misturadores Grover para QAOA: Mudando a complexidade do projeto do misturador para a preparação do estado”. Em 2020, Conferência Internacional IEEE sobre Computação e Engenharia Quântica (QCE). Páginas 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel e Zhihui Wang. “Circuito quântico quase ideal para busca não estruturada de Grover usando um campo transversal”. Revisão Física A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Amor K Grover. “Um algoritmo mecânico quântico rápido para pesquisa em banco de dados”. Em Anais do vigésimo oitavo simpósio anual da ACM sobre Teoria da Computação. Páginas 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer e Renato DC Monteiro. “Heurísticas de relaxamento de nível 2 para max-cut e outros programas quadráticos binários”. SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari e Roberto Imbuzeiro Oliveira. “Resolvendo problemas de sdps para sincronização e maxcut através da desigualdade de grothendieck”. Em Conferência sobre teoria da aprendizagem. Páginas 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh e Kevin Thompson. “Uma aproximação ideal do estado do produto para hamiltonianos quânticos 2-locais com termos positivos” (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Reuben Tate e Swati Gupta. “Ci-qube”. Repositório GitHub (2021). url: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. “Quão bom é o algoritmo Goemans – Williamson MAX-CUT?”. SIAM Journal on Computing 29, 336–350 (1999).
https: / / doi.org/ 10.1137 / S0097539797321481

[43] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. “Otimização quântica aproximada de problemas de grafos não planares em um processador supercondutor planar”. Física da Natureza 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-y

[44] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay e Jay M. Gambetta. “Mitigando erros de medição em experimentos multiqubit”. Física. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] George S. Barron e Christopher J. Wood. “Mitigação de erros de medição para algoritmos quânticos variacionais” (2020).

[46] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan , Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu e Xiaoqiang Zheng. “TensorFlow: aprendizado de máquina em larga escala em sistemas heterogêneos” (2015).

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

[48] Rogério Fletcher. “Métodos práticos de otimização (2ª edição)”. John Wiley e Filhos. Nova York, NY, EUA (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[49] MJD Powell. “Um método de otimização de busca direta que modela as funções objetivo e de restrição por interpolação linear”. Avanços em Otimização e Análise Numérica 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Alan J. Laub. “Análise matricial para cientistas e engenheiros”. Volume 91. Sião. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[51] Georg Frobenius. “Ueber matrizen aus nicht negativon elementen”. Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenPáginas 456–477 (1912).

[52] A. Kaveh e H. Rahami. “Um método unificado para autocomposição de produtos gráficos”. Comunicações em Métodos Numéricos em Engenharia com Aplicações Biomédicas 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Spacapan. “Conectividade de produtos cartesianos de grafos”. Cartas de Matemática Aplicada 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] Jacek Gondzio e Andreas Grothey. “Resolvendo problemas de planejamento financeiro não linear com 109 variáveis ​​de decisão em arquiteturas massivamente paralelas”. Transações WIT em Modelagem e Simulação 43 (2006).
https: / / doi.org/ 10.2495 / CF060101

[55] Ventilador RK Chung. “Teoria dos grafos espectrais”. Volume 92. Sociedade Matemática Americana. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen e IL Chuang. “Computação quântica e informação quântica: edição do 10º aniversário”. Cambridge University Press, Nova York. (2011).
https: / / doi.org/ 10.1017 / CBO9780511976667

[57] Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong e Benjamin Nachman. “Extrapolação de ruído zero computacionalmente eficiente para mitigação de erros de porta quântica”. Revisão Física A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala e Kristan Temme. “Cancelamento probabilístico de erros com modelos pauli-lindblad esparsos em processadores quânticos barulhentos”. Física da Natureza, páginas 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick e Frédéric Roupin. “BiqCrunch: Um método branch-and-bound semidefinido para resolver problemas quadráticos binários”. Transações ACM em Software Matemático 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer e Matt McGinnis. “Os menores autovalores de gráficos de Hamming, gráficos de Johnson e outros gráficos de distância regular com parâmetros clássicos”. Journal of Combinatorial Theory, Série B 133, 88–121 (2018).
https: / / doi.org/ 10.1016 / j.jctb.2018.04.005

[61] Donald Knuth. “Matrizes combinatórias”. Artigos selecionados sobre matemática discreta (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citado por

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner e Daniel J. Egger, “Scaling of the quantum Approximation Algoritmo on superconducting qubit based hardware”, Quântico 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun e Marco Pistoia, “Alinhamento entre o estado inicial e o mixer melhora o desempenho do QAOA para otimização de portfólio restrito”, arXiv: 2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad e Ping Koy Lam, “Uma Ansatz Expressiva para Otimização Quântica de Baixa Profundidade”, arXiv: 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo e Anh Pham, “Algoritmo de pesquisa complementar de Grover: uma implementação de supressão de amplitude”, arXiv: 2209.10484, (2022).

[5] 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).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble e Creston D. Herold, “Modelagem de ruído em interações globais Mølmer-Sørensen aplicadas à otimização quântica aproximada”, Revisão Física A 107 6, 062406 (2023).

[7] Guoming Wang, “Algoritmo de otimização quântica com reforço clássico”, arXiv: 2203.13936, (2022).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-09-27 01:31:19). 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 2023-09-27 01:31:17).

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