1Quantum Artificial Intelligence Laboratory (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, Universiteit van Californiรซ, Berkeley, CA
4Afdeling Computerwetenschappen, Universiteit van Chicago, Chicago, IL
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
We beschouwen de kracht van lokale algoritmen voor het ongeveer oplossen van Max $k$XOR, een generalisatie van twee constraint-tevredenheidsproblemen die eerder zijn bestudeerd met klassieke en kwantumalgoritmen (MaxCut en Max E3LIN2). In Max $k$XOR is elke beperking de XOR van exact $k$ variabelen en een pariteitsbit. Op instanties met willekeurige tekens (pariteiten) of geen overlappende clausules en $D+1$-clausules per variabele, berekenen we de verwachte bevredigende fractie van de depth-1 QAOA van Farhi et al [arXiv:1411.4028] en vergelijken met een generalisatie van het lokale drempelalgoritme van Hirvonen et al [arXiv:1402.2543]. Met name presteert het kwantumalgoritme beter dan het drempelalgoritme voor $k$$gt$$4$.
Aan de andere kant benadrukken we mogelijke moeilijkheden voor de QAOA om een โโrekenkundig kwantumvoordeel op dit probleem te behalen. We berekenen eerst een strakke bovengrens van de maximaal bevredigende fractie van bijna alle grote willekeurige reguliere Max $k$XOR instanties door numeriek de grondtoestand energiedichtheid $P(k)$ van een mean-field $k$-spin glas [ arXiv:1606.02365]. De bovengrens groeit met $k$ veel sneller dan de prestaties van beide รฉรฉn-lokale algoritmen. We identificeren ook een nieuw obstructieresultaat voor kwantumcircuits met een lage diepte (inclusief de QAOA) wanneer $k=3$, waarbij we een resultaat van Bravyi et al [arXiv:1910.08980] generaliseren wanneer $k=2$. We veronderstellen dat er voor alle $k$ een soortgelijke belemmering bestaat.
Uitgelichte afbeelding: vergelijking van de bevredigende fractie (prestaties) van het drempelalgoritme en de depth-1 QAOA voor Max kXOR bij grote $D$ (en $D gg k$). De constante $C_k$ voor QAOA groeit sneller met $k$ dan voor het drempelalgoritme. Hoewel het drempelalgoritme beter presteert dan de depth-1 QAOA voor $k in {2,3,4}$, is de QAOA bij alle andere k het betere algoritme.
[Ingesloten inhoud]
โบ BibTeX-gegevens
โบ Referenties
[1] A. Auffinger en W.-K. Chen. Over eigenschappen van Parijse maatregelen. 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 en W.-K. Chen. De Parisi-formule heeft een unieke minimalizer. Communications in Mathematical Physics, 335(3):1429โ1444, nov 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 en W.-K. Chen. Parisi-formule voor de energie in de grondtoestand in het gemengde p-spin-model. arXiv:1606.05335, doi:10.1214/โ16-aop1173.
https://โ/โdoi.org/โ10.1214/โ16-aop1173
arXiv: 1606.05335
[4] AE Alaoui en A. Montanari. Algoritmische drempels in gemiddelde veldspinglazen. arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari en M. Sellke. Optimalisatie van mean-field spin-brillen. 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 en E. Tang. Obstakels voor toestandsvoorbereiding en variatie-optimalisatie door symmetriebescherming. arXiv voordruk, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak en K. Marwaha. Klassieke algoritmen en kwantumbeperkingen voor maximale verlaging van grafieken met een hoge omtrek. 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. Het verslaan van de willekeurige opdracht op constraint-tevredenheidsproblemen van begrensde graad. arXiv:1505.03424.
arXiv: 1505.03424
[9] W.-K. Chen, D. Gamarnik, D. Panchenko en M. Rahman. Suboptimaliteit van lokale algoritmen voor een klasse van max-cut problemen. The Annals of Probability, 47(3), mei 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 en J. Shi. Beperkingen van lokale kwantumalgoritmen op willekeurige Max-k-XOR en hoger. arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti en T. Rizzo. Analyse van de $infty$-replica symmetriebrekende oplossing van het Sherrington-Kirkpatrick-model. 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. Willekeurig-energiemodel: een exact oplosbaar model van ongeordende systemen. Fysiek. 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 en S. Sen. Extremale sneden van schaarse willekeurige grafieken. 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 en AW Harrow. Lokale Hamiltonianen waarvan de grondtoestanden moeilijk te benaderen zijn. 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 en S. Gutmann. Een kwantumbenaderend optimalisatie-algoritme. arXiv:1411.4028.
arXiv: 1411.4028
[16] E. Farhi, J. Goldstone en S. Gutmann. Een kwantumbenaderend optimalisatiealgoritme toegepast op een beperkingsprobleem met begrensd voorkomen. arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik en S. Gutmann. Het kwantumbenaderende algoritme voor optimalisatie moet de hele grafiek zien: een typisch geval. arXiv:2004.09002.
arXiv: 2004.09002
[18] J Friedman. Een bewijs van Alons tweede eigenwaardevermoeden en gerelateerde problemen. arXiv:cs/โ0405020, doi:10.1090/โmemo/โ0910.
https://โ/โdoi.org/โ10.1090/โmemo/โ0910
arXiv: cs / 0405020
[19] S Hadfield. Kwantumalgoritmen voor wetenschappelijke berekeningen en geschatte optimalisatie. Universiteit van Columbia, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Hรฅstad. Enkele optimale onbenaderbaarheidsresultaten. 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. Triviale lage energietoestanden voor pendelende Hamiltonianen, en het kwantum PCP-vermoeden. Quantuminformatie en berekeningen, 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. Klassieke en kwantumbegrensde algoritmen voor dieptebenadering. 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 en TH Hsieh. Efficiรซnte variatiesimulatie van niet-triviale kwantumtoestanden. 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 en J. Suomela. Grote bezuinigingen met lokale algoritmen op driehoeksvrije grafieken. The Electronic Journal of Combinatorics, pagina's P4โ21, 2017. arXiv:1402.2543, doi:10.37236/โ6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543
[25] CY-J. Lin en Y. Zhu. Prestaties van QAOA op typische gevallen van constraint-tevredenheidsproblemen met beperkte mate. arXiv:1601.01744.
arXiv: 1601.01744
[26] K. Marwaha. Het lokale klassieke MAX-CUT-algoritme presteert beter dan $p=2$ QAOA op reguliere grafieken met een hoge omtrek. 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. Optimalisatie van de Sherrington-Kirkpatrick Hamiltoniaan. arXiv:1812.10897, doi:10.1109/โfocs.2019.00087.
https: / / doi.org/ 10.1109 / focs.2019.00087
arXiv: 1812.10897
[28] P. Obszarski en A. Jastrzศฉbski. Randkleuring van 3-uniforme hypergrafen. Discrete toegepaste wiskunde, 217:48โ52, 2017, Combinatorische optimalisatie: theorie, berekening en toepassingen. doi:10.1016/โj.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009
[29] D. Pantsjenko. Inleiding tot het SK-model. 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. Pantsjenko. Op het $k$-sat-model met een groot aantal clausules. arXiv:1608.06256, doi:10.1002/โrsa.20748.
https: / / doi.org/ 10.1002 / rsa.20748
arXiv: 1608.06256
[31] G. Parijs. Een reeks benaderde oplossingen voor het SK-model voor spinbrillen. Journal of Physics A: Mathematical and General, 13(4):L115โL121, april 1980. doi:10.1088/โ0305-4470/โ13/โ4/โ009.
https:/โ/โdoi.org/โ10.1088/โ0305-4470/โ13/โ4/โ009
[32] S. Sen. Optimalisatie op schaarse willekeurige hypergrafieรซn en spinbrillen. 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 en I. Safro. Klassieke symmetrieรซn en het quantum benaderende optimalisatie-algoritme. Quantuminformatieverwerking, 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. De Parisi-formule. 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 en EG Rieffel. Quantum benaderend optimalisatie-algoritme voor maxcut: een fermionische weergave. Fysiek. Rev. A, 97:022304, februari 2018. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998
Geciteerd door
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga en 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 en Stuart Hadfield, "Codering van compromissen en ontwerptoolkits in kwantumalgoritmen voor discrete optimalisatie: kleuren, routering, planning en andere problemen", arXiv: 2203.14432.
[3] Yash J. Patel, Sofiene Jerbi, Thomas Bรคck en Vedran Dunjko, "Reinforcement Learning Assisted Recursive QAOA", arXiv: 2207.06294.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-07-26 13:36:03). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2022-07-26 13:36:00).
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
