Kuantum ve Klasik Yerel Algoritmalar ile Maks. $k$XOR'u Yaklaştırmanın Sınırları

Plato tarafından yeniden yayınlandı

İzleyiciler: 0

Kunal Merve^1,2,3,4 ve Stuart Hadfield'ın^1,2

¹Kuantum Yapay Zeka Laboratuvarı (QuAIL), NASA Ames Araştırma Merkezi, Moffett Field, CA
²USRA İleri Bilgisayar Bilimi Araştırma Enstitüsü (RIACS), Mountain View, CA
³Berkeley Kuantum Bilgi ve Hesaplama Merkezi, California Üniversitesi, Berkeley, CA
⁴Bilgisayar Bilimleri Bölümü, Chicago Üniversitesi, Chicago, IL

Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.

Özet

Daha önce klasik ve kuantum algoritmaları (MaxCut ve Max E3LIN2) ile çalışılan iki kısıt tatmin probleminin bir genellemesi olan Max $k$XOR'u yaklaşık olarak çözmek için yerel algoritmaların gücünü göz önünde bulunduruyoruz. Max $k$XOR'da her kısıtlama, tam olarak $k$ değişkenlerinin XOR'u ve bir eşlik bitidir. Rastgele işaretli (eşlikler) veya örtüşen tümceler ve değişken başına $D+1$ tümceleri olmayan örneklerde, Farhi ve diğerleri [arXiv:1]'den derinlik-1411.4028 QAOA'nın beklenen tatmin edici fraksiyonunu hesaplar ve bir genelleştirme ile karşılaştırırız. Hirvonen ve arkadaşlarının yerel eşik algoritması [arXiv:1402.2543]. Özellikle, kuantum algoritması $k$$gt$$4$ için eşik algoritmasından daha iyi performans gösterir.

Öte yandan, QAOA'nın bu problemde hesaplamalı kuantum avantajı elde etmesi için potansiyel zorlukları vurguluyoruz. İlk önce, bir ortalama alan $k$-döndürme camının temel durum enerji yoğunluğunu $P(k)$ sayısal olarak hesaplayarak neredeyse tüm büyük rastgele normal Max $k$XOR örneklerinin maksimum tatmin edici fraksiyonu üzerinde sıkı bir üst sınır hesaplıyoruz [ arXiv:1606.02365]. Üst sınır $k$ ile her iki tek-yerel algoritmanın performansından çok daha hızlı büyür. Ayrıca, $k=3$ olduğunda düşük derinlikli kuantum devreleri (QAOA dahil) için yeni bir engelleme sonucu belirledik ve Bravyi ve arkadaşlarının [arXiv:1910.08980] sonucunu $k=2$ olduğunda genelleştirdik. Tüm $k$ için benzer bir engelin var olduğunu varsayıyoruz.

Öne çıkan resim: Eşik algoritmasının tatmin edici fraksiyonu (performans) ile büyük $D$'da (ve $D gg k$) Max kXOR için derinlik-1 QAOA'nın karşılaştırması. QAOA için sabit $C_k$, eşik algoritmasına göre $k$ ile daha hızlı büyür. Eşik algoritması, {1}$'da $k için derinlik-2,3,4 QAOA'dan daha iyi performans gösterse de, diğer tüm k'lerde QAOA daha iyi algoritmadır.

[Gömülü içerik]

► BibTeX verileri

@article{Marwaha2022sınırları yaklaşık olarak, doi = {10.22331/q-2022-07-07-757}, url = {https://doi.org/10.22331/q-2022-07-07-757}, başlık = {Kuantum ve klasik yerel algoritmalarla {M}aks {$k$}{XOR} yaklaşımının sınırları}, yazar = {Marwaha, Kunal ve Hadfield, Stuart}, günlük = {{Kuantum}}, issn = {2521-327X}, yayıncı = {{Verein zur F{“{o}}rderung des Açık Erişim Yayıncıları in den Quantenwissenschaften}}, hacim = {6}, sayfalar = {757}, ay = temmuz, yıl = {2022} }

► Referanslar

[1] A. Auffinger ve W.-K. Chen. Parisi önlemlerinin özellikleri hakkında. arXiv:1303.3573, doi:10.1007/s00440-014-0563-y.
HTTPS: / / doi.org/ 10.1007 / s00440-014-0563-il
arXiv: 1303.3573

[2] A. Auffinger ve W.-K. Chen. Parisi formülünün benzersiz bir küçültücüsü vardır. Communications in Mathematical Physics, 335(3):1429–1444, Kasım 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 ve W.-K. Chen. Karışık p-spin modelinde temel durum enerjisi için Parisi formülü. arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335

[4] AE Alaoui ve A. Montanari. Ortalama alan spin camlarında algoritmik eşikler. arXiv:2009.11481.
arXiv: 2009.11481

[5] AE Alaoui, A. Montanari ve M. Sellke. Ortalama alan spin gözlüklerinin optimizasyonu. 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 ve E. Tang. Simetri korumasından durum hazırlığı ve varyasyon optimizasyonunun önündeki engeller. arXiv ön baskı, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980

[7] B. Barak ve K. Marwaha. Yüksek çevreli grafiklerde maksimum kesim için klasik algoritmalar ve kuantum sınırlamaları. 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. Rastgele atamayı sınırlı derecede kısıt tatmin problemlerinde yenmek. arXiv:1505.03424.
arXiv: 1505.03424

[9] W.-K. Chen, D. Gamarnik, D. Panchenko ve M. Rahman. Bir max-cut problemler sınıfı için yerel algoritmaların alt optimalliği. The Annals of Probability, 47(3), Mayıs 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 ve J. Shi. Rastgele Max-k-XOR ve Ötesinde Yerel Kuantum Algoritmalarının Sınırlamaları. arXiv:2108.06049.
arXiv: 2108.06049

[11] A. Crisanti ve T. Rizzo. Sherrington-Kirkpatrick modelinin $infty$-kopya simetri kırma çözümünün analizi. Fiziksel İnceleme E, 65(4), Nisan 2002. arXiv:cond-mat/0111037, doi:10.1103/physreve.65.046137.
https: / / doi.org/ 10.1103 / physreve.65.046137
arXiv: koşul-mat / 0111037

[12] B. Derrida. Rastgele enerji modeli: Tam olarak çözülebilir bir düzensiz sistem modeli. Fizik Rev. B, 24:2613–2626, Eylül 1981. doi:10.1103/PhysRevB.24.2613.
https: / / doi.org/ 10.1103 / PhysRevB.24.2613

[13] A. Dembo, A. Montanari ve S. Sen. Seyrek rastgele grafiklerin aşırı kesimleri. 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 ve AW Harrow. Temel durumları yaklaşık olarak tahmin edilmesi zor olan yerel Hamiltonianlar. 2017 IEEE 58. Yıllık Bilgisayar Bilimi Temelleri Sempozyumu (FOCS), Ekim 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 ve S. Gutmann. Bir kuantum yaklaşık optimizasyon algoritması. arXiv:1411.4028.
arXiv: 1411.4028

[16] E. Farhi, J. Goldstone ve S. Gutmann. Sınırlı bir oluşum kısıtlaması problemine uygulanan bir kuantum yaklaşık optimizasyon algoritması. arXiv:1412.6062.
arXiv: 1412.6062

[17] E. Farhi, D. Gamarnik ve S. Gutmann. Kuantum yaklaşık optimizasyon algoritmasının tüm grafiği görmesi gerekiyor: Tipik bir durum. arXiv:2004.09002.
arXiv: 2004.09002

[18] J. Friedman. Alon'un ikinci özdeğer varsayımı ve ilgili problemlerin bir kanıtı. arXiv:cs/0405020, doi:10.1090/memo/0910.
https://doi.org/10.1090/memo/0910
arXiv: cs / 0405020

[19] S. Hadfield. Bilimsel Hesaplama ve Yaklaşık Optimizasyon için Kuantum Algoritmaları. Columbia Üniversitesi, 2018, arXiv:1805.03265.
arXiv: 1805.03265

[20] J. Håstad. Bazı optimal yaklaştırmasızlık sonuçları. 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'in fotoğrafı. Hamiltonianları değiştirmek için önemsiz düşük enerji durumları ve kuantum PCP varsayımı. Kuantum Bilgi ve Hesaplama, 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'in fotoğrafı. Klasik ve kuantum sınırlı derinlik yaklaşımı algoritmaları. 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 ve TH Hsieh. Önemsiz kuantum durumlarının verimli varyasyonel simülasyonu. 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 ve J. Suomela. Üçgensiz grafiklerde yerel algoritmalarla büyük kesimler. The Electronic Journal of Combinatorics, sayfalar P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543

[25] CY-Y. Lin ve Y. Zhu. QAOA'nın sınırlı derecede kısıtlama memnuniyet problemlerinin tipik örnekleri üzerinde performansı. arXiv:1601.01744.
arXiv: 1601.01744

[26] K. Merve. Yerel klasik MAX-CUT algoritması, yüksek çevre düzenli grafiklerde $p=2$ QAOA'dan daha iyi performans gösterir. Quantum, 5:437, Nisan 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. Sherrington-Kirkpatrick Hamiltoniyenin optimizasyonu. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https: / / doi.org/ 10.1109 / focs.2019.00087
arXiv: 1812.10897

[28] P. Obszarski ve A. Jastrzȩbski. 3 tek tip hipergrafların kenar renklendirmesi. Discrete Applied Mathematics, 217:48–52, 2017, Kombinatoryal Optimizasyon: Teori, Hesaplama ve Uygulamalar. doi:10.1016/j.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009

[29] D. Panchenko. SK modeline giriş. 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. Çok sayıda tümce içeren $k$-sat modelinde. arXiv:1608.06256, doi:10.1002/rsa.20748.
https: / / doi.org/ 10.1002 / rsa.20748
arXiv: 1608.06256

[31] G. Parisi. Döndürme camları için SK modeline yaklaşık çözümler dizisi. Journal of Physics A: Mathematical and General, 13(4):L115–L121, Nisan 1980. doi:10.1088/0305-4470/13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009

[32] S. Sen. Seyrek rastgele hipergraflar ve döndürme camları üzerinde optimizasyon. 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 ve I. Safro. Klasik simetriler ve kuantum yaklaşık optimizasyon algoritması. Kuantum Bilgi İşleme, 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. Paris formülü. 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 ve EG Rieffel. maxcut için kuantum yaklaşık optimizasyon algoritması: fermiyonik bir görünüm. Fizik Rev. A, 97:022304, Şubat 2018. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998

Alıntılama

[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga ve 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 ve Stuart Hadfield, "Ayrık optimizasyon için kuantum algoritmalarında ödünleşimleri ve tasarım araç takımlarını kodlama: renklendirme, yönlendirme, zamanlama ve diğer sorunlar", arXiv: 2203.14432.

[3] Yash J. Patel, Sofiene Jerbi, Thomas Bäck ve Vedran Dunjko, “Reinforcement Learning Assisted Recursive QAOA”, arXiv: 2207.06294.

Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2022-07-26 13:36:03) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.

On Crossref'in alıntı yaptığı hizmet alıntı yapma çalışmaları ile ilgili veri bulunamadı (son deneme 2022-07-26 13:36:00).

Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.