QuOne Lab, Phanous Research and Innovation Centre, Teheran, Iran
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Udviklingen af lokale Hamiltonianere på korte tider forventes at forblive lokale og dermed begrænset. I dette papir validerer vi denne intuition ved at bevise nogle begrænsninger på korttidsudviklinger af lokale tidsafhængige Hamiltonianere. Vi viser, at fordelingen af måleoutput af korttids (højst logaritmiske) udviklinger af lokale Hamiltonianere er $koncentreret$ og tilfredsstiller en $textit{isoperimetrisk ulighed}$. For at fremvise eksplicitte anvendelser af vores resultater studerer vi $M$$small{AX}$$C$$small{UT}$-problemet og konkluderer, at kvanteudglødning kræver mindst en kørselstid, der skaleres logaritmisk i problemstørrelsen til slog klassiske algoritmer på $M$$small{AX}$$C$$small{UT}$. For at etablere vores resultater beviser vi også en Lieb-Robinson-binding, der virker for tidsafhængige Hamiltonianere, som kan være af uafhængig interesse.
Udvalgt billede: Denne illustration viser sandsynlighedsfordelingen af Hamming-vægten af tre forskellige $n$-qubit-tilstande for $n=100$. Den centrerede fordeling i midten (blå) er den typiske fordeling for et produkts begyndelsestilstand (f.eks. $|+rangle^{otimes n}$). Fordelingen, der topper lige til højre (orange), repræsenterer fordelingen efter en kort tids udvikling af den begyndelsestilstand, der er beskrevet af sætning 2 i manuskriptet. Fordelingen, der har to toppe på hver side af spektret (grøn), er en tilnærmelse for GHZ-tilstanden. Dette viser, at GHZ-tilstanden ikke engang kan genereres ved en kortvarig kvanteudglødning.
Populært resumé
► BibTeX-data
► Referencer
[1] T. Kadowaki og H. Nishimori. Kvanteudglødning i den tværgående Ising-model. Physical Review E 58, 5355-5363 (1998).
https:///doi.org/10.1103/PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann og M. Sipser. Kvanteberegning ved adiabatisk evolution. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[3] T. Kato. Om kvantemekanikkens adiabatiske sætning. Journal of the Physical Society of Japan 5, 435-439 (1950).
https:///doi.org/10.1143/JPSJ.5.435
[4] M. Born og V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https:///doi.org/10.1007/BF01343193
[5] T. Albash og DA Lidar. Adiabatisk kvanteberegning. Anmeldelser af Modern Physics 90, 015002 (2018).
https:///doi.org/10.1103/RevModPhys.90.015002
[6] I. Hen og FM Spedalieri. Kvanteudglødning for begrænset optimering. Fysisk gennemgang anvendt 5, 034007 (2016).
https:///doi.org/10.1103/PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo og A. Blais. Kvanteudglødning med alt-til-alle forbundne ikke-lineære oscillatorer. Nature Communications 8, 15785 (2017).
https:///doi.org/10.1038/ncomms15785
[8] W. Lechner, P. Hauke og P. Zoller. En kvanteudglødningsarkitektur med alt-til-alle-forbindelse fra lokale interaktioner. Science Advances 1, e1500838 (2015).
https:///doi.org/10.1126/sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble og S. Kais. Kvanteudglødning for prime faktorisering. Scientific Reports 8, 17667 (2018).
https:///doi.org/10.1038/s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs og DA Lidar. Kvanteudglødning versus klassisk maskinlæring anvendt på et forenklet beregningsbiologiproblem. NPJ kvanteinformation 4, 1-10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] L. Stella, GE Santoro og E. Tosatti. Optimering ved quantum annealing: Lektioner fra simple cases. Fysisk gennemgang B 72, 014303 (2005).
https:///doi.org/10.1103/PhysRevB.72.014303
[12] O. Titiloye og A. Crispin. Kvanteudglødning af graffarveproblemet. Diskret Optimering 8, 376-384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar og M. Spiropulu. Løsning af et Higgs-optimeringsproblem med kvanteudglødning til maskinlæring. Nature 550, 375-379 (2017).
https:///doi.org/10.1038/nature24047
[14] KL Pudenz, T. Albash og D. A Lidar. Kvanteudglødningskorrektion for tilfældige Ising-problemer. Fysisk anmeldelse A 91, 042302 (2015).
https:///doi.org/10.1103/PhysRevA.91.042302
[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose og A. Aspuru-Guzik. At finde lavenergikonformationer af gitterproteinmodeller ved kvante-annealing. Scientific reports 2, 571 (2012).
https:///doi.org/10.1038/srep00571
[16] KL Pudenz, T. Albash og D. A Lidar. Fejlkorrigeret kvanteudglødning med hundredvis af qubits. Naturformidling 5, 1–10 (2014).
https:///doi.org/10.1038/ncomms4243
[17] R. Martoňák, GE Santoro og E. Tosatti. Kvanteudglødning af problemet med den rejsende sælger. Fysisk gennemgang E 70, 057701 (2004).
https:///doi.org/10.1103/PhysRevE.70.057701
[18] SH Adachi og MP Henderson. Anvendelse af quantum annealing til træning af dybe neurale netværk. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[19] M.W. Johnson et al. Kvanteudglødning med fremstillede spins. Nature 473, 194-198 (2011).
https:///doi.org/10.1038/nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor og DA Lidar. Eksperimentel signatur af programmerbar kvanteudglødning. Naturformidling 4, 1–8 (2013).
https:///doi.org/10.1038/ncomms3067
[21] AD King, et al. Kohærent kvanteudglødning i en programmerbar 2000-qubit Ising-kæde. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[22] B. Foxen, et al. Demonstrering af et kontinuerligt sæt af to-qubit-porte for kortsigtede kvantealgoritmer. Physical Review Letters 125, 120504 (2020).
https:///doi.org/10.1103/PhysRevLett.125.120504
[23] K. Wright, et al. Benchmarking af en 11-qubit kvantecomputer. Naturformidling 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson og DA Lidar. Udsigter til kvanteforbedring med diabatisk kvanteudglødning. Nature Reviews Physics 3, 466-489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] E. Farhi, J. Goldstone og S. Gutmann. En omtrentlig kvanteoptimeringsalgoritme. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[26] E. Farhi, D. Gamarnik og S. Gutmann. Quantum Approximate Optimization Algorithm skal se hele grafen: Worst Case-eksempler. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[27] E. Farhi, D. Gamarnik og S. Gutmann. Quantum Approximate Optimization Algorithm skal se hele grafen: Et typisk tilfælde. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig og E. Tang. Forhindringer for variationskvanteoptimering fra symmetribeskyttelse. Physical Review Letters 125, 260505 (2020).
https:///doi.org/10.1103/PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset og R. Movassagh. Klassiske algoritmer for kvantemiddelværdier. Nature Physics 17, 337-341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig og E. Tang. Hybride kvanteklassiske algoritmer til omtrentlig graffarvning. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] L. Eldar og AW Harrow. Lokale Hamiltonianere, hvis grundstater er svære at tilnærme. I 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 og AV Gorshkov. Optimale protokoller i Quantum Annealing og Quantum Approximate Optimization Algoritme Problemer. 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 og AV Gorshkov. Opførsel af analoge kvantealgoritmer. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro og DA Lidar. Optimal kontrol til kvanteoptimering af lukkede og åbne systemer. Fysisk gennemgang anvendt 16, 054023 (2021).
https:///doi.org/10.1103/PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe og S. Zhu. Teori om travfejl med kommutatorskalering. Fysisk gennemgang X 11, 011020 (2021).
https:///doi.org/10.1103/PhysRevX.11.011020
[36] B. Nachtergaele, Y. Ogata og R. Sims. Udbredelse af korrelationer i kvantegittersystemer. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] B. Nachtergaele og R. Sims. Lieb-Robinson sætter grænser i kvante mange-legeme fysik. Contemporary Mathematics 529, 141-176 (2010).
https:///doi.org/10.1090/conm/529/10429
[38] S. Bravyi, MB Hastings og F. Verstraete. Lieb-robinson-grænser og generering af korrelationer og topologisk kvanteorden. Physical Review Letters 97, 050401 (2006).
https:///doi.org/10.1103/PhysRevLett.97.050401
[39] C.-F. Chen og A. Lucas. Operatør vækstgrænser fra grafteori. Communications in Mathematical Physics 385, side 1273-1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] EH Lieb og DW Robinson. Den endelige gruppehastighed af kvantespinsystemer. Communications in Mathematical Physics 28, 251-257 (1972).
https:///doi.org/10.1007/BF01645779
[41] J. Haah, MB Hastings, R. Kothari og GH Low. Kvantealgoritme til simulering af realtidsudvikling af 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 og P. Sarnak. Ramanujan-grafer. Combinatorica 8, 261-277 (1988).
https:///doi.org/10.1007/BF02126799
[43] B. Mohar. Isoperimetriske 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 og N. Srivastava. Sammenflettede familier IV: Todelte Ramanujan-grafer i alle størrelser. 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 og N. Srivastava. Sammenflettede familier IV: Todelte Ramanujan-grafer i alle størrelser. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X
[46] C. Hall, D. Puder og WF Sawin. Ramanujan belægninger af grafer. Advances in Mathematics 323, 367–410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
[47] MX Goemans og DP Williamson. Forbedrede tilnærmelsesalgoritmer til maksimal snit- og tilfredshedsproblemer ved brug af semidefinite programmering. Journal of the ACM 42, 1115-1145 (1995).
https:///doi.org/10.1145/227683.227684
[48] RD Somma, D. Nagaj og M. Kieferová. Quantum Speedup ved Quantum Annealing. Physical Review Letters 109, 050501 (2012).
https:///doi.org/10.1103/PhysRevLett.109.050501
[49] MB Hastings. Styrken ved adiabatisk kvanteberegning uden tegnproblem. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings og U. Vazirani. (Sub)Eksponentiel fordel ved adiabatisk kvanteberegning uden tegnproblem. 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. Matrix analyse. Kandidattekster i matematik. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] R. Bhatia. Positive bestemte matricer. Princeton University Press, (2007).
https:///doi.org/10.1515/9781400827787
[53] BD McKay, NC Wormald og B. Wysocka. Korte cyklusser i tilfældige regulære grafer. The Electronic Journal of Combinatorics 11, 1-12 (2004).
https:///doi.org/10.37236/1819
[54] F. Kardoš, D. Král og J. Volec. Maksimale kantskæringer i kubiske grafer med stor omkreds og i tilfældige kubiske grafer. Random Structures & Algorithms 41, 506–520 (2012).
https:///doi.org/10.1002/rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi og GB Sorkin. Random MAX SAT, random MAX CUT og deres faseovergange. Random Structures and Algorithms 24, 502-545 (2004).
https:///doi.org/10.1002/rsa.20015
[56] A. Dembo, A. Montanari og S. Sen. Ekstreme udskæringer af sparsomme tilfældige grafer. Annals of Probability 45, 1190-1217 (2017).
https:///doi.org/10.1214/15-AOP1084
Citeret af
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé og Daniel Stilck França, "Begrænsninger af variationskvantealgoritmer: en kvanteoptimal transporttilgang", arXiv: 2204.03455.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-07-19 03:10: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 2022-07-19 03:10:07).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
