Les marches quantiques en temps continu pour MAX-CUT sont en vogue

Les marches quantiques en temps continu pour MAX-CUT sont en vogue

Robert J.Banks1, Ehsan Haque2, Farah Nazef2, Fatima Fethallah2, Fatima Ruqaya2, Hamza Ahsan2, La Vora2, Hibah Tahir2, Ibrahim Ahmad2, Isaac Hewins2, Ishaq Shah2, Krish Baranwal2, Mannan Arora2, Mateen Asad2, Mubasshirah Khan2, Nabian Hasan2, Nuh Azad2, Salgai Fedaiee2, Shakeel Majeed2, Shayam Bhuyan2, Tasfia Tarannum2, Yahya Ali2, Dan E. Browne3et PA Warburton1,4

1Centre de Londres pour la nanotechnologie, UCL, Londres WC1H 0AH, Royaume-Uni
2Newham Collegiate Sixth Form Centre, 326 Barking Rd, Londres, E6 2BB, Royaume-Uni
3Département de physique et d'astronomie, UCL, Londres WC1E 6BT, Royaume-Uni
4Département de génie électronique et électrique, UCL, Londres WC1E 7JE, Royaume-Uni

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

En exploitant le lien entre les hamiltoniens indépendants du temps et la thermalisation, des prédictions heuristiques sur les performances des marches quantiques en temps continu pour MAX-CUT sont réalisées. Les prédictions résultantes dépendent du nombre de triangles dans le graphique MAX-CUT sous-jacent. Nous étendons ces résultats au contexte dépendant du temps avec des marches quantiques à plusieurs étapes et des systèmes Floquet. L'approche suivie ici offre une nouvelle façon de comprendre le rôle de la dynamique unitaire dans la résolution des problèmes d'optimisation combinatoire avec des algorithmes quantiques en temps continu.

Les problèmes d’optimisation combinatoire sont présents dans de nombreux aspects de la vie moderne. Les exemples incluent la recherche du chemin le plus court, la maximisation des profits et la planification optimale des livraisons. Ces problèmes sont généralement difficiles à résoudre. Nous nous concentrons ici sur le problème canonique connu sous le nom de MAX-CUT. Les marches quantiques en temps continu présentent une nouvelle manière de résoudre les problèmes d'optimisation en exploitant les effets quantiques. Dans cet article, nous discutons de la manière d'optimiser les marches quantiques en temps continu pour MAX-CUT.

Les marches quantiques en temps continu contiennent un paramètre libre. Un paramètre bien optimisé se traduit par une meilleure qualité de solution. Afin d’optimiser la marche quantique, nous utilisons l’hypothèse bien établie selon laquelle les systèmes fermés peuvent se thermaliser. La température associée s'avère élevée. En modélisant efficacement la densité d'états pour la marche quantique, nous pouvons estimer de manière fiable le choix optimal du paramètre libre sans boucle externe variationnelle (classique). Il est important de noter que le choix optimal estimé du paramètre libre peut être lié aux propriétés du graphique MAX-CUT sous-jacent.

Ce travail présente une nouvelle approche, combinant physique statistique et optimisation quantique. Les travaux futurs pourraient impliquer d’étendre les connaissances contenues dans cet article à un éventail plus large d’approches quantiques de l’optimisation.

► Données BibTeX

► Références

Edward Farhi et Sam Gutmann. « Calcul quantique et arbres de décision ». Phys. Rév.A 58, 915-928 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.915

Andrew M. Childs. « Calcul universel par marche quantique ». Phys. Le révérend Lett. 102, 180501 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.180501

Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yogesh N. Joglekar et Peng Xue. « Réalisation expérimentale de marches quantiques en temps continu sur graphes orientés et leur application en pagerank ». Optique 7, 1524-1530 (2020).
https: / / doi.org/ 10.1364 / OPTICA.396228

Yunkai Wang, Shengjun Wu et Wei Wang. « Recherche quantique contrôlée sur des bases de données structurées ». Phys. Rév. Rés. 1, 033016 (2019).
https: / / doi.org/ 10.1103 / PhysRevResearch.1.033016

Yang Wang, Shichuan Xue, Junjie Wu et Ping Xu. "Tests de centralité basés sur la marche quantique en temps continu sur des graphiques pondérés". Rapports scientifiques 12, 6001 (2022).
https:/​/​doi.org/​10.1038/​s41598-022-09915-1

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann et Daniel A. Spielman. "Accélération algorithmique exponentielle par une marche quantique". Dans ACM (2003).
https: / / doi.org/ 10.1145 / 780542.780552

Josh A. Izaac, Xiang Zhan, Zhihao Bian, Kunkun Wang, Jian Li, Jingbo B. Wang et Peng Xue. « Mesure de centralité basée sur des marches quantiques en temps continu et une réalisation expérimentale ». Phys. Rév.A 95, 032318 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.032318

T. Loke, JW Tang, J. Rodriguez, M. Small et JB Wang. « Comparaison des pageranks classiques et quantiques ». Traitement de l'information quantique 16, 25 (2016).
https: / / doi.org/ 10.1007 / s11128-016-1456-z

Andrew M. Childs et Jeffrey Goldstone. "Recherche spatiale par marche quantique". Phys. Rev. A 70, 022314 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.022314

Adam Callison, Nicholas Chancelier, Florian Mintert et Viv Kendon. "Trouver les états fondamentaux du verre de spin à l'aide de marches quantiques". Nouveau Journal de Physique 21, 123022 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab5ca2

Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chancellor et Viv Kendon. "Comparaison de la dureté des instances de problèmes maximum de 2 sat pour les algorithmes quantiques et classiques". Phys. Rév. Rés. 5, 023151 (2023).
https: / / doi.org/ 10.1103 / PhysRevResearch.5.023151

Adam Callison. « Informatique quantique en temps continu ». Thèse de doctorat. Collège impérial de Londres. (2021).
https: / / doi.org/ 10.25560 / 91503

Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon et Nicholas Chancellor. "Perspective énergétique des trempes rapides dans le recuit quantique". PRX Quantique 2, 010338 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010338

JM Deutsch. « Mécanique statistique quantique en système fermé ». Phys. Rév. A 43, 2046–2049 (1991).
https: / / doi.org/ 10.1103 / PhysRevA.43.2046

Mark Srednicki. "Chaos et thermalisation quantique". Phys. Rev. E 50, 888–901 (1994).
https: / / doi.org/ 10.1103 / PhysRevE.50.888

Joshua M Deutsch. "Hypothèse de thermalisation de l'état propre". Rapports sur les progrès en physique 81, 082001 (2018).
https:/​/​doi.org/​10.1088/​1361-6633/​aac9f1

Marcos Rigol. « Décomposition de la thermalisation dans les systèmes finis unidimensionnels ». Phys. Le révérend Lett. 103, 100403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.100403

Fabian HL Essler et Maurizio Fagotti. "Extinction de la dynamique et de la relaxation dans les chaînes de spin quantiques intégrables isolées". Journal de mécanique statistique : théorie et expérience 2016, 064002 (2016).
https:/​/​doi.org/​10.1088/​1742-5468/​2016/​06/​064002

Marlon Brenes, Tyler LeBlond, John Goold et Marcos Rigol. « Thermalisation des états propres dans un système intégrable localement perturbé ». Phys. Le révérend Lett. 125, 070605 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.070605

Jae Dong Noh. "Hypothèse de thermalisation des états propres et fluctuations d'un état propre à l'autre". Phys. Rév.E 103, 012129 (2021).
https: / / doi.org/ 10.1103 / PhysRevE.103.012129

David A. Huse, Rahul Nandkishore, Vadim Oganesyan, Arijeet Pal et SL Sondhi. « Ordre quantique protégé par localisation ». Phys. Rév.B 88, 014206 (2013).
https: / / doi.org/ 10.1103 / PhysRevB.88.014206

Rahul Nandkishore et David A. Huse. "Localisation et thermalisation à N corps en mécanique statistique quantique". Revue annuelle de la physique de la matière condensée 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

Ehud Altman. « Localisation à N corps et thermalisation quantique ». Physique de la nature 14, 979-983 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0305-7

Marcos Rigol, Vanja Dunjko et Maxim Olshanii. "La thermalisation et son mécanisme pour les systèmes quantiques génériques isolés". Nature 452, 854–858 (2008).
https: / / doi.org/ 10.1038 / nature06838

Giulio Biroli, Corinna Kollath et Andreas M. Läuchli. « Effet de rares fluctuations sur la thermalisation de systèmes quantiques isolés ». Phys. Le révérend Lett. 105, 250401 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.105.250401

Léa F. Santos et Marcos Rigol. "Début du chaos quantique dans les systèmes bosoniques et fermioniques unidimensionnels et sa relation avec la thermalisation". Phys. Rév.E 81, 036206 (2010).
https: / / doi.org/ 10.1103 / PhysRevE.81.036206

R. Steinigeweg, J. Herbrych et P. Prelovšek. « Thermalisation des états propres dans les systèmes de chaînes de spin isolés ». Phys. Rév.E 87, 012118 (2013).
https: / / doi.org/ 10.1103 / PhysRevE.87.012118

Hyungwon Kim, Tatsuhiko N. Ikeda et David A. Huse. "Tester si tous les états propres obéissent à l'hypothèse de thermalisation des états propres". Phys. Rév.E 90, 052105 (2014).
https: / / doi.org/ 10.1103 / PhysRevE.90.052105

R. Steinigeweg, A. Khodja, H. Niemeyer, C. Gogolin et J. Gemmer. "Repousser les limites de l'hypothèse de thermalisation des états propres vers les systèmes quantiques mésoscopiques". Phys. Le révérend Lett. 112, 130403 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.130403

Keith R. Fratus et Mark Srednicki. « Thermalisation des états propres dans les systèmes à symétrie spontanément brisée ». Phys. Rév.E 92, 040103 (2015).
https: / / doi.org/ 10.1103 / PhysRevE.92.040103

Abdellah Khodja, Robin Steinigeweg et Jochen Gemmer. "Pertinence de l'hypothèse de thermalisation des états propres pour la relaxation thermique". Phys. Rév.E 91, 012120 (2015).
https: / / doi.org/ 10.1103 / PhysRevE.91.012120

Rubem Mondaini et Marcos Rigol. « Thermalisation des états propres dans le modèle de champ transversal bidimensionnel. ii. éléments matriciels hors diagonale des observables ». Phys. Rév.E 96, 012157 (2017).
https: / / doi.org/ 10.1103 / PhysRevE.96.012157

Toru Yoshizawa, Eiki Iyoda et Takahiro Sagawa. "Analyse numérique des grandes déviations de l'hypothèse de thermalisation des états propres". Phys. Le révérend Lett. 120, 200604 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.120.200604

David Jansen, Jan Stolpp, Lev Vidmar et Fabian Heidrich-Meisner. « Thermalisation des états propres et chaos quantique dans le modèle du polaron de Holstein ». Phys. Rév.B 99, 155130 (2019).
https: / / doi.org/ 10.1103 / PhysRevB.99.155130

S. Trotzky, YA. Chen, A. Flesch, IP McCulloch, U. Schollwöck, J. Eisert et I. Bloch. "Sonder la relaxation vers l'équilibre dans un gaz Bose unidimensionnel isolé fortement corrélé". Physique de la nature 8, 325-330 (2012).
https: / / doi.org/ 10.1038 / nphys2232

Govinda Clos, Diego Porras, Ulrich Warring et Tobias Schaetz. "Observation résolue en temps de la thermalisation dans un système quantique isolé". Phys. Le révérend Lett. 117, 170401 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.170401

Adam M. Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss et Markus Greiner. "Thermalisation quantique par intrication dans un système isolé à plusieurs corps". Sciences 353, 794–800 (2016).
https: / / doi.org/ 10.1126 / science.aaf6725

G. Kucsko, S. Choi, J. Choi, PC Maurer, H. Zhou, R. Landig, H. Sumiya, S. Onoda, J. Isoya, F. Jelezko, E. Demler, NY Yao et MD Lukin. « Thermalisation critique d'un système de spin dipolaire désordonné dans le diamant ». Phys. Le révérend Lett. 121, 023601 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.023601

Yijun Tang, Wil Kao, Kuan-Yu Li, Sangwon Seo, Krishnanand Mallayya, Marcos Rigol, Sarang Gopalakrishnan et Benjamin L. Lev. « Thermalisation proche de l'intégrabilité dans un berceau de Newton quantique dipolaire ». Phys. Rév.X 8, 021030 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021030

JR Johansson, PD Nation et Franco Nori. « Qutip : Un framework Python open source pour la dynamique des systèmes quantiques ouverts ». Communications de physique informatique 183, 1760-1772 (2012).
https: / / doi.org/ 10.1016 / j.cpc.2012.02.021

JR Johansson, PD Nation et Franco Nori. "Qutip 2: Un cadre python pour la dynamique des systèmes quantiques ouverts". Communications de physique informatique 184, 1234–1240 (2013).
https: / / doi.org/ 10.1016 / j.cpc.2012.11.019

Aric A. Hagberg, Daniel A. Schult et Pieter J. Swart. "Explorer la structure, la dynamique et la fonction du réseau à l'aide de networkx". Dans Gaël Varoquaux, Travis Vaught et Jarrod Millman, éditeurs, Actes de la 7e conférence Python in Science. Pages 11 à 15. Pasadena, Californie, États-Unis (2008). URL : https://​/​conference.scipy.org/​proceedings/​SciPy2008/​paper_2/​.
https://​/​conference.scipy.org/​proceedings/​SciPy2008/​paper_2/​

Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan et Xiangjie Kong. "Marches aléatoires : une revue des algorithmes et des applications". Transactions IEEE sur des sujets émergents en intelligence informatique 4, 95-107 (2020).
https://​/​doi.org/​10.1109/​tetci.2019.2952908

Henrik Wilming, Thiago R. de Oliveira, Anthony J. Short et Jens Eisert. « Temps d'équilibre dans les systèmes quantiques fermés à N corps ». Pages 435 à 455. Éditions internationales Springer. (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_18

James R. Garrison et Tarun Grover. "Est-ce qu'un seul état propre code pour le hamiltonien complet ?". Examen physique X 8 (2018).
https: / / doi.org/ 10.1103 / physrevx.8.021026

Pierre Reimann. « Thermalisation des états propres : l'approche de Deutsch et au-delà ». Nouveau Journal de Physique 17, 055025 (2015).
https:/​/​doi.org/​10.1088/​1367-2630/​17/​5/​055025

Tameem Albash et Daniel A. Lidar. "Calcul quantique adiabatique". Examens de Physique moderne 90 (2018).
https: / / doi.org/ 10.1103 / revmodphys.90.015002

Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori et William D Oliver. « Perspectives du recuit quantique : méthodes et implémentations ». Rapports sur les progrès en physique 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler et Mikhail D. Lukin. "Algorithme d'optimisation approximative quantique : performances, mécanisme et mise en œuvre sur des appareils à court terme". Phys. Rév. X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

Laba et Tkachuk. « Caractéristiques géométriques de l'évolution quantique : courbure et torsion ». Physique de la matière condensée 20, 13003 (2017).
https://​/​doi.org/​10.5488/​cmp.20.13003

Kh.P. Gnatenko, HP Laba et VM Tkachuk. "Propriétés géométriques des états des graphes évolutifs et leur détection sur un ordinateur quantique". Lettres de physique A 452, 128434 (2022).
https: / / doi.org/ 10.1016 / j.physleta.2022.128434

Luca D'Alessio, Yariv Kafri, Anatoli Polkovnikov et Marcos Rigol. « Du chaos quantique et de la thermalisation des états propres à la mécanique statistique et à la thermodynamique ». Advances in Physics 65, 239–362 (2016).
https: / / doi.org/ 10.1080 / 00018732.2016.1198134

Edward Farhi, David Gosset, Itay Hen, AW Sandvik, Peter Shor, AP Young et Francesco Zamponi. "Performance de l'algorithme adiabatique quantique sur des instances aléatoires de deux problèmes d'optimisation sur des hypergraphes réguliers". Examen physique A 86 (2012).
https: / / doi.org/ 10.1103 / physreva.86.052334

Mark Jeansonne et Joe Foley. "Revue de la fonction gaussienne (emg) modifiée exponentiellement depuis 1983". Journal of Chromatographic Science 29, 258-266 (1991).
https://​/​doi.org/​10.1093/​chromsci/​29.6.258

Youri Kalambet, Youri Kozmin, Ksenia Mikhailova, Igor Nagaev et Pavel Tikhonov. "Reconstruction des pics chromatographiques en utilisant la fonction gaussienne modifiée exponentiellement". Journal de chimiométrie 25, 352-356 (2011).
https://​/​doi.org/​10.1002/​cem.1343

Stephen J. Blundell et Katherine M. Blundell. « Concepts en physique thermique ». Presse de l'Université d'Oxford. (2009).
https: / / doi.org/ 10.1093 / acprof: oso / 9780199562091.001.0001

Elizabeth Crosson et Samuel Slezak. « Simulation classique de modèles quantiques à haute température » ​​(2020). arXiv : 2002.02232.
arXiv: 2002.02232

Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore et Matthew J. Reagor. « Perspective de l'intrication sur l'algorithme d'optimisation approchée quantique ». Examen physique A 106 (2022).
https: / / doi.org/ 10.1103 / physreva.106.022423

JM Deutsch. "Entropie thermodynamique d'un état propre d'énergie à N corps". Nouveau Journal de Physique 12, 075021 (2010).
https:/​/​doi.org/​10.1088/​1367-2630/​12/​7/​075021

JM Deutsch, Haibin Li et Auditya Sharma. "Origine microscopique de l'entropie thermodynamique dans les systèmes isolés". Phys. Rév.E 87, 042135 (2013).
https: / / doi.org/ 10.1103 / PhysRevE.87.042135

Lea F. Santos, Anatoli Polkovnikov et Marcos Rigol. "Entropie des systèmes quantiques isolés après une trempe". Phys. Le révérend Lett. 107, 040601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.040601

Michael A. Nielsen et Isaac L. Chuang. "Calcul quantique et information quantique: édition du 10e anniversaire". La presse de l'Universite de Cambridge. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

Edward Farhi, Jeffrey Goldstone et Sam Gutmann. "Un algorithme d'optimisation approchée quantique" (2014). arXiv:1411.4028.
arXiv: 1411.4028

Milena Grifoni et Peter Hänggi. « Tunneling quantique piloté ». Rapports de physique 304, 229-354 (1998).
https:/​/​doi.org/​10.1016/​S0370-1573(98)00022-2

Masahito Ueda. «Équilibration quantique, thermalisation et préthermalisation dans les atomes ultrafroids». Nature Reviews Physique 2, 669-681 (2020).
https: / / doi.org/ 10.1038 / s42254-020-0237-x

Luca D'Alessio et Anatoli Polkovnikov. "Transition de localisation d'énergie à N corps dans des systèmes pilotés périodiquement". Annales de physique 333, 19-33 (2013).
https: / / doi.org/ 10.1016 / j.aop.2013.02.011

Luca D'Alessio et Marcos Rigol. "Comportement à long terme de systèmes de réseaux en interaction isolés et périodiquement entraînés". Examen physique X 4 (2014).
https: / / doi.org/ 10.1103 / physrevx.4.041048

Achilleas Lazarides, Arnab Das et Roderich Moessner. "États d'équilibre des systèmes quantiques génériques soumis à une conduite périodique". Phys. Rév.E 90, 012110 (2014).
https: / / doi.org/ 10.1103 / PhysRevE.90.012110

Keith R. Fratus et Mark Allen Srednicki. « Thermalisation des états propres et rupture spontanée de symétrie dans le modèle de champ transversal unidimensionnel avec interactions de loi de puissance » (2016). arXiv : 1611.03992.
arXiv: 1611.03992

Attila Felinger, Tamás Pap et János Inczédy. "Ajustement de courbe aux chromatogrammes asymétriques par le filtre de Kalman étendu dans le domaine fréquentiel". Talante 41, 1119-1126 (1994).
https:/​/​doi.org/​10.1016/​0039-9140(94)80081-2

KF Riley, député Hobson et SJ Bence. « Méthodes mathématiques pour la physique et l'ingénierie : un guide complet ». La presse de l'Universite de Cambridge. (2006). 3 édition.
https: / / doi.org/ 10.1017 / CBO9780511810763

Brian C. Hall. « Une introduction élémentaire aux groupes et aux représentations » (2000). arXiv:math-ph/​0005032.
arXiv: math-ph / 0005032

Michael M. Wolf, Frank Verstraete, Matthew B. Hastings et J. Ignacio Cirac. "Lois des aires dans les systèmes quantiques : informations mutuelles et corrélations". Phys. Le révérend Lett. 100, 070502 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.100.070502

Martin Kliesch et Arnau Riera. « Propriétés des états quantiques thermiques : localité de la température, dégradation des corrélations, et plus encore ». Dans Théories fondamentales de la physique. Pages 481 à 502. Éditions Springer International (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_20

SH Simon. "Les bases du solide d'Oxford". OUP Oxford. (2013).

Cité par

[1] R. Au-Yeung, B. Camino, O. Rathore et V. Kendon, « Algorithmes quantiques pour applications scientifiques », arXiv: 2312.14904, (2023).

[2] Sebastian Schulz, Dennis Willsch et Kristel Michielsen, « Marche quantique guidée », arXiv: 2308.05418, (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2024-02-14 02:07:09). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2024-02-14 02:07:08).

Horodatage:

Plus de Journal quantique