Paikallisten hamiltonilaisten lyhytaikaisen kehityksen rajat

Julkaissut Platon

seuraajia: 0

Ali Hamed Moosavian, Seyed Sajad Kahani ja Salman Beigi

QuOne Lab, Phanous Research and Innovation Center, Teheran, Iran

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Paikallisten hamiltonilaisten kehityksen lyhyessä ajassa odotetaan pysyvän paikallisena ja siten rajoitettuna. Tässä artikkelissa vahvistamme tämän intuition osoittamalla joitain rajoituksia paikallisten ajasta riippuvaisten hamiltonilaisten lyhytaikaiselle kehitykselle. Osoitamme, että paikallisten Hamiltonilaisten lyhytaikaisten (korkeintaan logaritmien) evoluutioiden mittaustulosten jakauma on $keskittynyt$ ja täyttää $textit{isoperimetrisen epäyhtälön}$. Esittelemme tulostemme eksplisiittisiä sovelluksia tutkimalla ongelmaa $M$$small{AX}$$C$$small{UT}$ ja päättelemme, että kvanttihehkutus tarvitsee vähintään suoritusajan, joka skaalautuu logaritmisesti tehtävän kokoon. päihittää klassiset algoritmit $M$$small{AX}$$C$$small{UT}$:lla. Tulostemme vahvistamiseksi todistamme myös Lieb-Robinson-sidon, joka toimii ajasta riippuvaisille hamiltonilaisille, jotka saattavat olla riippumattomia kiinnostavia.

Suositeltu kuva: Tämä kuva esittää Hamming-painon todennäköisyysjakauman kolmessa eri $n$-qubit-tilassa, kun $n=100$. Keskitetty jakauma keskellä (sininen) on tyypillinen jakauma tuotteen alkutilalle (esim. $|+rangle^{otimes n}$). Jakauma, joka on huipussaan juuri oikealla (oranssi), edustaa jakaumaa lyhyen ajan kuluttua käsikirjoituksen lauseessa 2 kuvatusta alkutilan kehityksestä. Jakauma, jossa on kaksi huippua spektrin kummallakin puolella (vihreä), on likimääräinen GHZ-tila. Tämä osoittaa, että GHZ-tilaa ei voida luoda edes likimääräisesti lyhytaikaisella kvanttihehkutuksella.

Suosittu yhteenveto

Paikallisten hamiltonilaisten kehityksen lyhyessä ajassa odotetaan pysyvän paikallisena ja siten rajoitettuna. Tässä artikkelissa vahvistamme tämän intuition osoittamalla joitain rajoituksia paikallisten ajasta riippuvaisten hamiltonilaisten lyhytaikaiselle kehitykselle. Osoitamme, että paikallisten Hamiltonilaisten lyhytaikaisten (korkeintaan logaritmien) evoluutioiden mittaustulosten jakauma on keskittynyt ja täyttää isoperimetrisen epäyhtälön. Esittelemme tuloksiamme eksplisiittisiä sovelluksia tutkimalla MaxCut-ongelmaa ja päättelemme, että kvanttihehkutus tarvitsee vähintään suoritusajan, joka skaalautuu logaritmisesti ongelman kokoon voittaakseen klassiset algoritmit MaxCutissa.

► BibTeX-tiedot

@article{Moosavian2022limitsofhorttime, doi = {10.22331/q-2022-06-27-744}, url = {https://doi.org/10.22331/q-2022-06-27-744}, title = {{S}lyhytaikaisen {E}{L}paikallisen {H}miltonian} voluution rajat, kirjoittaja = {Moosavian, Ali Hamed ja Kahani, Seyed Sajad ja Beigi, Salman}, päiväkirja = {{Kvantti}}, issn = {2521-327X}, julkaisija = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, tilavuus = {6}, sivut = {744}, kuukausi = kesäkuu, vuosi = {2022} }

► Viitteet

[1] T. Kadowaki ja H. Nishimori. Kvanttihehkutus poikkisuuntaisessa Ising-mallissa. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[2] E. Farhi, J. Goldstone, S. Gutmann ja M. Sipser. Adiabatic Evolutionin kvanttilaskenta. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106

[3] T. Kato. Kvanttimekaniikan adiabaattisesta lauseesta. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435

[4] M. Born ja V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193

[5] T. Albash ja DA Lidar. Adiabaattinen kvanttilaskenta. Reviews of Modern Physics 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[6] I. Hen ja FM Spedalieri. Kvanttihehkutus rajoitettua optimointia varten. Physical Review Applied 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007

[7] S. Puri, CK Andersen, AL Grimsmo ja A. Blais. Kvanttihehkutus all-to-all-kytketyillä epälineaarisilla oskillaattorilla. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785

[8] W. Lechner, P. Hauke ja P. Zoller. Kvanttihehkutusarkkitehtuuri, jossa on kaikki-kaikkien liitettävyys paikallisista vuorovaikutuksista. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838

[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble ja S. Kais. Kvanttihehkutus primäärifaktorointiin. Scientific Reports 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z

[10] RY Li, R. Di Felice, R. Rohs ja DA Lidar. Kvanttihehkutus verrattuna klassiseen koneoppimiseen sovellettu yksinkertaistettuun laskennallisen biologian ongelmaan. NPJ-kvanttitiedot 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8

[11] L. Stella, GE Santoro ja E. Tosatti. Optimointi kvanttihehkutuksella: Oppitunnit yksinkertaisista tapauksista. Physical Review B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303

[12] O. Titiloye ja A. Crispin. Graafin väritysongelman kvanttihehkutus. Discrete Optimization 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001

[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar ja M. Spiropulu. Higgsin optimointiongelman ratkaiseminen kvanttihehkutuksella koneoppimista varten. Nature 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047

[14] KL Pudenz, T. Albash ja D. A Lidar. Kvanttihehkutuskorjaus satunnaisille Ising-ongelmille. Physical Review A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302

[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose ja A. Aspuru-Guzik. Hilaproteiinimallien matalaenergisten konformaatioiden löytäminen kvanttihehkutuksella. Scientific Reports 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571

[16] KL Pudenz, T. Albash ja D. A Lidar. Virhekorjattu kvanttihehkutus sadoilla kubiteilla. Luontoviestintä 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243

[17] R. Martoňák, GE Santoro ja E. Tosatti. Matkustaja-myyjä-ongelman kvanttihehkutus. Physical Review E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701

[18] SH Adachi ja kansanedustaja Henderson. Kvanttihehkutuksen soveltaminen syvien hermoverkkojen koulutukseen. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356

[19] M. W. Johnson, et ai. Kvanttihehkutus valmistetuilla spineillä. Nature 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012

[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor ja DA Lidar. Ohjelmoitavan kvanttihehkutuksen kokeellinen allekirjoitus. Luontoviestintä 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067

[21] AD King, et ai. Koherentti kvanttihehkutus ohjelmoitavassa 2000 kubitin Ising-ketjussa. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847

[22] B. Foxen et ai. Jatkuvan kahden kubitin porttien joukon osoittaminen lähiajan kvanttialgoritmeille. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504

[23] K. Wright, et ai. 11 kubitin kvanttitietokoneen benchmarking. Luontoviestintä 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2

[24] EJ Crosson ja DA Lidar. Kvanttiparannuksen näkymät diabaattisen kvanttihehkutuksen avulla. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6

[25] E. Farhi, J. Goldstone ja S. Gutmann. Kvanttilikimääräinen optimointialgoritmi. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[26] E. Farhi, D. Gamarnik ja S. Gutmann. Kvanttilikimääräisen optimointialgoritmin on nähtävä koko kaavio: esimerkkejä pahimmasta tapauksesta. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747

[27] E. Farhi, D. Gamarnik ja S. Gutmann. Kvanttilikimääräisen optimointialgoritmin on nähtävä koko kaavio: tyypillinen tapaus. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002

[28] S. Bravyi, A. Kliesch, R. Koenig ja E. Tang. Esteet variaatiokvanttioptimoinnille symmetria-suojauksesta. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[29] S. Bravyi, D. Gosset ja R. Movassagh. Klassiset algoritmit kvanttikeskiarvoille. Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8

[30] S. Bravyi, A. Kliesch, R. Koenig ja E. Tang. Hybridi-kvanttiklassiset algoritmit likimääräiseen graafin väritykseen. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678

[31] L. Eldar ja AW Harrow. Paikalliset hamiltonilaiset, joiden pohjatiloja on vaikea arvioida. Vuonna 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46

[32] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov ja AV Gorshkov. Optimaaliset protokollat kvanttihehkutuksessa ja kvanttilikimääräisen optimointialgoritmin ongelmissa. Physical Review Letters 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505

[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov ja AV Gorshkov. Analogisten kvanttialgoritmien käyttäytyminen. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218

[34] LC Venuti, D. D'Alessandro ja DA Lidar. Optimaalinen ohjaus suljettujen ja avoimien järjestelmien kvanttioptimointiin. Physical Review Applied 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023

[35] AM Childs, Y. Su, MC Tran, N. Wiebe ja S. Zhu. Trotter-virheen teoria kommutaattorin skaalauksella. Physical Review X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[36] B. Nachtergaele, Y. Ogata ja R. Sims. Korrelaatioiden leviäminen kvanttihilajärjestelmissä. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6

[37] B. Nachtergaele ja R. Sims. Lieb-Robinson rajoittuu kvanttimonikehofysiikkaan. Contemporary Mathematics 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429

[38] S. Bravyi, MB Hastings ja F. Verstraete. Lieb-robinsonin rajat ja korrelaatioiden ja topologisen kvanttijärjestyksen generointi. Physical Review Letters 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401

[39] C.-F. Chen ja A. Lucas. Operaattoreiden kasvurajat graafiteoriasta. Communications in Mathematical Physics 385, sivut 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6

[40] EH Lieb ja DW Robinson. Kvanttispin-järjestelmien äärellinen ryhmänopeus. Communications in Mathematical Physics 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779

[41] J. Haah, MB Hastings, R. Kothari ja GH Low. Kvanttialgoritmi hilan Hamiltonian reaaliaikaisen kehityksen simuloimiseen. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350–360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041

[42] A. Lubotzky, R. Phillips ja P. Sarnak. Ramanujan-kaaviot. Combinatorica 8, 261-277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[43] B. Mohar. Kuvaajien isoperimetriset luvut. Journal of Combinatorial Theory, sarja B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4

[44] AW Marcus, DA Spielman ja N. Srivastava. Interlacing Families IV: Kaikenkokoiset kaksipuoliset Ramanujan-kaaviot. Vuonna 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87

[45] AW Marcus, DA Spielman ja N. Srivastava. Interlacing Families IV: Kaikenkokoiset kaksipuoliset Ramanujan-kaaviot. SIAM Journal on Computing 47, 2488–2509 (2018).
https://doi.org/ 10.1137/16M106176X

[46] C. Hall, D. Puder ja WF Sawin. Graafisten Ramanujan-peitokset. Advances in Mathematics 323, 367–410 (2018).
https: / / doi.org/ 10.1016 / j.aim.2017.10.042

[47] MX Goemans ja DP Williamson. Parannetut approksimaatioalgoritmit maksimileikkaus- ja tyydyttävyysongelmiin käyttämällä puolimääräistä ohjelmointia. Journal of the ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / +227683.227684

[48] RD Somma, D. Nagaj ja M. Kieferová. Quantum Speedup, Quantum Hehkutus. Physical Review Letters 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501

[49] MB Hastings. Adiabaattisen kvanttilaskennan teho ilman merkkiongelmaa. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597

[50] A. Gilyén, MB Hastings ja U. Vazirani. (Sub)Adiabaattisen kvanttilaskennan eksponentiaalinen etu ilman etumerkkiongelmaa. Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / +3406325.3451060

[51] R. Bhatia. Matriisianalyysi. Matematiikan tutkinnon tekstit. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8

[52] R. Bhatia. Positiiviset määrätyt matriisit. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / +9781400827787

[53] BD McKay, NC Wormald ja B. Wysocka. Lyhyet syklit satunnaisissa säännöllisissä kaavioissa. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / +1819

[54] F. Kardoš, D. Král ja J. Volec. Maksimireunaleikkaukset kuutiokaavioissa, joissa on suuri ympärysmitta, ja satunnaisissa kuutiokaavioissa. Random Structures & Algorithms 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471

[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi ja GB Sorkin. Satunnainen MAX SAT, satunnainen MAX CUT ja niiden vaihemuutokset. Random Structures and Algorithms 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015

[56] A. Dembo, A. Montanari ja S. Sen. Harvaiden satunnaisten kuvaajien äärimmäiset leikkaukset. Annals of Probability 45, 1190–1217 (2017).
https://doi.org/ 10.1214/15-AOP1084

Viitattu

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé ja Daniel Stilck França, "Limitations of variational quantum algoritmms: a quantum optimal transport approach" arXiv: 2204.03455.

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-07-19 03:10:09). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2022-07-19 03:10:07).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.