Caminhadas quânticas em tempo contínuo para MAX-CUT são interessantes

Caminhadas quânticas em tempo contínuo para MAX-CUT são interessantes

Robert J. Bancos1, Ehsan Haque2, Farah Nazef2, Fátima Fethallah2, Fátima Ruqaya2, Hamza Ahsan2, Het Vora2, Hibah Tahir2, Ibrahim Ahmad2, Isaac Hewins2, Ishaq Xá2, Krish Baranwal2, Mannan Arora2, Mateen Asad2, Mubasshirah Khan2, Nabian Hasan2, Nuh Azad2, Salgai Fedaiee2, Shakeel Majeed2, Shayam Bhuyan2, Tasfia Tarannum2, Yahya Ali2, Dan E. Browne3e PA Warburton1,4

1Centro de Londres para Nanotecnologia, UCL, Londres WC1H 0AH, Reino Unido
2Newham Collegiate Sixth Form Centre, 326 Barking Rd, Londres, E6 2BB, Reino Unido
3Departamento de Física e Astronomia, UCL, Londres WC1E 6BT, Reino Unido
4Departamento de Engenharia Eletrônica e Elétrica, UCL, Londres WC1E 7JE, Reino Unido

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

Sumário

Ao explorar a ligação entre hamiltonianos independentes do tempo e a termalização, são feitas previsões heurísticas sobre o desempenho de caminhadas quânticas em tempo contínuo para MAX-CUT. As previsões resultantes dependem do número de triângulos no gráfico MAX-CUT subjacente. Estendemos esses resultados para o cenário dependente do tempo com caminhadas quânticas de vários estágios e sistemas Floquet. A abordagem seguida aqui fornece uma nova maneira de compreender o papel da dinâmica unitária no tratamento de problemas de otimização combinatória com algoritmos quânticos de tempo contínuo.

Problemas de otimização combinatória aparecem em muitos aspectos da vida moderna. Os exemplos incluem encontrar o caminho mais curto, maximizar o lucro e programar entregas de maneira ideal. Esses problemas são normalmente difíceis de resolver. Aqui nos concentramos no problema canônico conhecido como MAX-CUT. Caminhadas quânticas em tempo contínuo apresentam uma nova maneira de lidar com problemas de otimização, explorando efeitos quânticos. Neste artigo discutimos como otimizar caminhadas quânticas em tempo contínuo para MAX-CUT.

Caminhadas quânticas em tempo contínuo contêm um parâmetro livre. Um parâmetro bem otimizado resulta em uma melhor qualidade de solução. Para otimizar o passeio quântico, utilizamos a hipótese bem estabelecida de que sistemas fechados podem termalizar. A temperatura associada acaba sendo alta. Ao modelar efetivamente a densidade de estados para a caminhada quântica, podemos estimar com segurança a escolha ideal do parâmetro livre sem um loop externo variacional (clássico). É importante ressaltar que a escolha ideal estimada do parâmetro livre pode ser vinculada às propriedades do gráfico MAX-CUT subjacente.

Este trabalho apresenta uma abordagem inovadora, combinando física estatística com otimização quântica. Trabalhos futuros podem envolver a extensão dos insights deste artigo para uma gama mais ampla de abordagens quânticas para otimização.

► dados BibTeX

► Referências

[1] Edward Farhi e Sam Gutmann. “Computação quântica e árvores de decisão”. Física. Rev. A 58, 915–928 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.915

[2] Andrew M. Childs. “Computação universal por caminhada quântica”. Física. Rev. 102, 180501 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.180501

[3] Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yogesh N. Joglekar e Peng Xue. “Realização experimental de caminhadas quânticas em tempo contínuo em gráficos direcionados e sua aplicação em pagerank”. Óptica 7, 1524–1530 (2020).
https: / / doi.org/ 10.1364 / OPTICA.396228

[4] Yunkai Wang, Shengjun Wu e Wei Wang. “Pesquisa quântica controlada em bancos de dados estruturados”. Física. Rev. 1, 033016 (2019).
https: / / doi.org/ 10.1103 / PhysRevResearch.1.033016

[5] Yang Wang, Shichuan Xue, Junjie Wu e Ping Xu. “Testes de centralidade baseados em caminhada quântica em tempo contínuo em gráficos ponderados”. Relatórios Científicos 12, 6001 (2022).
https:/​/​doi.org/​10.1038/​s41598-022-09915-1

[6] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann e Daniel A. Spielman. “Aceleração algorítmica exponencial por uma caminhada quântica”. Em ACM (2003).
https: / / doi.org/ 10.1145 / 780542.780552

[7] Josh A. Izaac, Xiang Zhan, Zhihao Bian, Kunkun Wang, Jian Li, Jingbo B. Wang e Peng Xue. “Medida de centralidade baseada em caminhadas quânticas em tempo contínuo e realização experimental”. Física. Rev.A 95, 032318 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032318

[8] T. Loke, JW Tang, J. Rodriguez, M. Small e JB Wang. “Comparando pageranks clássicos e quânticos”. Processamento de Informação Quântica 16, 25 (2016).
https: / / doi.org/ 10.1007 / s11128-016-1456-z

[9] Andrew M. Childs e Jeffrey Goldstone. “Pesquisa espacial por caminhada quântica”. Física Rev. A 70, 022314 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.022314

[10] Adam Callison, Nicholas Chanceler, Florian Mintert e Viv Kendon. “Encontrando estados fundamentais de spin glass usando caminhadas quânticas”. Novo Jornal de Física 21, 123022 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab5ca2

[11] Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chanceler e Viv Kendon. “Comparando a dureza de instâncias de problemas de no máximo 2 satélites para algoritmos quânticos e clássicos”. Física. Rev. 5, 023151 (2023).
https: / / doi.org/ 10.1103 / PhysRevResearch.5.023151

[12] Adam Callison. “Computação quântica em tempo contínuo”. Tese de doutorado. Colégio Imperial de Londres. (2021).
https: / / doi.org/ 10.25560 / 91503

[13] Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon e Nicholas Chancellor. “Perspectiva energética sobre extinção rápida em recozimento quântico”. PRX Quantum 2, 010338 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010338

[14] JM Deutsch. “Mecânica estatística quântica em sistema fechado”. Física. Rev. A 43, 2046–2049 (1991).
https: / / doi.org/ 10.1103 / PhysRevA.43.2046

[15] Marco Srednicki. “Caos e termalização quântica”. Física. Rev. E 50, 888–901 (1994).
https: / / doi.org/ 10.1103 / PhysRevE.50.888

[16] Joshua M Deutsch. “Hipótese de termalização do estado próprio”. Relatórios de Progresso em Física 81, 082001 (2018).
https:/​/​doi.org/​10.1088/​1361-6633/​aac9f1

[17] Marcos Rigol. “Quebra da termalização em sistemas unidimensionais finitos”. Física. Rev. 103, 100403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.100403

[18] Fabian HL Essler e Maurizio Fagotti. “Dinâmica de têmpera e relaxamento em cadeias de spin quânticas integráveis ​​isoladas”. Journal of Statistical Mechanics: Teoria e Experimento 2016, 064002 (2016).
https:/​/​doi.org/​10.1088/​1742-5468/​2016/​06/​064002

[19] Marlon Brenes, Tyler LeBlond, John Goold e Marcos Rigol. “Termalização de estados próprios em um sistema integrável localmente perturbado”. Física. Rev. 125, 070605 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.070605

[20] Jae Dong Noh. “Hipótese de termalização de autoestado e flutuações de autoestado para autoestado”. Física. Rev. E 103, 012129 (2021).
https: / / doi.org/ 10.1103 / PhysRevE.103.012129

[21] David A. Huse, Rahul Nandkishore, Vadim Oganesyan, Arijeet Pal e SL Sondhi. “Ordem quântica protegida por localização”. Física. Rev. B 88, 014206 (2013).
https: / / doi.org/ 10.1103 / PhysRevB.88.014206

[22] Rahul Nandkishore e David A. Huse. “Localização e termalização de muitos corpos em mecânica estatística quântica”. Revisão Anual da Física da Matéria Condensada 6, 15–38 (2015). arXiv:https:/​/​doi.org/​10.1146/​annurev-conmatphys-031214-014726.
https: / / doi.org/ 10.1146 / annurev-conmatphys-031214-014726
arXiv: https://doi.org/10.1146/annurev-conmatphys-031214-014726

[23] Ehud Altman. “Localização de muitos corpos e termalização quântica”. Física da Natureza 14, 979–983 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0305-7

[24] Marcos Rigol, Vanja Dunjko e Maxim Olshanii. “Termalização e seu mecanismo para sistemas quânticos isolados genéricos”. Natureza 452, 854-858 (2008).
https: / / doi.org/ 10.1038 / nature06838

[25] Giulio Biroli, Corinna Kollath e Andreas M. Läuchli. “Efeito de flutuações raras na termalização de sistemas quânticos isolados”. Física. Rev. 105, 250401 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.105.250401

[26] Lea F. Santos e Marcos Rigol. “Início do caos quântico em sistemas bosônicos e fermiônicos unidimensionais e sua relação com a termalização”. Física. Rev. E 81, 036206 (2010).
https: / / doi.org/ 10.1103 / PhysRevE.81.036206

[27] R. Steinigeweg, J. Herbrych e P. Prelovšek. “Termalização de estado próprio em sistemas isolados de cadeia de spin”. Física. Rev. E 87, 012118 (2013).
https: / / doi.org/ 10.1103 / PhysRevE.87.012118

[28] Hyungwon Kim, Tatsuhiko N. Ikeda e David A. Huse. “Testando se todos os estados próprios obedecem à hipótese de termalização dos estados próprios”. Física. Rev. E 90, 052105 (2014).
https: / / doi.org/ 10.1103 / PhysRevE.90.052105

[29] R. Steinigeweg, A. Khodja, H. Niemeyer, C. Gogolin e J. Gemmer. “Empurrando os limites da hipótese de termalização do estado próprio em direção a sistemas quânticos mesoscópicos”. Física. Rev. 112, 130403 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.130403

[30] Keith R. Fratus e Mark Srednicki. “Termalização de estados próprios em sistemas com simetria quebrada espontaneamente”. Física. Rev. E 92, 040103 (2015).
https: / / doi.org/ 10.1103 / PhysRevE.92.040103

[31] Abdellah Khodja, Robin Steinigeweg e Jochen Gemmer. “Relevância da hipótese de termalização do estado próprio para relaxamento térmico”. Física. Rev. E 91, 012120 (2015).
https: / / doi.org/ 10.1103 / PhysRevE.91.012120

[32] Rubem Mondaini e Marcos Rigol. “Termalização de estado próprio no modelo de formação de campo transversal bidimensional. ii. elementos de matriz fora da diagonal de observáveis”. Física. Rev. E 96, 012157 (2017).
https: / / doi.org/ 10.1103 / PhysRevE.96.012157

[33] Toru Yoshizawa, Eiki Iyoda e Takahiro Sagawa. “Análise numérica de grandes desvios da hipótese de termalização do estado próprio”. Física. Rev. 120, 200604 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.120.200604

[34] David Jansen, Jan Stolpp, Lev Vidmar e Fabian Heidrich-Meisner. “Termalização de estado próprio e caos quântico no modelo holstein polaron”. Física. Rev. B 99, 155130 (2019).
https: / / doi.org/ 10.1103 / PhysRevB.99.155130

[35] S. Trotzky, YA. Chen, A. Flesch, IP McCulloch, U. Schollwöck, J. Eisert e I. Bloch. “Sondando o relaxamento em direção ao equilíbrio em um gás bose unidimensional fortemente correlacionado isolado”. Física da Natureza 8, 325–330 (2012).
https: / / doi.org/ 10.1038 / nphys2232

[36] Govinda Clos, Diego Porras, Ulrich Warring e Tobias Schaetz. “Observação da termalização resolvida no tempo em um sistema quântico isolado”. Física. Rev. 117, 170401 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.170401

[37] Adam M. Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss e Markus Greiner. “Termalização quântica através do emaranhamento em um sistema isolado de muitos corpos”. Ciência 353, 794–800 (2016).
https: / / doi.org/ 10.1126 / science.aaf6725

[38] G. Kucsko, S. Choi, J. Choi, PC Maurer, H. Zhou, R. Landig, H. Sumiya, S. Onoda, J. Isoya, F. Jelezko, E. Demler, NY Yao e MD Lukin. “Termalização crítica de um sistema de spin dipolar desordenado em diamante”. Física. Rev. 121, 023601 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.023601

[39] Yijun Tang, Wil Kao, Kuan-Yu Li, Sangwon Seo, Krishnanand Mallayya, Marcos Rigol, Sarang Gopalakrishnan e Benjamin L. Lev. “Termalização próxima à integrabilidade em berço de newton quântico dipolar”. Física. Rev. X 8, 021030 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021030

[40] JR Johansson, PD Nation e Franco Nori. “Qutip: Uma estrutura python de código aberto para a dinâmica de sistemas quânticos abertos”. Comunicações de Física da Computação 183, 1760–1772 (2012).
https: / / doi.org/ 10.1016 / j.cpc.2012.02.021

[41] JR Johansson, PD Nação e Franco Nori. “Qutip 2: Uma estrutura python para a dinâmica de sistemas quânticos abertos”. Comunicações de Física da Computação 184, 1234–1240 (2013).
https: / / doi.org/ 10.1016 / j.cpc.2012.11.019

[42] Aric A. Hagberg, Daniel A. Schult e Pieter J. Swart. “Explorando estrutura, dinâmica e função de rede usando networkx”. Em Gaël Varoquaux, Travis Vaught e Jarrod Millman, editores, Proceedings of the 7th Python in Science Conference. Páginas 11 – 15. Pasadena, CA EUA (2008). url: https://conference.scipy.org/​proceedings/​SciPy2008/​paper_2/​.
https://conference.scipy.org/​proceedings/​SciPy2008/​paper_2/​

[43] Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan e Xiangjie Kong. “Caminhadas aleatórias: uma revisão de algoritmos e aplicações”. Transações IEEE sobre Tópicos Emergentes em Inteligência Computacional 4, 95–107 (2020).
https://​/​doi.org/​10.1109/​tetci.2019.2952908

[44] Henrik Wilming, Thiago R. de Oliveira, Anthony J. Short e Jens Eisert. “Tempos de equilíbrio em sistemas quânticos fechados de muitos corpos”. Página 435–455. Publicação Internacional Springer. (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_18

[45] James R. Garrison e Tarun Grover. “Será que um único estado próprio codifica o hamiltoniano completo?”. Revisão Física X 8 (2018).
https: / / doi.org/ 10.1103 / physrevx.8.021026

[46] Pedro Reimann. “Termalização Eigenstate: a abordagem de Deutsch e além”. Novo Jornal de Física 17, 055025 (2015).
https:/​/​doi.org/​10.1088/​1367-2630/​17/​5/​055025

[47] Tameem Albash e Daniel A. Lidar. “Computação quântica adiabática”. Resenhas de Física Moderna 90 (2018).
https: / / doi.org/ 10.1103 / revmodphys.90.015002

[48] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori e William D Oliver. "Perspectivas de recozimento quântico: métodos e implementações". Reports on Progress in Physics 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[49] 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”. Física Rev. X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[50] Laba e Tkachuk. “Características geométricas da evolução quântica: curvatura e torção”. Física da Matéria Condensada 20, 13003 (2017).
https://​/​doi.org/​10.5488/​cmp.20.13003

[51] Kh.P. Gnatenko, HP Laba e VM Tkachuk. “Propriedades geométricas de estados de gráficos evolutivos e sua detecção em um computador quântico”. Cartas de Física A 452, 128434 (2022).
https: / / doi.org/ 10.1016 / j.physleta.2022.128434

[52] Luca D'Alessio, Yariv Kafri, Anatoli Polkovnikov e Marcos Rigol. “Do caos quântico e termalização de autoestados à mecânica estatística e termodinâmica”. Avanços em Física 65, 239–362 (2016).
https: / / doi.org/ 10.1080 / 00018732.2016.1198134

[53] Edward Farhi, David Gosset, Itay Hen, AW Sandvik, Peter Shor, AP Young e Francesco Zamponi. “Desempenho do algoritmo quântico adiabático em instâncias aleatórias de dois problemas de otimização em hipergrafos regulares”. Revisão Física A 86 (2012).
https: / / doi.org/ 10.1103 / physreva.86.052334

[54] Mark Jeansonne e Joe Foley. “Revisão da função gaussiana (emg) exponencialmente modificada desde 1983”. Journal of Chromatographic Science 29, 258–266 (1991).
https://​/​doi.org/​10.1093/​chromsci/​29.6.258

[55] Yuri Kalambet, Yuri Kozmin, Ksenia Mikhailova, Igor Nagaev e Pavel Tikhonov. “Reconstrução de picos cromatográficos utilizando a função gaussiana exponencialmente modificada”. Journal of Chemometrics 25, 352–356 (2011).
https://​/​doi.org/​10.1002/​cem.1343

[56] Stephen J. Blundell e Katherine M. Blundell. “Conceitos de Física Térmica”. Imprensa da Universidade de Oxford. (2009).
https: / / doi.org/ 10.1093 / acprof: oso / 9780199562091.001.0001

[57] Elizabeth Crosson e Samuel Slezak. “Simulação clássica de modelos quânticos de alta temperatura” (2020). arXiv:2002.02232.
arXiv: 2002.02232

[58] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore e Matthew J. Reagor. “Perspectiva de emaranhamento no algoritmo de otimização quântica aproximada”. Revisão Física A 106 (2022).
https: / / doi.org/ 10.1103 / physreva.106.022423

[59] JM Deutsch. “Entropia termodinâmica de um estado próprio de energia de muitos corpos”. Novo Jornal de Física 12, 075021 (2010).
https:/​/​doi.org/​10.1088/​1367-2630/​12/​7/​075021

[60] JM Deutsch, Haibin Li e Auditya Sharma. “Origem microscópica da entropia termodinâmica em sistemas isolados”. Física. Rev. E 87, 042135 (2013).
https: / / doi.org/ 10.1103 / PhysRevE.87.042135

[61] Lea F. Santos, Anatoli Polkovnikov e Marcos Rigol. “Entropia de sistemas quânticos isolados após um resfriamento”. Física. Rev. 107, 040601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.040601

[62] Michael A. Nielsen e Isaac L. Chuang. “Computação quântica e informação quântica: edição do 10º aniversário”. Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

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

[64] Milena Grifoni e Peter Hänggi. “Tunelamento quântico conduzido”. Relatórios de Física 304, 229–354 (1998).
https:/​/​doi.org/​10.1016/​S0370-1573(98)00022-2

[65] Masahito Ueda. “Equilíbrio quântico, termalização e pré-termalização em átomos ultrafrios”. Nature Reviews Physics 2, 669–681 (2020).
https: / / doi.org/ 10.1038 / s42254-020-0237-x

[66] Luca D'Alessio e Anatoli Polkovnikov. “Transição de localização de energia de muitos corpos em sistemas acionados periodicamente”. Anais de Física 333, 19–33 (2013).
https: / / doi.org/ 10.1016 / j.aop.2013.02.011

[67] Luca D’Alessio e Marcos Rigol. “Comportamento de longo prazo de sistemas reticulados interativos isolados e acionados periodicamente”. Revisão Física X 4 (2014).
https: / / doi.org/ 10.1103 / physrevx.4.041048

[68] Achilleas Lazarides, Arnab Das e Roderich Moessner. “Estados de equilíbrio de sistemas quânticos genéricos sujeitos a condução periódica”. Física. Rev. E 90, 012110 (2014).
https: / / doi.org/ 10.1103 / PhysRevE.90.012110

[69] Keith R. Fratus e Mark Allen Srednicki. “Termalização de estados próprios e quebra espontânea de simetria no modelo de campo transversal unidimensional com interações de lei de potência” (2016). arXiv:1611.03992.
arXiv: 1611.03992

[70] Attila Felinger, Tamás Pap e János Inczédy. “Ajuste de curva a cromatogramas assimétricos pelo filtro de Kalman estendido no domínio da frequência”. Talanta 41, 1119–1126 (1994).
https:/​/​doi.org/​10.1016/​0039-9140(94)80081-2

[71] KF Riley, MP Hobson e SJ Bence. “Métodos matemáticos para física e engenharia: um guia completo”. Cambridge University Press. (2006). 3 edição.
https: / / doi.org/ 10.1017 / CBO9780511810763

[72] Brian C. Salão. “Uma introdução elementar a grupos e representações” (2000). arXiv: matemática-ph/​0005032.
arXiv: math-ph / 0005032

[73] Michael M. Wolf, Frank Verstraete, Matthew B. Hastings e J. Ignacio Cirac. “Leis de área em sistemas quânticos: informações mútuas e correlações”. Física. Rev. 100, 070502 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.100.070502

[74] Martin Kliesch e Arnau Riera. “Propriedades dos estados quânticos térmicos: localidade da temperatura, decaimento de correlações e muito mais”. Em Teorias Fundamentais da Física. Páginas 481–502. Publicação Internacional Springer (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_20

[75] SH Simão. “Os fundamentos do estado sólido de Oxford”. OUP Oxford. (2013).

Citado por

[1] R. Au-Yeung, B. Camino, O. Rathore e V. Kendon, “Algoritmos quânticos para aplicações científicas”, arXiv: 2312.14904, (2023).

[2] Sebastian Schulz, Dennis Willsch e Kristel Michielsen, “Caminhada quântica guiada”, arXiv: 2308.05418, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2024-02-14 02:07:09). 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-02-14 02:07:08).

Carimbo de hora:

Mais de Diário Quântico