1Laboratorul de Inteligență Artificială Cuantică (QuAIL), Centrul de Cercetare Ames NASA, Moffett Field, CA
2Institutul de Cercetare USRA pentru Informatică Avansată (RIACS), Mountain View, CA
3Berkeley Center for Quantum Information and Computation, Universitatea din California, Berkeley, CA
4Departamentul de Informatică, Universitatea din Chicago, Chicago, IL
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
Considerăm puterea algoritmilor locali pentru rezolvarea aproximativă a Max $k$XOR, o generalizare a două probleme de satisfacție a constrângerilor studiate anterior cu algoritmi clasici și cuantici (MaxCut și Max E3LIN2). În Max $k$XOR fiecare constrângere este XOR al exact $k$ variabile și un bit de paritate. Pe cazurile cu semne aleatoare (parități) sau fără clauze suprapuse și clauze $D+1$ per variabilă, calculăm fracția satisfăcătoare așteptată a QAOA depth-1 din Farhi și colab. [arXiv:1411.4028] și comparăm cu o generalizare a algoritmul de prag local de la Hirvonen et al [arXiv:1402.2543]. În special, algoritmul cuantic depășește algoritmul de prag pentru $k$$gt$$4$.
Pe de altă parte, evidențiem potențialele dificultăți pentru QAOA pentru a obține un avantaj cuantic computațional în această problemă. Mai întâi calculăm o limită superioară strânsă a fracției maxime satisfăcătoare din aproape toate cazurile mari aleatoare Max $k$XOR, calculând numeric densitatea de energie a stării fundamentale $P(k)$ a unui câmp mediu $k$-spin de sticlă [ arXiv:1606.02365]. Limita superioară crește cu $k$ mult mai rapid decât performanța ambilor algoritmi locali. De asemenea, identificăm un nou rezultat de obstrucție pentru circuitele cuantice de adâncime mică (inclusiv QAOA) când $k=3$, generalizând un rezultat al lui Bravyi și colab. [arXiv:1910.08980] când $k=2$. Presupunem că o obstrucție similară există pentru toți $k$.
Imagine prezentată: comparație între fracția satisfăcătoare (performanța) algoritmului de prag și QAOA depth-1 pentru Max kXOR la $D$ mari (și $D gg k$). Constanta $C_k$ pentru QAOA crește mai repede cu $k$ decât pentru algoritmul de prag. Deși algoritmul de prag depășește QAOA adâncime-1 pentru $k în {2,3,4}$, la toate celelalte k, QAOA este algoritmul mai bun.
[Conținutul încorporat]
► Date BibTeX
► Referințe
[1] A. Auffinger și W.-K. Chen. Despre proprietățile măsurilor Parisi. 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 și W.-K. Chen. Formula Parisi are un minimizator unic. Communications in Mathematical Physics, 335(3):1429–1444, noiembrie 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 și W.-K. Chen. Formula Parisi pentru energia stării fundamentale în modelul mixt p-spin. arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335
[4] AE Alaoui şi A. Montanari. Praguri algoritmice în ochelarii de spin de câmp mediu. arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari și M. Sellke. Optimizarea ochelarilor de spin cu câmp mediu. 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 și E. Tang. Obstacole la pregătirea stării și optimizarea variațională din protecția simetriei. arXiv preprint, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak și K. Marwaha. Algoritmi clasici și limitări cuantice pentru tăierea maximă pe grafice cu circumferință mare. 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. Depășirea atribuirii aleatorii pe probleme de satisfacție a constrângerilor de grad mărginit. arXiv:1505.03424.
arXiv: 1505.03424
[9] W.-K. Chen, D. Gamarnik, D. Panchenko și M. Rahman. Suboptimalitatea algoritmilor locali pentru o clasă de probleme max-cut. The Annals of Probability, 47(3), mai 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 și J. Shi. Limitări ale algoritmilor cuantici locali pe Max-k-XOR aleatoriu și dincolo. arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti si T. Rizzo. Analiza soluției de spargere a simetriei $infty$-replica a modelului Sherrington-Kirkpatrick. Physical Review E, 65(4), Apr 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 energetic aleatoriu: un model exact rezolvabil de sisteme dezordonate. Fiz. Rev. B, 24:2613–2626, septembrie 1981. doi:10.1103/PhysRevB.24.2613.
https: / / doi.org/ 10.1103 / PhysRevB.24.2613
[13] A. Dembo, A. Montanari și S. Sen. Tăieri extreme de grafice aleatorii rare. 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 și AW Harrow. Hamiltonieni locali ale căror stări fundamentale sunt greu de aproximat. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), oct 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 și S. Gutmann. Un algoritm de optimizare cuantică aproximativă. arXiv:1411.4028.
arXiv: 1411.4028
[16] E. Farhi, J. Goldstone și S. Gutmann. Un algoritm de optimizare cuantică aproximativ aplicat unei probleme de constrângere de apariție mărginită. arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik și S. Gutmann. Algoritmul de optimizare cuantică aproximativă trebuie să vadă întregul grafic: Un caz tipic. arXiv:2004.09002.
arXiv: 2004.09002
[18] J. Friedman. O dovadă a celei de-a doua conjecturi cu valori proprii a lui Alon și a problemelor conexe. arXiv:cs/0405020, doi:10.1090/memo/0910.
https:///doi.org/10.1090/memo/0910
arXiv: cs / 0405020
[19] S. Hadfield. Algoritmi cuantici pentru calcul științific și optimizare aproximativă. Universitatea Columbia, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Håstad. Câteva rezultate optime de inaproximabilitate. 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. Stări banale de energie scăzută pentru naveta hamiltonienilor și conjectura PCP cuantică. Quantum Information & Computation, 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. Algoritmi clasici și cuantici de aproximare a adâncimii. 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 și TH Hsieh. Simularea variațională eficientă a stărilor cuantice non-triviale. 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 și J. Suomela. Tăieri mari cu algoritmi locali pe grafice fără triunghi. The Electronic Journal of Combinatorics, paginile P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543
[25] CY-Y. Lin și Y. Zhu. Performanța QAOA pe cazuri tipice de probleme de satisfacție a constrângerilor cu grad mărginit. arXiv:1601.01744.
arXiv: 1601.01744
[26] K. Marwaha. Algoritmul local clasic MAX-CUT depășește $p=2$ QAOA pe graficele obișnuite cu circumferință mare. Quantum, 5:437, apr. 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. Optimizarea hamiltonianului Sherrington–Kirkpatrick. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https: / / doi.org/ 10.1109 / focs.2019.00087
arXiv: 1812.10897
[28] P. Obszarski şi A. Jastrzȩbski. Colorarea marginilor hipergrafelor 3-uniforme. Matematică aplicată discretă, 217:48–52, 2017, Optimizare combinatorie: teorie, calcul și aplicații. doi:10.1016/j.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009
[29] D. Pancenko. Introducere în modelul 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. Pancenko. Pe modelul $k$-sat cu un număr mare de clauze. arXiv:1608.06256, doi:10.1002/rsa.20748.
https:///doi.org/10.1002/rsa.20748
arXiv: 1608.06256
[31] G. Parisi. O secvență de soluții aproximate la modelul SK pentru ochelari spin. 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. Optimizare pe hipergrafe aleatoare rare și ochelari de rotație. 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 și I. Safro. Simetrii clasice și algoritmul de optimizare cuantică aproximativă. Quantum Information Processing, 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. Formula Parisi. 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 și EG Rieffel. Algoritm de optimizare cuantică aproximativă pentru maxcut: O vedere fermionică. Fiz. Rev. A, 97:022304, feb 2018. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998
Citat de
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga și Leo Zhou, „The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model”, arXiv: 2110.14206.
[2] Nicolas PD Sawaya, Albert T Schmitz și 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 și Vedran Dunjko, „Reinforcement Learning Assisted Recursive QAOA”, arXiv: 2207.06294.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-07-26 13:36:03). 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-26 13:36:00).
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.
