1Laboratorium Kecerdasan Buatan Kuantum (QuAIL), Pusat Penelitian Ames NASA, Lapangan Moffett, CA
2Institut Penelitian USRA untuk Ilmu Komputer Tingkat Lanjut (RIACS), Mountain View, CA
3Pusat Informasi dan Komputasi Kuantum Berkeley, University of California, Berkeley, CA
4Departemen Ilmu Komputer, Universitas Chicago, Chicago, IL
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Kami mempertimbangkan kekuatan algoritme lokal untuk penyelesaian kira-kira Max $k$XOR, generalisasi dari dua masalah kepuasan kendala yang sebelumnya dipelajari dengan algoritme klasik dan kuantum (MaxCut dan Max E3LIN2). Dalam Max $k$XOR setiap kendala adalah XOR dari variabel $k$ persis dan bit paritas. Pada contoh dengan tanda acak (paritas) atau tanpa klausa yang tumpang tindih dan klausa $D+1$ per variabel, kami menghitung fraksi kepuasan yang diharapkan dari QAOA kedalaman-1 dari Farhi et al [arXiv:1411.4028] dan membandingkan dengan generalisasi dari algoritma ambang batas lokal dari Hirvonen et al [arXiv: 1402.2543]. Khususnya, algoritme kuantum mengungguli algoritme ambang batas untuk $k$$gt$$4$.
Di sisi lain, kami menyoroti potensi kesulitan untuk QAOA untuk mencapai keuntungan kuantum komputasi pada masalah ini. Pertama-tama kita menghitung batas atas yang ketat pada fraksi kepuasan maksimum dari hampir semua instans Max $k$XOR reguler acak yang besar dengan menghitung secara numerik kepadatan energi keadaan dasar $P(k)$ dari bidang rata-rata $k$-spin glass [ arXiv:1606.02365]. Batas atas tumbuh dengan $k$ jauh lebih cepat daripada kinerja kedua algoritme satu-lokal. Kami juga mengidentifikasi hasil obstruksi baru untuk sirkuit kuantum kedalaman rendah (termasuk QAOA) ketika $k=3$, menggeneralisasi hasil Bravyi et al [arXiv:1910.08980] ketika $k=2$. Kami menduga bahwa halangan serupa ada untuk semua $k$.
Gambar unggulan: Perbandingan fraksi (kinerja) yang memuaskan dari algoritme ambang dan QAOA kedalaman-1 untuk Max kXOR pada $D$ (dan $D gg k$). Konstanta $C_k$ untuk QAOA tumbuh lebih cepat dengan $k$ daripada untuk algoritma ambang batas. Meskipun algoritma threshold mengungguli QAOA depth-1 untuk $k dalam {2,3,4}$, pada semua k lainnya, QAOA adalah algoritma yang lebih baik.
[Embedded content]
โบ data BibTeX
โบ Referensi
[1] A. Auffinger dan W.-K. Chen. Tentang sifat-sifat tindakan 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 dan W.-K. Chen. Formula Parisi memiliki minimizer yang unik. Komunikasi dalam Fisika Matematika, 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 dan W.-K. Chen. Rumus Parisi untuk energi keadaan dasar dalam model p-spin campuran. arXiv:1606.05335, doi:10.1214/โ16-aop1173.
https://โ/โdoi.org/โ10.1214/โ16-aop1173
arXiv: 1606.05335
[4] AE Alaoui dan A. Montanari. Ambang algoritma dalam kacamata putaran rata-rata. arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari, dan M. Sellke. Optimalisasi kacamata spin medan rata-rata. 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, dan E. Tang. Hambatan untuk persiapan keadaan dan optimalisasi variasi dari perlindungan simetri. pracetak arXiv, 2019. arXiv:1910.08980.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak dan K. Marwaha. Algoritme klasik dan batasan kuantum untuk pemotongan maksimum pada grafik berketebalan tinggi. 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, dkk. Mengalahkan tugas acak pada masalah kepuasan kendala derajat terbatas. arXiv:1505.03424.
arXiv: 1505.03424
[9] W.-K. Chen, D. Gamarnik, D. Panchenko, dan M. Rahman. Suboptimalitas algoritma lokal untuk kelas masalah max-cut. 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, dan J. Shi. Keterbatasan Algoritma Kuantum Lokal pada Acak Max-k-XOR dan Beyond. arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti dan T. Rizzo. Analisis pemecahan simetri $infty$-replika dari model Sherrington-Kirkpatrick. Tinjauan Fisik 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 energi acak: Model sistem tak teratur yang dapat dipecahkan dengan tepat. fisik. Rev. B, 24:2613โ2626, Sep 1981. doi:10.1103/โPhysRevB.24.2613.
https://โ/โdoi.org/โ10.1103/โPhysRevB.24.2613
[13] A. Dembo, A. Montanari, dan S. Sen. Pemotongan ekstrim dari grafik acak jarang. 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 dan AW Harrow. Hamiltonian lokal yang keadaan dasarnya sulit diperkirakan. 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, dan S. Gutmann. Algoritma optimasi perkiraan kuantum. arXiv:1411.4028.
arXiv: 1411.4028
[16] E. Farhi, J. Goldstone, dan S. Gutmann. Algoritma optimasi perkiraan kuantum yang diterapkan pada masalah kendala kejadian terbatas. arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik, dan S. Gutmann. Algoritma optimasi perkiraan kuantum perlu melihat seluruh grafik: Kasus tipikal. arXiv: 2004.09002.
arXiv: 2004.09002
[18] J.Friedman. Bukti dugaan eigenvalue kedua Alon dan masalah terkait. arXiv:cs/โ0405020, doi:10.1090/โmemo/โ0910.
https://โ/โdoi.org/โ10.1090/โmemo/โ0910
arXiv: cs / 0405020
[19] S. Hadfield. Algoritma Quantum untuk Komputasi Ilmiah dan Optimasi Perkiraan. Universitas Columbia, 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] J. Hรฅstad. Beberapa hasil ketidakdekatan yang optimal. Jurnal 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 Hasting. Status energi rendah yang sepele untuk perjalanan Hamiltonians, dan dugaan PCP kuantum. Informasi & Komputasi Kuantum, 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 Hasting. Algoritma aproksimasi kedalaman terbatas klasik dan kuantum. 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 dan TH Hsieh. Simulasi variasional yang efisien dari keadaan kuantum non-sepele. 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, dan J. Suomela. Pemotongan besar dengan algoritme lokal pada grafik bebas segitiga. The Electronic Journal of Combinatorics, halaman P4โ21, 2017. arXiv:1402.2543, doi:10.37236/โ6862.
https: / / doi.org/ 10.37236 / 6862
arXiv: 1402.2543
[25] CY-Y. Lin dan Y.Zhu. Kinerja QAOA pada contoh khas masalah kepuasan kendala dengan derajat terbatas. arXiv:1601.01744.
arXiv: 1601.01744
[26] K.Marwaha. Algoritma MAX-CUT klasik lokal mengungguli $p=2$ QAOA pada graf reguler berketebalan tinggi. 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. Optimalisasi 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 dan A. Jastrzศฉbski. Pewarnaan tepi hipergraf 3-seragam. Matematika Terapan Diskrit, 217:48โ52, 2017, Optimasi Kombinatorial: Teori, Komputasi, dan Aplikasi. doi:10.1016/โj.dam.2016.06.009.
https: / / doi.org/ 10.1016 / j.dam.2016.06.009
[29] D. Panchenko. Pengantar 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. Panchenko. Pada model $k$-sat dengan sejumlah besar klausa. arXiv:1608.06256, doi:10.1002/โrsa.20748.
https: / / doi.org/ 10.1002 / rsa.20748
arXiv: 1608.06256
[31] G.Paris. Urutan solusi perkiraan untuk model SK untuk kacamata spin. Jurnal Fisika A: Matematika dan Umum, 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. Optimalisasi pada hipergraf acak yang jarang dan kacamata berputar. 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, dan I. Safro. Simetri klasik dan algoritma optimasi perkiraan kuantum. Pemrosesan Informasi Kuantum, 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 Paris. 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, dan EG Rieffel. Algoritme optimasi perkiraan kuantum untuk maxcut: Tampilan fermionik. fisik. 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
Dikutip oleh
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, dan Leo Zhou, โAlgoritma Optimasi Perkiraan Kuantum pada Kedalaman Tinggi untuk MaxCut pada Graf Reguler Besar-Girth dan Model Sherrington-Kirkpatrickโ, arXiv: 2110.14206.
[2] Nicolas PD Sawaya, Albert T Schmitz, dan Stuart Hadfield, "Pengkodean trade-off dan toolkit desain dalam algoritma kuantum untuk optimasi diskrit: pewarnaan, perutean, penjadwalan, dan masalah lainnya", arXiv: 2203.14432.
[3] Yash J. Patel, Sofiene Jerbi, Thomas Bck, dan Vedran Dunjko, โReinforcement Learning Assisted Recursive QAOAโ, arXiv: 2207.06294.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-07-26 13:36:03). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.
On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2022-07-26 13:36:00).
Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.
