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, University of California, Berkeley, CA
4Department of Computer Science, University of Chicago, Chicago, IL
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Vi betragter styrken af lokale algoritmer til tilnærmelsesvis løsning af Max $k$XOR, en generalisering af to begrænsningstilfredshedsproblemer, der tidligere er undersøgt med klassiske og kvantealgoritmer (MaxCut og Max E3LIN2). I Max $k$XOR er hver begrænsning XOR for nøjagtigt $k$ variabler og en paritetsbit. På tilfælde med enten tilfældige fortegn (pariteter) eller ingen overlappende klausuler og $D+1$-sætninger pr. variabel, beregner vi den forventede tilfredsstillende brøkdel af dybden-1 QAOA fra Farhi et al [arXiv:1411.4028] og sammenligner med en generalisering af den lokale tærskelalgoritme fra Hirvonen et al [arXiv:1402.2543]. Navnlig overgår kvantealgoritmen tærskelalgoritmen for $k$$gt$$4$.
På den anden side fremhæver vi potentielle vanskeligheder for QAOA med at opnå beregningsmæssig kvantefordel på dette problem. Vi beregner først en stram øvre grænse for den maksimale tilfredsstillende brøkdel af næsten alle store tilfældige regulære Max $k$XOR-instanser ved numerisk at beregne grundtilstandsenergitætheden $P(k)$ af et middelfelt $k$-spin glas [ arXiv:1606.02365]. Den øvre grænse vokser med $k$ meget hurtigere end ydeevnen af begge en-lokale algoritmer. Vi identificerer også et nyt obstruktionsresultat for kvantekredsløb med lav dybde (inklusive QAOA), når $k=3$, generaliserer et resultat af Bravyi et al [arXiv:1910.08980], når $k=2$. Vi formoder, at der findes en lignende hindring for alle $k$.
Udvalgt billede: Sammenligning af den tilfredsstillende brøkdel (ydelse) af tærskelalgoritmen og dybde-1 QAOA for Max kXOR ved stort $D$ (og $D gg k$). Konstanten $C_k$ for QAOA vokser hurtigere med $k$ end for tærskelalgoritmen. Selvom tærskelalgoritmen overgår dybde-1 QAOA for $k i {2,3,4}$, på alle andre k, er QAOA den bedre algoritme.
[Indlejret indhold]
► BibTeX-data
► Referencer
[1] A. Auffinger og W.-K. Chen. Om egenskaber af Parisi foranstaltninger. 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 og W.-K. Chen. Parisi-formlen har en unik minimer. 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 og W.-K. Chen. Parisi formel for grundtilstandsenergien i den blandede p-spin model. arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335
[4] AE Alaoui og A. Montanari. Algoritmiske tærskler i middelfeltspinglas. arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari og M. Sellke. Optimering af middelfeltsspinglas. 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 og E. Tang. Forhindringer for tilstandsforberedelse og variationsoptimering fra symmetribeskyttelse. arXiv fortryk, 2019. arXiv:1910.08980.
https:///doi.org/10.1103/PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak og K. Marwaha. Klassiske algoritmer og kvantebegrænsninger for maksimal skæring på grafer med høj omkreds. 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. Slå den tilfældige opgave på problemer med begrænsningstilfredshed af begrænset grad. arXiv:1505.03424.
arXiv: 1505.03424
[9] W.-K. Chen, D. Gamarnik, D. Panchenko og M. Rahman. Suboptimalitet af lokale algoritmer til en klasse af max-cut-problemer. 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 og J. Shi. Begrænsninger af lokale kvantealgoritmer på tilfældig Max-k-XOR og videre. arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti og T. Rizzo. Analyse af $infty$-replika symmetri brydende løsning af Sherrington-Kirkpatrick modellen. 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. Random-energy model: En nøjagtigt løselig model af uordnede systemer. 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 og S. Sen. Ekstreme udskæringer af sparsomme tilfældige grafer. 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 og AW Harrow. Lokale Hamiltonianere, hvis grundtilstande er svære at tilnærme. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), okt. 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 og S. Gutmann. En omtrentlig kvanteoptimeringsalgoritme. arXiv:1411.4028.
arXiv: 1411.4028
[16] E. Farhi, J. Goldstone og S. Gutmann. En omtrentlig kvanteoptimeringsalgoritme anvendt på et afgrænset forekomstbegrænsningsproblem. arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik og S. Gutmann. Den omtrentlige kvanteoptimeringsalgoritme skal se hele grafen: Et typisk tilfælde. arXiv:2004.09002.
arXiv: 2004.09002
[18] J. Friedman. Et bevis på Alons anden egenværdiformodning og relaterede problemer. arXiv:cs/0405020, doi:10.1090/memo/0910.
https://doi.org/10.1090/memo/0910
arXiv:cs/0405020
[19] S. Hadfield. Kvantealgoritmer til videnskabelig databehandling og omtrentlig optimering. Columbia University, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Håstad. Nogle optimale resultater med utilnærmelighed. 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. Trivielle lavenergitilstande for pendlende Hamiltonianere og kvante PCP-formodningen. 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. Klassiske og kvantegrænsede dybdetilnærmelsesalgoritmer. 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 og TH Hsieh. Effektiv variationssimulering af ikke-trivielle kvantetilstande. 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 og J. Suomela. Store snit med lokale algoritmer på trekantfri grafer. The Electronic Journal of Combinatorics, side P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https:///doi.org/10.37236/6862
arXiv: 1402.2543
[25] CY-Y. Lin og Y. Zhu. Udførelse af QAOA på typiske tilfælde af begrænsningstilfredshedsproblemer med begrænset grad. arXiv:1601.01744.
arXiv: 1601.01744
[26] K. Marwaha. Lokal klassisk MAX-CUT-algoritme overgår $p=2$ QAOA på almindelige grafer med høj omkreds. 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. Optimering af Sherrington-Kirkpatrick Hamiltonian. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https:///doi.org/10.1109/focs.2019.00087
arXiv: 1812.10897
[28] P. Obszarski og A. Jastrzȩbski. Kantfarvning af 3-ensartede hypergrafer. Discrete Applied Mathematics, 217:48–52, 2017, Combinatorial Optimization: Theory, Computation, and Applications. doi:10.1016/j.dam.2016.06.009.
https:///doi.org/10.1016/j.dam.2016.06.009
[29] D. Panchenko. Introduktion til SK-modellen. 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. Panchenko. På $k$-sat modellen med et stort antal klausuler. arXiv:1608.06256, doi:10.1002/rsa.20748.
https:///doi.org/10.1002/rsa.20748
arXiv: 1608.06256
[31] G. Parisi. En sekvens af tilnærmede løsninger til SK-modellen for spin-briller. 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. Optimering på sparsomme tilfældige hypergrafer og spin-briller. 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 og I. Safro. Klassiske symmetrier og den omtrentlige kvanteoptimeringsalgoritme. 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. Parisi-formlen. 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 og EG Rieffel. Kvantetilnærmet optimeringsalgoritme for maxcut: En fermionisk visning. Phys. 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
Citeret af
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga og 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 og Stuart Hadfield, "Kodning af afvejninger og designværktøjssæt i kvantealgoritmer til diskret optimering: farvelægning, routing, planlægning og andre problemer", arXiv: 2203.14432.
[3] Yash J. Patel, Sofiene Jerbi, Thomas Bäck og Vedran Dunjko, "Reinforcement Learning Assisted Recursive QAOA", arXiv: 2207.06294.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-07-26 13:36:03). 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-26 13:36:00).
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.
