Meje kratkoročnega razvoja lokalnih hamiltonianov

Ponovno objavil Platon

Spremljevalci: 0

Ali Hamed Moosavian, Seyed Sajad Kahani in Salman Beigi

QuOne Lab, Center za raziskave in inovacije Phanous, Teheran, Iran

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Pričakuje se, da bodo evolucije lokalnih hamiltonianov v kratkem času ostale lokalne in tako omejene. V tem prispevku potrjujemo to intuicijo z dokazovanjem nekaterih omejitev kratkočasovnega razvoja lokalnih časovno odvisnih Hamiltonianov. Pokažemo, da je porazdelitev rezultatov meritev kratkočasovnih (največ logaritemskih) evolucij lokalnih hamiltonianov $koncentrirana$ in zadošča $textit{izoperimetrični neenakosti}$. Za predstavitev eksplicitnih aplikacij naših rezultatov preučujemo problem $M$$small{AX}$$C$$small{UT}$ in sklepamo, da kvantno žarjenje potrebuje vsaj čas izvajanja, ki se logaritemsko spreminja v velikosti problema na premagati klasične algoritme na $M$$small{AX}$$C$$small{UT}$. Za določitev naših rezultatov smo dokazali tudi Lieb-Robinsonovo vezavo, ki deluje za časovno odvisne Hamiltonije, ki bi lahko bili neodvisno zanimivi.

Predstavljena slika: Ta ilustracija prikazuje verjetnostno porazdelitev Hammingove uteži treh različnih stanj $n$-kubitov za $n=100$. Sredinska porazdelitev na sredini (modra) je tipična porazdelitev za začetno stanje izdelka (npr. $|+rangle^{otimes n}$). Porazdelitev z vrhom na desni (oranžna) predstavlja porazdelitev po kratkem časovnem razvoju začetnega stanja, ki ga opisuje izrek 2 rokopisa. Porazdelitev z dvema vrhovoma na obeh straneh spektra (zeleno) je približek za stanje GHZ. To kaže, da stanja GHZ ni mogoče ustvariti niti približno s kratkotrajnim kvantnim žarjenjem.

Priljubljen povzetek

Pričakuje se, da bodo evolucije lokalnih hamiltonianov v kratkem času ostale lokalne in tako omejene. V tem prispevku potrjujemo to intuicijo z dokazovanjem nekaterih omejitev kratkočasovnega razvoja lokalnih časovno odvisnih Hamiltonianov. Pokažemo, da je porazdelitev rezultatov meritev kratkočasovnih (največ logaritemskih) evolucij lokalnih hamiltonianov koncentrirana in zadošča izoperimetrični neenakosti. Za predstavitev eksplicitnih aplikacij naših rezultatov preučujemo problem MaxCut in sklepamo, da kvantno žarjenje potrebuje vsaj čas izvajanja, ki se logaritmično spreminja glede na velikost problema, da premaga klasične algoritme na MaxCut.

► BibTeX podatki

@članek{Moosavian2022meje kratkega časa, doi = {10.22331/q-2022-06-27-744}, url = {https://doi.org/10.22331/q-2022-06-27-744}, title = {Meje {S}kratkočasovne {E}volucije {L}lokalnih {H}amiltoncev}, avtor = {Moosavian, Ali Hamed in Kahani, Seyed Sajad in Beigi, Salman}, dnevnik = {{Quantum}}, issn = {2521-327X}, založnik = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, obseg = {6}, strani = {744}, mesec = jun, leto = {2022} }

► Reference

[1] T. Kadowaki in H. Nishimori. Kvantno žarjenje v prečnem Isingovem modelu. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[2] E. Farhi, J. Goldstone, S. Gutmann in M. Sipser. Kvantno računanje z adiabatsko evolucijo. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106

[3] T. Kato. O adiabatnem izreku kvantne mehanike. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435

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

[5] T. Albash in DA Lidar. Adiabatno kvantno računanje. Reviews of Modern Physics 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[6] I. Hen in FM Spedalieri. Kvantno žarjenje za omejeno optimizacijo. Uporabljen fizični pregled 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007

[7] S. Puri, CK Andersen, AL Grimsmo in A. Blais. Kvantno žarjenje z vsemi povezanimi nelinearnimi oscilatorji. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785

[8] W. Lechner, P. Hauke in P. Zoller. Arhitektura kvantnega žarjenja s povezljivostjo vseh z vsemi iz lokalnih interakcij. Znanstveni napredek 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838

[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble in S. Kais. Kvantno žarjenje za prafaktorizacijo. Znanstvena poročila 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z

[10] RY Li, R. Di Felice, R. Rohs in DA Lidar. Kvantno žarjenje v primerjavi s klasičnim strojnim učenjem, uporabljeno za poenostavljen problem računalniške biologije. NPJ kvantne informacije 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8

[11] L. Stella, GE Santoro in E. Tosatti. Optimizacija s kvantnim žarjenjem: Lekcije iz preprostih primerov. Physical Review B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303

[12] O. Titiloye in A. Crispin. Kvantno žarjenje problema barvanja grafov. Diskretna optimizacija 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001

[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar in M. Spiropulu. Reševanje Higgsovega optimizacijskega problema s kvantnim žarjenjem za strojno učenje. Narava 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047

[14] KL Pudenz, T. Albash in D. A Lidar. Popravek kvantnega žarjenja za naključne Isingove probleme. 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 in A. Aspuru-Guzik. Iskanje nizkoenergijskih konformacij mrežnih proteinskih modelov s kvantnim žarjenjem. Znanstvena poročila 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571

[16] KL Pudenz, T. Albash in D. A Lidar. Kvantno žarjenje s popravljenimi napakami s stotinami kubitov. Nature Communications 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243

[17] R. Martoňák, GE Santoro in E. Tosatti. Kvantno žarjenje problema trgovskega potnika. Physical Review E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701

[18] SH Adachi in MP Henderson. Uporaba kvantnega žarjenja za usposabljanje globokih nevronskih mrež. arXiv:1510.06356 [količinsko-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356

[19] M. W Johnson, et al. Kvantno žarjenje z izdelanimi vrtljaji. Narava 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012

[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor in DA Lidar. Eksperimentalni podpis programabilnega kvantnega žarjenja. Nature Communications 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067

[21] AD King, et al. Koherentno kvantno žarjenje v programabilni 2000-kubitni Isingovi verigi. arXiv:2202.05847 [kvant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847

[22] B. Foxen, et al. Predstavitev zveznega nabora vrat z dvema kubitoma za bližnjeročne kvantne algoritme. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504

[23] K. Wright, et al. Primerjalno testiranje 11-qubitnega kvantnega računalnika. Nature Communications 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2

[24] EJ Crosson in DA Lidar. Obeti za kvantno izboljšanje z diabatskim kvantnim žarjenjem. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6

[25] E. Farhi, J. Goldstone in S. Gutmann. Algoritem kvantne približne optimizacije. arXiv:1411.4028 [kvant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[26] E. Farhi, D. Gamarnik in S. Gutmann. Algoritem kvantne približne optimizacije mora videti celoten graf: primeri najslabšega primera. arXiv:2005.08747 [kvant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747

[27] E. Farhi, D. Gamarnik in S. Gutmann. Algoritem kvantne približne optimizacije mora videti celoten graf: tipičen primer. arXiv:2004.09002 [kvant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002

[28] S. Bravyi, A. Kliesch, R. Koenig in E. Tang. Ovire za variacijsko kvantno optimizacijo zaradi zaščite simetrije. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[29] S. Bravyi, D. Gosset in R. Movassagh. Klasični algoritmi za kvantne srednje vrednosti. Fizika narave 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8

[30] S. Bravyi, A. Kliesch, R. Koenig in E. Tang. Hibridni kvantno-klasični algoritmi za približno barvanje grafov. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678

[31] L. Eldar in AW Harrow. Lokalni hamiltonci, katerih osnovna stanja je težko približno oceniti. Leta 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. Harkov in AV Gorškov. Optimalni protokoli pri problemih kvantnega žarjenja in algoritmov kvantne približne optimizacije. Physical Review Letters 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505

[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Harkov in AV Gorškov. Obnašanje analognih kvantnih algoritmov. arXiv:2107.01218 [kvant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218

[34] LC Venuti, D. D'Alessandro in DA Lidar. Optimalni nadzor za kvantno optimizacijo zaprtih in odprtih sistemov. Uporabljen fizični pregled 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023

[35] AM Childs, Y. Su, MC Tran, N. Wiebe in S. Zhu. Teorija Trotterjeve napake s komutatorskim skaliranjem. Physical Review X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[36] B. Nachtergaele, Y. Ogata in R. Sims. Širjenje korelacij v kvantnih mrežnih sistemih. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6

[37] B. Nachtergaele in R. Sims. Lieb-Robinsonove meje v kvantni fiziki več teles. Sodobna matematika 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429

[38] S. Bravyi, MB Hastings in F. Verstraete. Lieb-robinsonove meje in generiranje korelacije ter topološki kvantni red. Physical Review Letters 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401

[39] C.-F. Chen in A. Lucas. Meje rasti operatorja iz teorije grafov. Sporočila v matematični fiziki 385, strani 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6

[40] EH Lieb in DW Robinson. Končna skupinska hitrost kvantnih spinskih sistemov. Sporočila v matematični fiziki 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779

[41] J. Haah, MB Hastings, R. Kothari in GH Low. Kvantni algoritem za simulacijo evolucije mrežnih hamiltonianov v realnem času. 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 in P. Sarnak. Ramanujan grafi. Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[43] B. Mohar. Izoperimetrična števila grafov. Journal of Combinatorial Theory, serija B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4

[44] AW Marcus, DA Spielman in N. Srivastava. Družine prepletanja IV: Bipartitni Ramanujanovi grafi vseh velikosti. Leta 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 in N. Srivastava. Družine prepletanja IV: Bipartitni Ramanujanovi grafi vseh velikosti. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X

[46] C. Hall, D. Puder in WF Sawin. Ramanujanova prekrivanja grafov. Napredek v matematiki 323, 367–410 (2018).
https: / / doi.org/ 10.1016 / j.aim.2017.10.042

[47] MX Goemans in DP Williamson. Izboljšani aproksimacijski algoritmi za probleme največjega reza in zadovoljivosti z uporabo poldoločenega programiranja. Journal of the ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[48] RD Somma, D. Nagaj in M. Kieferová. Kvantna pospešitev s kvantnim žarjenjem. Physical Review Letters 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501

[49] MB Hastings. Moč adiabatnega kvantnega računanja brez predznaka. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597

[50] A. Gilyén, MB Hastings in U. Vazirani. (Sub)eksponentna prednost adiabatnega kvantnega računanja brez problema predznaka. V zborniku letnega simpozija ACM o teoriji računalništva (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060

[51] R. Bhatia. Matrična analiza. Diplomska besedila iz matematike. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8

[52] R. Bhatia. Pozitivno določene matrike. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787

[53] BD McKay, NC Wormald in B. Wysocka. Kratki cikli v naključnih pravilnih grafih. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819

[54] F. Kardoš, D. Král in J. Volec. Največji robni rezi v kubičnih grafih z velikim obsegom in v naključnih kubičnih grafih. Naključne strukture in algoritmi 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471

[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi in GB Sorkin. Naključni MAX SAT, naključni MAX CUT in njihovi fazni prehodi. Naključne strukture in algoritmi 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015

[56] A. Dembo, A. Montanari in S. Sen. Ekstremni rezi redkih naključnih grafov. Annals of Probability 45, 1190–1217 (2017).
https://doi.org/ 10.1214/15-AOP1084

Navedel

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé in Daniel Stilck França, "Omejitve variacijskih kvantnih algoritmov: pristop kvantnega optimalnega transporta", arXiv: 2204.03455.

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-07-19 03:10:09). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2022-07-19 03:10:07).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.