Kontinuerlige kvantevandringer for MAX-CUT er varme

Kontinuerlige kvantevandringer for MAX-CUT er varme

Robert J. Banks1, Ehsan Haque2, Farah Nazef2, Fatima Fethallah2, Fatima Ruqaya2, Hamza Ahsan2, Het 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. Browne3og PA Warburton1,4

1London Centre for Nanotechnology, UCL, London WC1H 0AH, UK
2Newham Collegiate Sixth Form Centre, 326 Barking Rd, London, E6 2BB, UK
3Institut for Fysik og Astronomi, UCL, London WC1E 6BT, UK
4Department of Electronic & Electrical Engineering, UCL, London WC1E 7JE, UK

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Ved at udnytte forbindelsen mellem tidsuafhængige Hamiltonianere og termalisering laves heuristiske forudsigelser om ydeevnen af ​​kontinuerte kvantevandringer for MAX-CUT. De resulterende forudsigelser afhænger af antallet af trekanter i den underliggende MAX-CUT-graf. Vi udvider disse resultater til den tidsafhængige indstilling med flertrins kvantevandring og Floquet-systemer. Den tilgang, der følges her, giver en ny måde at forstå rollen af ​​enhedsdynamik i at tackle kombinatoriske optimeringsproblemer med kontinuerlige-tids kvantealgoritmer.

Kombinatoriske optimeringsproblemer optræder i mange aspekter af det moderne liv. Eksempler inkluderer at finde den korteste vej, maksimere profit og optimal planlægning af leverancer. Disse problemer er typisk svære at løse. Her fokuserer vi på det kanoniske problem kendt som MAX-CUT. Kontinuerlige kvantevandringer præsenterer en ny måde at tackle optimeringsproblemer ved at udnytte kvanteeffekter. I dette papir diskuterer vi, hvordan man optimerer kontinuerlige kvantevandringer til MAX-CUT.

Kontinuerlige kvantevandringer indeholder en gratis parameter. Et veloptimeret parameter resulterer i en bedre løsningskvalitet. For at optimere kvantevandringen udnytter vi den veletablerede hypotese om, at lukkede systemer kan termalisere. Den tilhørende temperatur viser sig at være høj. Ved effektivt at modellere tætheden af ​​tilstande for kvantevandringen kan vi pålideligt estimere det optimale valg af fri parameter uden en (klassisk) variationsmæssig ydre sløjfe. Det er vigtigt, at det estimerede optimale valg af den frie parameter kan knyttes til egenskaberne for den underliggende MAX-CUT-graf.

Dette arbejde præsenterer en ny tilgang, der kombinerer statistisk fysik med kvanteoptimering. Fremtidigt arbejde kan involvere at udvide indsigterne i dette papir til en bredere række af kvantetilgange til optimering.

► BibTeX-data

► Referencer

[1] Edward Farhi og Sam Gutmann. "Kvanteberegning og beslutningstræer". Phys. Rev. A 58, 915-928 (1998).
https://​/​doi.org/​10.1103/​PhysRevA.58.915

[2] Andrew M. Childs. "Universal beregning ved kvantegang". Phys. Rev. Lett. 102, 180501 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.102.180501

[3] Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yogesh N. Joglekar og Peng Xue. "Eksperimentel realisering af kontinuerlige kvantevandringer på rettede grafer og deres anvendelse i pagerank". Optica 7, 1524-1530 (2020).
https://​/​doi.org/​10.1364/​OPTICA.396228

[4] Yunkai Wang, Shengjun Wu og Wei Wang. "Kontrolleret kvantesøgning på strukturerede databaser". Phys. Rev. Res. 1, 033016 (2019).
https://​/​doi.org/​10.1103/​PhysRevResearch.1.033016

[5] Yang Wang, Shichuan Xue, Junjie Wu og Ping Xu. "Kontinuerlig-tids kvantevandring baseret centralitetstest på vægtede grafer". Scientific Reports 12, 6001 (2022).
https:/​/​doi.org/​10.1038/​s41598-022-09915-1

[6] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann og Daniel A. Spielman. "Eksponentiel algoritmisk fremskyndelse ved en kvantevandring". I ACM (2003).
https://​/​doi.org/​10.1145/​780542.780552

[7] Josh A. Izaac, Xiang Zhan, Zhihao Bian, Kunkun Wang, Jian Li, Jingbo B. Wang og Peng Xue. "Centralitetsmål baseret på kontinuerlige kvantevandringer og eksperimentel realisering". Phys. Rev. A 95, 032318 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.95.032318

[8] T. Loke, JW Tang, J. Rodriguez, M. Small og JB Wang. "Sammenligning af klassiske og kvante pageranks". Quantum Information Processing 16, 25 (2016).
https://​/​doi.org/​10.1007/​s11128-016-1456-z

[9] Andrew M. Childs og Jeffrey Goldstone. "Rumlig søgning ved kvantevandring". Phys. Rev. A 70, 022314 (2004).
https://​/​doi.org/​10.1103/​PhysRevA.70.022314

[10] Adam Callison, Nicholas Chancellor, Florian Mintert og Viv Kendon. "Find af spinglasjordtilstande ved hjælp af kvantevandringer". New Journal of Physics 21, 123022 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab5ca2

[11] Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chancellor og Viv Kendon. "Sammenligning af hårdheden af ​​maks. 2-sat probleminstanser for kvante- og klassiske algoritmer". Phys. Rev. Res. 5, 023151 (2023).
https://​/​doi.org/​10.1103/​PhysRevResearch.5.023151

[12] Adam Callison. "Kontinuerlig-tids kvanteberegning". Ph.d.-afhandling. Imperial College London. (2021).
https://​/​doi.org/​10.25560/​91503

[13] Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon og Nicholas Chancellor. "Energetisk perspektiv på hurtige quenches i kvanteudglødning". PRX Quantum 2, 010338 (2021).
https://​/​doi.org/​10.1103/​PRXQuantum.2.010338

[14] JM Deutsch. "Kvantestatistisk mekanik i et lukket system". Phys. Rev. A 43, 2046-2049 (1991).
https://​/​doi.org/​10.1103/​PhysRevA.43.2046

[15] Mark Srednicki. "Kaos og kvantetermalisering". Phys. Rev. E 50, 888-901 (1994).
https://​/​doi.org/​10.1103/​PhysRevE.50.888

[16] Joshua M Deutsch. "Eigenstate-termaliseringshypotese". Rapporter om fremskridt i fysik 81, 082001 (2018).
https:/​/​doi.org/​10.1088/​1361-6633/​aac9f1

[17] Marcos Rigol. "Opdeling af termalisering i endelige endimensionelle systemer". Phys. Rev. Lett. 103, 100403 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.103.100403

[18] Fabian HL Essler og Maurizio Fagotti. "Sluk dynamik og afslapning i isolerede integrerbare kvantespinkæder". Journal of Statistical Mechanics: Theory and Experiment 2016, 064002 (2016).
https:/​/​doi.org/​10.1088/​1742-5468/​2016/​06/​064002

[19] Marlon Brenes, Tyler LeBlond, John Goold og Marcos Rigol. "Eigenstate-termalisering i et lokalt forstyrret integrerbart system". Phys. Rev. Lett. 125, 070605 (2020).
https://​/​doi.org/​10.1103/​PhysRevLett.125.070605

[20] Jae Dong Noh. "Eigenstate-termaliseringshypotese og egentilstand-til-egenstats-fluktuationer". Phys. Rev. E 103, 012129 (2021).
https://​/​doi.org/​10.1103/​PhysRevE.103.012129

[21] David A. Huse, Rahul Nandkishore, Vadim Oganesyan, Arijeet Pal og SL Sondhi. "Lokaliseringsbeskyttet kvanteorden". Phys. Rev. B 88, 014206 (2013).
https://​/​doi.org/​10.1103/​PhysRevB.88.014206

[22] Rahul Nandkishore og David A. Huse. "Mangekropslokalisering og termalisering i kvantestatistisk mekanik". Annual Review of Condensed Matter Physics 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. "Mangekropslokalisering og kvantetermalisering". Nature Physics 14, 979-983 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0305-7

[24] Marcos Rigol, Vanja Dunjko og Maxim Olshanii. "Termalisering og dens mekanisme for generiske isolerede kvantesystemer". Nature 452, 854-858 (2008).
https://​/​doi.org/​10.1038/​nature06838

[25] Giulio Biroli, Corinna Kollath og Andreas M. Läuchli. "Effekt af sjældne udsving på termalisering af isolerede kvantesystemer". Phys. Rev. Lett. 105, 250401 (2010).
https://​/​doi.org/​10.1103/​PhysRevLett.105.250401

[26] Lea F. Santos og Marcos Rigol. "Begyndelse af kvantekaos i endimensionelle bosoniske og fermioniske systemer og dets forhold til termalisering". Phys. Rev. E 81, 036206 (2010).
https://​/​doi.org/​10.1103/​PhysRevE.81.036206

[27] R. Steinigeweg, J. Herbrych og P. Prelovšek. "Eigenstate-termalisering inden for isolerede spin-chain-systemer". Phys. Rev. E 87, 012118 (2013).
https://​/​doi.org/​10.1103/​PhysRevE.87.012118

[28] Hyungwon Kim, Tatsuhiko N. Ikeda og David A. Huse. "Test, om alle egentilstande overholder egentilstands-termaliseringshypotesen". Phys. Rev. E 90, 052105 (2014).
https://​/​doi.org/​10.1103/​PhysRevE.90.052105

[29] R. Steinigeweg, A. Khodja, H. Niemeyer, C. Gogolin og J. Gemmer. "Skub grænserne for egentilstands-termaliseringshypotesen mod mesoskopiske kvantesystemer". Phys. Rev. Lett. 112, 130403 (2014).
https://​/​doi.org/​10.1103/​PhysRevLett.112.130403

[30] Keith R. Fratus og Mark Srednicki. "Eigenstate-termalisering i systemer med spontant brudt symmetri". Phys. Rev. E 92, 040103 (2015).
https://​/​doi.org/​10.1103/​PhysRevE.92.040103

[31] Abdellah Khodja, Robin Steinigeweg og Jochen Gemmer. "Relevansen af ​​egentilstands-termaliseringshypotesen for termisk afslapning". Phys. Rev. E 91, 012120 (2015).
https://​/​doi.org/​10.1103/​PhysRevE.91.012120

[32] Rubem Mondaini og Marcos Rigol. "Eigenstate-termalisering i den todimensionelle tværgående felt-iseringsmodel. ii. off-diagonale matrixelementer af observerbare objekter”. Phys. Rev. E 96, 012157 (2017).
https://​/​doi.org/​10.1103/​PhysRevE.96.012157

[33] Toru Yoshizawa, Eiki Iyoda og Takahiro Sagawa. "Numerisk stor afvigelsesanalyse af egentilstands-termaliseringshypotesen". Phys. Rev. Lett. 120, 200604 (2018).
https://​/​doi.org/​10.1103/​PhysRevLett.120.200604

[34] David Jansen, Jan Stolpp, Lev Vidmar og Fabian Heidrich-Meisner. "Eigenstate-termalisering og kvantekaos i holstein-polaronmodellen". Phys. Rev. B 99, 155130 (2019).
https://​/​doi.org/​10.1103/​PhysRevB.99.155130

[35] S. Trotsky, YA. Chen, A. Flesch, IP McCulloch, U. Schollwöck, J. Eisert og I. Bloch. "Søge afslapningen mod ligevægt i en isoleret stærkt korreleret endimensionel bose-gas". Nature Physics 8, 325-330 (2012).
https://doi.org/​10.1038/​nphys2232

[36] Govinda Clos, Diego Porras, Ulrich Warring og Tobias Schaetz. "Tidsopløst observation af termalisering i et isoleret kvantesystem". Phys. Rev. Lett. 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 og Markus Greiner. "Kvante-termalisering gennem sammenfiltring i et isoleret system med mange krop". Science 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 og MD Lukin. "Kritisk termalisering af et uordnet dipolært spin-system i diamant". Phys. Rev. Lett. 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 og Benjamin L. Lev. "Termalisering nær integrerbarhed i en dipolær kvante newtons vugge". Phys. Rev. X 8, 021030 (2018).
https://​/​doi.org/​10.1103/​PhysRevX.8.021030

[40] JR Johansson, PD Nation, og Franco Nori. "Qutip: En open source python-ramme for dynamikken i åbne kvantesystemer". Computer Physics Communications 183, 1760-1772 (2012).
https://​/​doi.org/​10.1016/​j.cpc.2012.02.021

[41] JR Johansson, PD Nation, og Franco Nori. "Qutip 2: En pythonramme for dynamikken i åbne kvantesystemer". Computer Physics Communications 184, 1234-1240 (2013).
https://​/​doi.org/​10.1016/​j.cpc.2012.11.019

[42] Aric A. Hagberg, Daniel A. Schult og Pieter J. Swart. "Udforsker netværksstruktur, dynamik og funktion ved hjælp af networkx". I Gaël Varoquaux, Travis Vaught og Jarrod Millman, redaktører, Proceedings of the 7th Python in Science Conference. Side 11 – 15. Pasadena, CA USA (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 og Xiangjie Kong. "Random walks: En gennemgang af algoritmer og applikationer". IEEE Transactions on Emerging Topics in Computational Intelligence 4, 95-107 (2020).
https://​/​doi.org/​10.1109/​tetci.2019.2952908

[44] Henrik Wilming, Thiago R. de Oliveira, Anthony J. Short og Jens Eisert. "Ligevægtstider i lukkede kvante-mangelegemesystemer". Side 435–455. Springer International Publishing. (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_18

[45] James R. Garrison og Tarun Grover. "Koder en enkelt egentilstand den fulde hamiltonian?". Fysisk gennemgang X 8 (2018).
https://​/​doi.org/​10.1103/​physrevx.8.021026

[46] Peter Reimann. "Eigenstate-termalisering: Deutschs tilgang og videre". New Journal of Physics 17, 055025 (2015).
https:/​/​doi.org/​10.1088/​1367-2630/​17/​5/​055025

[47] Tameem Albash og Daniel A. Lidar. "Adiabatisk kvanteberegning". Anmeldelser af Modern Physics 90 (2018).
https://​/​doi.org/​10.1103/​revmodphys.90.015002

[48] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori og William D Oliver. "Perspektiver af kvanteudglødning: metoder og implementeringer". Rapporter om fremskridt i fysik 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[49] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler og Mikhail D. Lukin. "Quantum omtrentlig optimeringsalgoritme: Ydeevne, mekanisme og implementering på enheder på kort sigt". Phys. Rev. X 10, 021067 (2020).
https://​/​doi.org/​10.1103/​PhysRevX.10.021067

[50] Laba og Tkachuk. "Geometriske karakteristika ved kvanteevolution: krumning og torsion". Condensed Matter Physics 20, 13003 (2017).
https://​/​doi.org/​10.5488/​cmp.20.13003

[51] Kh.P. Gnatenko, HP Laba og VM Tkachuk. "Geometriske egenskaber ved evolutionære graftilstande og deres påvisning på en kvantecomputer". Physics Letters A 452, 128434 (2022).
https://​/​doi.org/​10.1016/​j.physleta.2022.128434

[52] Luca D'Alessio, Yariv Kafri, Anatoli Polkovnikov og Marcos Rigol. "Fra kvantekaos og egentilstandstermalisering til statistisk mekanik og termodynamik". Advances in Physics 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 og Francesco Zamponi. "Ydeevne af den kvante-adiabatiske algoritme på tilfældige tilfælde af to optimeringsproblemer på almindelige hypergrafer". Fysisk gennemgang A 86 (2012).
https://​/​doi.org/​10.1103/​physreva.86.052334

[54] Mark Jeansonne og Joe Foley. "Gennemgang af den eksponentielt modificerede gaussiske (emg) funktion siden 1983". Journal of Chromatography Science 29, 258-266 (1991).
https://​/​doi.org/​10.1093/​chromsci/​29.6.258

[55] Yuri Kalambet, Yuri Kozmin, Ksenia Mikhailova, Igor Nagaev og Pavel Tikhonov. "Rekonstruktion af kromatografiske toppe ved hjælp af den eksponentielt modificerede gaussiske funktion". Journal of Chemometrics 25, 352-356 (2011).
https://​/​doi.org/​10.1002/​cem.1343

[56] Stephen J. Blundell og Katherine M. Blundell. "Begreber i termisk fysik". Oxford University Press. (2009).
https://​/​doi.org/​10.1093/​acprof:oso/​9780199562091.001.0001

[57] Elizabeth Crosson og Samuel Slezak. "Klassisk simulering af højtemperatur kvantemodeller" (2020). arXiv:2002.02232.
arXiv: 2002.02232

[58] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore og Matthew J. Reagor. "Entanglement perspektiv på den omtrentlige kvanteoptimeringsalgoritme". Fysisk gennemgang A 106 (2022).
https://​/​doi.org/​10.1103/​physreva.106.022423

[59] JM Deutsch. "Termodynamisk entropi af en energiegentilstand med mange legeme". New Journal of Physics 12, 075021 (2010).
https:/​/​doi.org/​10.1088/​1367-2630/​12/​7/​075021

[60] JM Deutsch, Haibin Li og Auditya Sharma. "Mikroskopisk oprindelse af termodynamisk entropi i isolerede systemer". Phys. Rev. E 87, 042135 (2013).
https://​/​doi.org/​10.1103/​PhysRevE.87.042135

[61] Lea F. Santos, Anatoli Polkovnikov og Marcos Rigol. "Entropi af isolerede kvantesystemer efter en quench". Phys. Rev. Lett. 107, 040601 (2011).
https://​/​doi.org/​10.1103/​PhysRevLett.107.040601

[62] Michael A. Nielsen og Isaac L. Chuang. "Kvanteberegning og kvanteinformation: 10-års jubilæumsudgave". Cambridge University Press. (2010).
https://​/​doi.org/​10.1017/​CBO9780511976667

[63] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. "En omtrentlig kvanteoptimeringsalgoritme" (2014). arXiv:1411.4028.
arXiv: 1411.4028

[64] Milena Grifoni og Peter Hänggi. "Drevet kvantetunneling". Physics Reports 304, 229-354 (1998).
https:/​/​doi.org/​10.1016/​S0370-1573(98)00022-2

[65] Masahito Ueda. "Kvanteækvilibrering, termalisering og prætermalisering i ultrakolde atomer". Nature Reviews Physics 2, 669–681 (2020).
https://​/​doi.org/​10.1038/​s42254-020-0237-x

[66] Luca D'Alessio og Anatoli Polkovnikov. "Mange-krops energilokaliseringsovergang i periodisk drevne systemer". Annals of Physics 333, 19-33 (2013).
https://​/​doi.org/​10.1016/​j.aop.2013.02.011

[67] Luca D'Alessio og Marcos Rigol. "Langtidsadfærd af isolerede periodisk drevne interagerende gittersystemer". Fysisk gennemgang X 4 (2014).
https://​/​doi.org/​10.1103/​physrevx.4.041048

[68] Achilleas Lazarides, Arnab Das og Roderich Moessner. "Ligevægtstilstande for generiske kvantesystemer underlagt periodisk kørsel". Phys. Rev. E 90, 012110 (2014).
https://​/​doi.org/​10.1103/​PhysRevE.90.012110

[69] Keith R. Fratus og Mark Allen Srednicki. "Eigenstate-termalisering og spontan symmetribrud i den endimensionelle tværfelts-model med magt-lov-interaktioner" (2016). arXiv:1611.03992.
arXiv: 1611.03992

[70] Attila Felinger, Tamás Pap og János Inczédy. "Kurvetilpasning til asymmetriske kromatogrammer med det udvidede Kalman-filter i frekvensdomæne". Talanta 41, 1119-1126 (1994).
https:/​/​doi.org/​10.1016/​0039-9140(94)80081-2

[71] KF Riley, MP Hobson og SJ Bence. "Matematiske metoder til fysik og teknik: En omfattende guide". Cambridge University Press. (2006). 3 udgave.
https://​/​doi.org/​10.1017/​CBO9780511810763

[72] Brian C. Hall. "En elementær introduktion til grupper og repræsentationer" (2000). arXiv:math-ph/​0005032.
arXiv:math-ph/0005032

[73] Michael M. Wolf, Frank Verstraete, Matthew B. Hastings og J. Ignacio Cirac. "Områdelove i kvantesystemer: Gensidig information og korrelationer". Phys. Rev. Lett. 100, 070502 (2008).
https://​/​doi.org/​10.1103/​PhysRevLett.100.070502

[74] Martin Kliesch og Arnau Riera. "Egenskaber ved termiske kvantetilstande: Temperaturens lokalitet, henfald af korrelationer og mere". I grundlæggende fysikteorier. Side 481–502. Springer International Publishing (2018).
https:/​/​doi.org/​10.1007/​978-3-319-99046-0_20

[75] SH Simon. "Oxford solid state basics". OUP Oxford. (2013).

Citeret af

[1] R. Au-Yeung, B. Camino, O. Rathore og V. Kendon, "Quantealgoritmer til videnskabelige applikationer", arXiv: 2312.14904, (2023).

[2] Sebastian Schulz, Dennis Willsch og Kristel Michielsen, “Guided quantum walk”, arXiv: 2308.05418, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-02-14 02:07:09). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-02-14 02:07:08).

Tidsstempel:

Mere fra Quantum Journal