1Laboratorij za kvantno umetno inteligenco (QuAIL), NASA Ames Research Center, Moffett Field, CA
2USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA
3Berkeley Center for Quantum Information and Computation, Univerza v Kaliforniji, Berkeley, CA
4Oddelek za računalništvo, Univerza v Chicagu, Chicago, IL
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Upoštevamo moč lokalnih algoritmov za približno reševanje Max $k$XOR, posplošitev dveh problemov zadovoljevanja omejitev, ki smo ju predhodno preučevali s klasičnimi in kvantnimi algoritmi (MaxCut in Max E3LIN2). V Max $k$XOR je vsaka omejitev XOR natančno $k$ spremenljivk in paritetnega bita. Za primere z naključnimi predznaki (paritete) ali brez prekrivajočih se klavzul in $D+1$ klavzul na spremenljivko izračunamo pričakovani zadovoljivi delež QAOA globine 1 iz Farhija et al [arXiv:1411.4028] in primerjamo s posplošitvijo algoritem lokalnega praga Hirvonen et al [arXiv:1402.2543]. Predvsem kvantni algoritem prekaša algoritem praga za $k$$gt$$4$.
Po drugi strani poudarjamo morebitne težave za QAOA pri doseganju računalniške kvantne prednosti pri tem problemu. Najprej izračunamo ozko zgornjo mejo največjega zadovoljivega deleža skoraj vseh velikih naključnih pravilnih primerkov Max $k$XOR z numeričnim izračunom gostote energije osnovnega stanja $P(k)$ stekla s $k$-spinom srednjega polja [ arXiv:1606.02365]. Zgornja meja raste z $k$ veliko hitreje kot zmogljivost obeh enolokalnih algoritmov. Identificiramo tudi nov rezultat obstrukcije za nizkoglobinska kvantna vezja (vključno s QAOA), ko je $k=3$, pri čemer posplošimo rezultat Bravyi et al [arXiv:1910.08980], ko $k=2$. Domnevamo, da podobna ovira obstaja za vse $k$.
Predstavljena slika: Primerjava zadovoljivega deleža (zmogljivosti) algoritma praga in QAOA globine 1 za Max kXOR pri velikem $D$ (in $D gg k$). Konstanta $C_k$ za QAOA raste hitreje z $k$ kot za algoritem praga. Čeprav je algoritem praga boljši od QAOA globine 1 za $k v {2,3,4}$, je pri vseh drugih k QAOA boljši algoritem.
[Vgrajeni vsebina]
► BibTeX podatki
► Reference
[1] A. Auffinger in W.-K. Chen. O lastnostih pariških mer. arXiv:1303.3573, doi:10.1007/s00440-014-0563-y.
https: / / doi.org/ 10.1007 / s00440-014-0563-y
arXiv: 1303.3573
[2] A. Auffinger in W.-K. Chen. Formula Parisi ima edinstven minimizator. Communications in Mathematical Physics, 335(3):1429–1444, november 2014. arXiv:1402.5132, doi:10.1007/s00220-014-2254-z.
https: / / doi.org/ 10.1007 / s00220-014-2254-z
arXiv: 1402.5132
[3] A. Auffinger in W.-K. Chen. Parisijeva formula za energijo osnovnega stanja v modelu mešanega p-spina. arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335
[4] AE Alaoui in A. Montanari. Algoritemski pragovi v vrtilnih očalih srednjega polja. arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari in M. Sellke. Optimizacija vrtilnih stekel srednjega polja. arXiv:2001.00904, doi:10.1214/21-aop1519.
https:///doi.org/10.1214/21-aop1519
arXiv: 2001.00904
[6] S. Bravyi, A. Kliesch, R. Koenig in E. Tang. Ovire za pripravo stanja in variacijsko optimizacijo zaradi zaščite simetrije. arXiv prednatis, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak in K. Marwaha. Klasični algoritmi in kvantne omejitve za največji rez na grafih z visokim obsegom. arXiv:2106.05900, doi:10.4230/LIPIcs.ITCS.2022.14.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14
arXiv: 2106.05900
[8] B. Barak, A. Moitra, R. O’Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. arXiv:1505.03424.
arXiv: 1505.03424
[9] W.-K. Chen, D. Gamarnik, D. Panchenko in M. Rahman. Suboptimalnost lokalnih algoritmov za razred problemov max-cut. The Annals of Probability, 47(3), maj 2019. arXiv:1707.05386, doi:10.1214/18-aop1291.
https:///doi.org/10.1214/18-aop1291
arXiv: 1707.05386
[10] C.-N. Chou, PJ Love, JS Sandhu in J. Shi. Omejitve lokalnih kvantnih algoritmov na Random Max-k-XOR in več. arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti in T. Rizzo. Analiza $infty$-replike rešitve lomljenja simetrije Sherrington-Kirkpatrickovega modela. Physical Review E, 65(4), april 2002. arXiv:cond-mat/0111037, doi:10.1103/physreve.65.046137.
https: / / doi.org/ 10.1103 / physreve.65.046137
arXiv: cond-mat / 0111037
[12] B. Derrida. Model naključne energije: Natančno rešljiv model neurejenih sistemov. Phys. Rev. B, 24:2613–2626, september 1981. doi:10.1103/PhysRevB.24.2613.
https: / / doi.org/ 10.1103 / PhysRevB.24.2613
[13] A. Dembo, A. Montanari in S. Sen. Ekstremni rezi redkih naključnih grafov. The Annals of Probability, 45(2):1190–1217, 2017. arXiv:1503.03923, doi:10.1214/15-aop1084.
https:///doi.org/10.1214/15-aop1084
arXiv: 1503.03923
[14] L. Eldar in AW Harrow. Lokalni hamiltonci, katerih osnovna stanja je težko približno oceniti. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), oktober 2017. arXiv:1510.02082, doi:10.1109/focs.2017.46.
https: / / doi.org/ 10.1109 / focs.2017.46
arXiv: 1510.02082
[15] E. Farhi, J. Goldstone in S. Gutmann. Algoritem kvantne približne optimizacije. arXiv:1411.4028.
arXiv: 1411.4028
[16] E. Farhi, J. Goldstone in S. Gutmann. Algoritem kvantne približne optimizacije, uporabljen pri problemu omejitve omejenega pojavljanja. arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik in S. Gutmann. Algoritem kvantne približne optimizacije mora videti celoten graf: tipičen primer. arXiv:2004.09002.
arXiv: 2004.09002
[18] J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. arXiv:cs/0405020, doi:10.1090/memo/0910.
https:///doi.org/10.1090/memo/0910
arXiv: cs / 0405020
[19] S. Hadfield. Kvantni algoritmi za znanstveno računalništvo in približno optimizacijo. Univerza Columbia, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Håstad. Nekaj optimalnih rezultatov nepribližljivosti. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/258533.258536, URL http://www.cs.umd.edu/gasarch/BLOGPAPERS/max3satl. pdf.
https: / / doi.org/ 10.1145 / 258533.258536
http:///www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf
[21] MB Hastings. Trivialna nizkoenergijska stanja za komutirane hamiltonije in domneva o kvantnem PCP. Kvantne informacije in računanje, 13, 2013. arXiv:1201.3387, doi:10.26421/qic13.5-6-3.
https: / / doi.org/ 10.26421 / qic13.5-6-3
arXiv: 1201.3387
[22] MB Hastings. Klasični in kvantno omejeni globinski aproksimacijski algoritmi. arXiv:1905.07047, doi:10.26421/qic19.13-14-3.
https: / / doi.org/ 10.26421 / qic19.13-14-3
arXiv: 1905.07047
[23] WW Ho in TH Hsieh. Učinkovita variacijska simulacija netrivialnih kvantnih stanj. arXiv:1803.00026, doi:10.21468/scipostphys.6.3.029.
https: / / doi.org/ 10.21468 / scipostphys.6.3.029
arXiv: 1803.00026
[24] J. Hirvonen, J. Rybicki, S. Schmid in J. Suomela. Veliki rezi z lokalnimi algoritmi na grafih brez trikotnikov. The Electronic Journal of Combinatorics, strani P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543
[25] CY-Y. Lin in Y. Zhu. Učinkovitost QAOA na tipičnih primerih težav z zadovoljevanjem omejitev z omejeno stopnjo. arXiv:1601.01744.
arXiv: 1601.01744
[26] K. Marwaha. Lokalni klasični algoritem MAX-CUT prekaša $p=2$ QAOA na običajnih grafih z velikim obsegom. Quantum, 5:437, april 2021. arXiv:2101.05513, doi:10.22331/q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437
arXiv: 2101.05513
[27] A. Montanari. Optimizacija Sherrington–Kirkpatrickovega Hamiltoniana. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https: / / doi.org/ 10.1109 / focs.2019.00087
arXiv: 1812.10897
[28] P. Obszarski in A. Jastrzȩbski. Barvanje robov 3-uniformnih hipergrafov. Diskretna uporabna matematika, 217:48–52, 2017, Kombinatorna optimizacija: teorija, računanje in aplikacije. doi:10.1016/j.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009
[29] D. Pančenko. Uvod v model SK. arXiv:1412.0170, doi:10.4310/cdm.2014.v2014.n1.a4.
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
arXiv: 1412.0170
[30] D. Pančenko. Na modelu $k$-sat z velikim številom klavzul. arXiv:1608.06256, doi:10.1002/rsa.20748.
https: / / doi.org/ 10.1002 / rsa.20748
arXiv: 1608.06256
[31] G. Parisi. Zaporedje aproksimiranih rešitev modela SK za spin očala. Journal of Physics A: Mathematical and General, 13(4):L115–L121, apr. 1980. doi:10.1088/0305-4470/13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009
[32] S. Sen. Optimizacija na redkih naključnih hipergrafih in spin kozarcih. arXiv:1606.02365, doi:10.1002/rsa.20774.
https: / / doi.org/ 10.1002 / rsa.20774
arXiv: 1606.02365
[33] R. Shaydulin, S. Hadfield, T. Hogg in I. Safro. Klasične simetrije in algoritem kvantne približne optimizacije. Kvantna obdelava informacij, 20(11):1–28, 2021. arXiv:2012.04713, doi:10.1007/s11128-021-03298-4.
https://doi.org/10.1007/s11128-021-03298-4
arXiv: 2012.04713
[34] M. Talagrand. Pariška formula. Annals of Mathematics, 163:221–263, 2006. doi:10.4007/annals.2006.163.221, URL https://annals.math.princeton.edu/wp-content/uploads/annals-v163 -n1-p04.pdf.
https:///doi.org/10.4007/annals.2006.163.221
https:///annals.math.princeton.edu/wp-content/uploads/annals-v163-n1-p04.pdf
[35] Z. Wang, S. Hadfield, Z. Jiang in EG Rieffel. Kvantni približni optimizacijski algoritem za maxcut: fermionski pogled. Phys. Rev. A, 97:022304, februar 2018. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998
Navedel
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga in Leo Zhou, »Algoritem kvantne približne optimizacije pri veliki globini za MaxCut na regularnih grafih velikega obsega in Sherrington-Kirkpatrickov model«, arXiv: 2110.14206.
[2] Nicolas PD Sawaya, Albert T Schmitz, and Stuart Hadfield, “Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems”, arXiv: 2203.14432.
[3] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, “Reinforcement Learning Assisted Recursive QAOA”, arXiv: 2207.06294.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-07-26 13:36:03). 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-26 13:36:00).
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.
