Laboratorul QuOne, Centrul de cercetare și inovare Phanous, Teheran, Iran
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
Evoluțiile hamiltonienilor locali în timp scurt sunt de așteptat să rămână locale și, prin urmare, limitate. În această lucrare, validăm această intuiție prin demonstrarea unor limitări ale evoluțiilor de scurtă durată ale hamiltonienilor locali dependenți de timp. Arătăm că distribuția rezultatelor de măsurare a evoluțiilor de scurtă durată (cel mult logaritmice) ale hamiltonienilor locali sunt $concentrate$ și satisfac o $textit{inegalitate izoperimetrică}$. Pentru a prezenta aplicații explicite ale rezultatelor noastre, studiem problema $M$$small{AX}$$C$$small{UT}$ și concluzionăm că recoacere cuantică are nevoie de cel puțin un timp de rulare care se scalează logaritmic în dimensiunea problemei la bate algoritmii clasici pe $M$$small{AX}$$C$$small{UT}$. Pentru a stabili rezultatele noastre, demonstrăm, de asemenea, o legătură Lieb-Robinson care funcționează pentru Hamiltonieni dependenți de timp, care ar putea fi de interes independent.
Imagine prezentată: această ilustrație ilustrează distribuția probabilității ponderii Hamming a trei stări diferite de $n$-qubit pentru $n=100$. Distribuția centrată în mijloc (albastru) este distribuția tipică pentru o stare inițială a produsului (de exemplu, $|+rangle^{otimes n}$). Distribuția care are vârful la dreapta (portocaliu) reprezintă distribuția după o scurtă evoluție a stării inițiale descrise de teorema 2 a manuscrisului. Distribuția care are două vârfuri de fiecare parte a spectrului (verde) este o aproximare pentru starea GHZ. Acest lucru arată că starea GHZ nu poate fi generată nici măcar aproximativ printr-o recoacere cuantică de scurtă durată.
Rezumat popular
► Date BibTeX
► Referințe
[1] T. Kadowaki şi H. Nishimori. Recoacere cuantică în modelul Ising transversal. Physical Review E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann și M. Sipser. Calcul cuantic prin evoluție adiabatică. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[3] T. Kato. Despre teorema adiabatică a mecanicii cuantice. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
[4] M. Born şi V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[5] T. Albash și DA Lidar. Calcul cuantic adiabatic. Recenzii de Fizica Modernă 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[6] I. Hen şi FM Spedalieri. Recoacere cuantică pentru optimizare constrânsă. Physical Review Applied 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo și A. Blais. Recoacere cuantică cu oscilatoare neliniare conectate all-to-all. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
[8] W. Lechner, P. Hauke și P. Zoller. O arhitectură de recoacere cuantică cu conectivitate totală din interacțiuni locale. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble și S. Kais. Recoacere cuantică pentru factorizare primă. Scientific Reports 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs și DA Lidar. Recoacere cuantică versus învățarea automată clasică aplicată la o problemă simplificată de biologie computațională. Informații cuantice NPJ 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] L. Stella, GE Santoro și E. Tosatti. Optimizare prin recoacere cuantică: Lecții din cazuri simple. Physical Review B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
[12] O. Titiloye şi A. Crispin. Recoacere cuantică a problemei de colorare a graficului. Optimizare discretă 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar și M. Spiropulu. Rezolvarea unei probleme de optimizare Higgs cu recoacere cuantică pentru învățarea automată. Nature 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] KL Pudenz, T. Albash și D. A Lidar. Corecție de recoacere cuantică pentru probleme aleatorii Ising. 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 și A. Aspuru-Guzik. Găsirea conformațiilor cu energie scăzută ale modelelor de proteine latice prin recoacere cuantică. Rapoarte științifice 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[16] KL Pudenz, T. Albash și D. A Lidar. Recoacere cuantică corectată cu erori cu sute de qubiți. Nature communications 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[17] R. Martoňák, GE Santoro și E. Tosatti. Recoacere cuantică a problemei vânzătorului ambulant. Physical Review E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] SH Adachi și MP Henderson. Aplicarea recoacirii cuantice la antrenamentul rețelelor neuronale profunde. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[19] M. W Johnson, şi colab. Recoacere cuantică cu spinuri fabricate. Natura 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Cancelar și DA Lidar. Semnătura experimentală a recoacerii cuantice programabile. Nature communications 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[21] AD King și colab. Recoacere cuantică coerentă într-un lanț Ising programabil de 2000 de qubiți. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[22] B. Foxen, şi colab. Demonstrarea unui set continuu de porți de doi qubiți pentru algoritmi cuantici pe termen apropiat. Physical Review Letters 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] K. Wright și colab. Evaluarea comparativă a unui computer cuantic de 11 qubiți. Nature communications 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson și DA Lidar. Perspective pentru îmbunătățirea cuantică cu recoacere cuantică diabatică. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] E. Farhi, J. Goldstone și S. Gutmann. Un algoritm de optimizare cuantică aproximativă. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[26] E. Farhi, D. Gamarnik și S. Gutmann. Algoritmul de optimizare aproximativă cuantică trebuie să vadă întregul grafic: exemple de caz cel mai rău. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[27] E. Farhi, D. Gamarnik și S. Gutmann. Algoritmul de optimizare aproximativă cuantică trebuie să vadă întregul grafic: un caz tipic. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig și E. Tang. Obstacole în calea optimizării cuantice variaționale de la protecția simetriei. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset și R. Movassagh. Algoritmi clasici pentru valori medii cuantice. Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig și E. Tang. Algoritmi hibrizi cuantico-clasici pentru colorarea aproximativă a graficelor. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] L. Eldar și AW Harrow. Hamiltonieni locali ale căror state de bază sunt greu de aproximat. În 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 și AV Gorshkov. Protocoale optime în recoacerea cuantică și problemele algoritmilor de optimizare aproximativă cuantică. 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 și AV Gorshkov. Comportamentul algoritmilor cuantici analogici. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro, and DA Lidar. Control optim pentru optimizarea cuantică a sistemelor închise și deschise. Physical Review Applied 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe și S. Zhu. Teoria erorii Trotter cu scalarea comutatorului. Physical Review X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[36] B. Nachtergaele, Y. Ogata și R. Sims. Propagarea corelațiilor în sisteme cu rețele cuantice. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] B. Nachtergaele şi R. Sims. Limitele Lieb-Robinson în fizica cuantică a mai multor corpuri. Matematică contemporană 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
[38] S. Bravyi, MB Hastings și F. Verstraete. Limitele Lieb-robinson și generarea de corelații și ordine cuantică topologică. Physical Review Letters 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[39] C.-F. Chen şi A. Lucas. Limitele de creștere ale operatorului din teoria grafurilor. Communications in Mathematical Physics 385, paginile 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] EH Lieb și DW Robinson. Viteza de grup finit a sistemelor de spin cuantic. Communications in Mathematical Physics 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari și GH Low. Algoritm cuantic pentru simularea evoluției în timp real a hamiltonienilor latice. 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 și P. Sarnak. Grafice Ramanujan. Combinatorică 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[43] B. Mohar. Numerele izoperimetrice ale graficelor. Journal of Combinatorial Theory, Seria B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[44] AW Marcus, DA Spielman și N. Srivastava. Interlacing Families IV: Grafice Ramanujan bipartite de toate dimensiunile. În 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 și N. Srivastava. Interlacing Families IV: Grafice Ramanujan bipartite de toate dimensiunile. SIAM Journal on Computing 47, 2488–2509 (2018).
https: / / doi.org/ 10.1137 / 16M106176X
[46] C. Hall, D. Puder și WF Sawin. Ramanujan acoperiri de grafice. Advances in Mathematics 323, 367–410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
[47] MX Goemans și DP Williamson. Algoritmi de aproximare îmbunătățiți pentru probleme de tăiere maximă și de satisfacție folosind programarea semidefinită. Jurnalul ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj și M. Kieferová. Accelerare cuantică prin recucere cuantică. Physical Review Letters 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[49] MB Hastings. Puterea calculului cuantic adiabatic fără probleme fără semn. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings și U. Vazirani. Avantaj (sub)exponențial al calculului cuantic adiabatic fără probleme de semn. În Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] R. Bhatia. Analiza matriceală. Texte de absolvent în matematică. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] R. Bhatia. Matrici definite pozitive. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald și B. Wysocka. Cicluri scurte în grafice regulate aleatorii. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
[54] F. Kardoš, D. Král și J. Volec. Tăieri maxime de margine în grafice cubice cu circumferință mare și în grafice cubice aleatorii. Random Structures & Algorithms 41, 506–520 (2012).
https:///doi.org/10.1002/rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi și GB Sorkin. Random MAX SAT, aleator MAX CUT și tranzițiile lor de fază. Structuri aleatoare și algoritmi 24, 502–545 (2004).
https:///doi.org/10.1002/rsa.20015
[56] A. Dembo, A. Montanari și S. Sen. Tăieri extreme de grafice aleatorii rare. Analele probabilității 45, 1190–1217 (2017).
https: / / doi.org/ 10.1214 / 15-AOP1084
Citat de
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé și Daniel Stilck França, „Limitații ale algoritmilor cuantici variaționali: o abordare cuantică optimă a transportului”, arXiv: 2204.03455.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-07-19 03:10:09). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.
On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2022-07-19 03:10:07).
Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.
