Gränser för korttidsutvecklingen för lokala Hamiltonianer

Återutgiven av Platon

anhängare: 0

Ali Hamed Moosavian, Seyed Sajad Kahani och Salman Beigi

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

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Utvecklingen av lokala Hamiltonianer på kort tid förväntas förbli lokal och därmed begränsad. I det här dokumentet validerar vi denna intuition genom att bevisa några begränsningar för korttidsutvecklingar av lokala tidsberoende Hamiltonianer. Vi visar att fördelningen av mätresultatet av korttids (högst logaritmiska) evolutioner av lokala Hamiltonianer är $koncentrerade$ och uppfyller en $textit{isoperimetrisk ojämlikhet}$. För att visa upp explicita tillämpningar av våra resultat studerar vi $M$$small{AX}$$C$$small{UT}$-problemet och drar slutsatsen att kvantglödgning behöver åtminstone en körtid som skalas logaritmiskt i problemstorleken till slå klassiska algoritmer på $M$$small{AX}$$C$$small{UT}$. För att fastställa våra resultat, bevisar vi också en Lieb-Robinson bunden som fungerar för tidsberoende Hamiltonianer som kan vara av oberoende intresse.

Utvald bild: Denna illustration visar sannolikhetsfördelningen av Hamming-vikten för tre olika $n$-qubit-tillstånd för $n=100$. Den centrerade fördelningen i mitten (blå) är den typiska fördelningen för en produkts initialtillstånd (t.ex. $|+rangle^{otimes n}$). Fördelningen som är toppad precis till höger (orange) representerar fördelningen efter en kort tids utveckling av det initiala tillståndet som beskrivs av sats 2 i manuskriptet. Fördelningen som har två toppar på vardera sidan av spektrumet (grön) är en approximation för GHZ-tillståndet. Detta visar att GHZ-tillståndet inte kan genereras ens ungefär genom en korttids kvantglödgning.

Populär sammanfattning

Utvecklingen av lokala Hamiltonianer på kort tid förväntas förbli lokal och därmed begränsad. I det här dokumentet validerar vi denna intuition genom att bevisa några begränsningar för korttidsutvecklingar av lokala tidsberoende Hamiltonianer. Vi visar att fördelningen av mätresultatet av korttids (högst logaritmiska) evolutioner av lokala Hamiltonianer är koncentrerad och uppfyller en isoperimetrisk olikhet. För att visa upp explicita tillämpningar av våra resultat studerar vi MaxCut-problemet och drar slutsatsen att kvantglödgning behöver åtminstone en körtid som skalas logaritmiskt i problemstorleken för att slå klassiska algoritmer på MaxCut.

► BibTeX-data

@artikel{Moosavian2022limitsofshorttime, doi = {10.22331/q-2022-06-27-744}, url = {https://doi.org/10.22331/q-2022-06-27-744}, title = {Limits of {S}hort-{T}time {E}volution of {L}local {H}amiltonians}, författare = {Moosavian, Ali Hamed och Kahani, Seyed Sajad och Beigi, Salman}, journal = {{Quantum}}, issn = {2521-327X}, utgivare = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volym = {6}, sidor = {744}, månad = jun, år = {2022} }

► Referenser

[1] T. Kadowaki och H. Nishimori. Kvantglödgning i den tvärgående Ising-modellen. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[2] E. Farhi, J. Goldstone, S. Gutmann och M. Sipser. Kvantberäkning av adiabatisk evolution. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106

[3] T. Kato. Om kvantmekanikens adiabatiska sats. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / â € </ â € <doi.org/â€ <10.1143 / â € <JPSJ.5.435

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

[5] T. Albash och DA Lidar. Adiabatisk kvantberäkning. Reviews of Modern Physics 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[6] I. Hen och FM Spedalieri. Kvantglödgning för begränsad optimering. Fysisk granskning tillämpad 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007

[7] S. Puri, CK Andersen, AL Grimsmo och A. Blais. Kvantglödgning med allt-till-alla-anslutna olinjära oscillatorer. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785

[8] W. Lechner, P. Hauke och P. Zoller. En kvantglödgningsarkitektur med allt-till-alla-anslutning från lokala interaktioner. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838

[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble och S. Kais. Kvantglödgning för primärfaktorisering. Scientific Reports 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z

[10] RY Li, R. Di Felice, R. Rohs och DA Lidar. Kvantglödgning kontra klassisk maskininlärning tillämpas på ett förenklat beräkningsbiologiskt problem. NPJ kvantinformation 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8

[11] L. Stella, GE Santoro och E. Tosatti. Optimering genom kvantglödgning: Lärdomar från enkla fall. Physical Review B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303

[12] O. Titiloye och A. Crispin. Kvantglödgning av graffärgningsproblemet. 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 och M. Spiropulu. Att lösa ett Higgs-optimeringsproblem med kvantglödgning för maskininlärning. Nature 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047

[14] KL Pudenz, T. Albash och DA Lidar. Kvantglödgningskorrigering för slumpmässiga Ising-problem. 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 och A. Aspuru-Guzik. Att hitta lågenergikonformationer av gitterproteinmodeller genom kvantglödgning. Vetenskapliga rapporter 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571

[16] KL Pudenz, T. Albash och DA Lidar. Felkorrigerad kvantglödgning med hundratals kvantbitar. Naturkommunikationer 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243

[17] R. Martoňák, GE Santoro och E. Tosatti. Quantum glödgning av resande-säljare problemet. Physical Review E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701

[18] SH Adachi och MP Henderson. Tillämpning av kvantglödgning för träning av djupa neurala nätverk. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356

[19] M.W Johnson, et al. Kvantglödgning med tillverkade snurr. Nature 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012

[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor och DA Lidar. Experimentell signatur av programmerbar kvantglödgning. Naturkommunikationer 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067

[21] AD King, et al. Koherent kvantglödgning i en programmerbar 2000-qubit Ising-kedja. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847

[22] B. Foxen, et al. Demonstrera en kontinuerlig uppsättning av två-qubit-portar för nära sikt kvantalgoritmer. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504

[23] K. Wright, et al. Benchmarking av en 11-qubit kvantdator. Naturkommunikationer 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2

[24] EJ Crosson och DA Lidar. Utsikter för kvantförbättring med diabatisk kvantglödgning. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6

[25] E. Farhi, J. Goldstone och S. Gutmann. En ungefärlig kvantoptimeringsalgoritm. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[26] E. Farhi, D. Gamarnik och S. Gutmann. Quantum Approximate Optimization Algorithm måste se hela grafen: Worst Case-exempel. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747

[27] E. Farhi, D. Gamarnik och S. Gutmann. Quantum Approximate Optimization Algorithm måste se hela grafen: ett typiskt fall. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002

[28] S. Bravyi, A. Kliesch, R. Koenig och E. Tang. Hinder för variationsmässig kvantoptimering från symmetriskydd. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[29] S. Bravyi, D. Gosset och R. Movassagh. Klassiska algoritmer för kvantmedelvärden. Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8

[30] S. Bravyi, A. Kliesch, R. Koenig och E. Tang. Hybrid kvantklassiska algoritmer för ungefärlig graffärgning. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678

[31] L. Eldar och AW Harrow. Lokala Hamiltonbor vars marktillstånd är svåra att uppskatta. Under 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 och AV Gorshkov. Optimala protokoll i Quantum Annealing och Quantum Approximate Optimization Algoritmproblem. 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 och AV Gorshkov. Beteende hos analoga kvantalgoritmer. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218

[34] LC Venuti, D. D'Alessandro och DA Lidar. Optimal kontroll för kvantoptimering av slutna och öppna system. Fysisk granskning tillämpad 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023

[35] AM Childs, Y. Su, MC Tran, N. Wiebe och S. Zhu. Teori om travfel med kommutatorskalning. Fysisk granskning X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[36] B. Nachtergaele, Y. Ogata och R. Sims. Utbredning av korrelationer i kvantgittersystem. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6

[37] B. Nachtergaele och R. Sims. Lieb-Robinson gränsar i kvantfysiken för många kroppar. Samtida matematik 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529 / 10429

[38] S. Bravyi, MB Hastings och F. Verstraete. Lieb-robinson gränser och generering av korrelationer och topologisk kvantordning. Physical Review Letters 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401

[39] C.-F. Chen och A. Lucas. Operatörens tillväxtgränser från grafteori. Communications in Mathematical Physics 385, sid 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6

[40] EH Lieb och DW Robinson. Den ändliga grupphastigheten för kvantspinnsystem. Communications in Mathematical Physics 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779

[41] J. Haah, MB Hastings, R. Kothari och GH Low. Kvantalgoritm för simulering av realtidsutveckling av Hamiltonians gitter. 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 och P. Sarnak. Ramanujan-grafer. Combinatorica 8, 261-277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[43] B. Mohar. Isoperimetriska antal grafer. Journal of Combinatorial Theory, Series B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4

[44] AW Marcus, DA Spielman och N. Srivastava. Interlacing Familjer IV: Tvådelade Ramanujan-grafer av alla storlekar. I 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 och N. Srivastava. Interlacing Familjer IV: Tvådelade Ramanujan-grafer av alla storlekar. SIAM Journal on Computing 47, 2488–2509 (2018).
https://doi.org/ 10.1137/16M106176X

[46] C. Hall, D. Puder och WF Sawin. Ramanujan beläggningar av grafer. Advances in Mathematics 323, 367–410 (2018).
https: / / doi.org/ 10.1016 / j.aim.2017.10.042

[47] MX Goemans och DP Williamson. Förbättrade approximationsalgoritmer för maximal skärning och tillfredsställbarhetsproblem med semidefinite programmering. Journal of the ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

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

[49] MB Hastings. Kraften i adiabatisk kvantberäkning utan teckenproblem. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597

[50] A. Gilyén, MB Hastings och U. Vazirani. (Sub)Exponentiell fördel med adiabatisk kvantberäkning utan teckenproblem. I Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060

[51] R. Bhatia. Matrisanalys. Examentexter i matematik. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8

[52] R. Bhatia. Positiva bestämda matriser. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787

[53] BD McKay, NC Wormald och B. Wysocka. Korta cykler i slumpmässiga reguljära grafer. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819

[54] F. Kardoš, D. Král och J. Volec. Maximala kantskärningar i kubiska grafer med stor omkrets och i slumpmässiga kubiska grafer. Random Structures & Algorithms 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471

[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi och GB Sorkin. Random MAX SAT, random MAX CUT och deras fasövergångar. Random Structures and Algorithms 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015

[56] A. Dembo, A. Montanari och S. Sen. Extrema klipp av glesa slumpmässiga grafer. Annals of Probability 45, 1190–1217 (2017).
https://doi.org/ 10.1214/15-AOP1084

Citerad av

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé och Daniel Stilck França, "Begränsningar av variationskvantalgoritmer: en kvantoptimal transportmetod", arXiv: 2204.03455.

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-07-19 03:10:09). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2022-07-19 03:10:07).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.