1ห้องปฏิบัติการปัญญาประดิษฐ์ควอนตัม (นกกระทา), ศูนย์วิจัย NASA Ames, Moffett Field, CA
2USRA Research Institute for Advanced Computer Science (RIACS), เมาน์เทนวิว, CA
3ศูนย์ข้อมูลควอนตัมและการคำนวณเบิร์กลีย์ มหาวิทยาลัยแคลิฟอร์เนีย เบิร์กลีย์ แคลิฟอร์เนีย
4ภาควิชาวิทยาการคอมพิวเตอร์ University of Chicago, Chicago, IL
พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.
นามธรรม
เราพิจารณาถึงพลังของอัลกอริธึมท้องถิ่นสำหรับการแก้ปัญหา Max $k$XOR โดยประมาณ ซึ่งเป็นปัญหาทั่วไปของปัญหาความพึงพอใจที่มีข้อจำกัดสองประการที่ศึกษาก่อนหน้านี้ด้วยอัลกอริธึมแบบคลาสสิกและควอนตัม (MaxCut และ Max E3LIN2) ใน Max $k$XOR แต่ละข้อจำกัดคือ XOR ของตัวแปร $k$ และพาริตีบิต ในอินสแตนซ์ที่มีเครื่องหมายสุ่ม (พาริตี) หรือไม่มีส่วนคำสั่งที่ทับซ้อนกันและส่วนคำสั่ง $D+1$ ต่อตัวแปร เราจะคำนวณเศษส่วนที่น่าพอใจที่คาดหวังของ QAOA เชิงลึก -1 จาก Farhi et al [arXiv:1411.4028] และเปรียบเทียบกับลักษณะทั่วไปของ อัลกอริธึมเกณฑ์ท้องถิ่นจาก Hirvonen et al [arXiv:1402.2543] โดยเฉพาะอย่างยิ่ง อัลกอริทึมควอนตัมมีประสิทธิภาพเหนือกว่าอัลกอริทึมขีดจำกัดสำหรับ $k$$gt$$4$
ในทางกลับกัน เราเน้นถึงปัญหาที่อาจเกิดขึ้นสำหรับ QAOA เพื่อให้เกิดความได้เปรียบเชิงควอนตัมเชิงคำนวณสำหรับปัญหานี้ ขั้นแรก เราคำนวณขอบเขตบนอย่างแน่นหนาบนเศษส่วนที่น่าพอใจสูงสุดของอินสแตนซ์สูงสุด $k$XOR ปกติขนาดใหญ่เกือบทั้งหมด โดยการคำนวณเชิงตัวเลขของความหนาแน่นของสถานะภาคพื้นดิน $P(k)$ ของกระจกหมุน $k$-spin ที่มีฟิลด์กลาง arXiv:1606.02365]. ขอบเขตบนเติบโตด้วย $k$ เร็วกว่าประสิทธิภาพของอัลกอริธึมแบบโลคัลทั้งสองมาก นอกจากนี้เรายังระบุผลการกีดขวางใหม่สำหรับวงจรควอนตัมความลึกต่ำ (รวมถึง QAOA) เมื่อ $k=3$ สรุปผลลัพธ์ของ Bravyi et al [arXiv:1910.08980] เมื่อ $k=2$ เราคาดว่ามีสิ่งกีดขวางที่คล้ายกันสำหรับ $k$ ทั้งหมด
ภาพเด่น: การเปรียบเทียบเศษส่วนที่น่าพอใจ (ประสิทธิภาพ) ของอัลกอริธึมขีดจำกัดและ QAOA เชิงลึก -1 สำหรับ Max kXOR ที่ $D$ มาก (และ $D gg k$) ค่าคงที่ $C_k$ สำหรับ QAOA เติบโตเร็วกว่าด้วย $k$ สำหรับอัลกอริธึมขีดจำกัด แม้ว่าอัลกอรึทึมธรณีประตูจะทำงานได้ดีกว่า QAOA เชิงลึกสำหรับ $k ใน {1}$ ที่ k อื่นทั้งหมด QAOA เป็นอัลกอริธึมที่ดีกว่า
[เนื้อหาฝัง]
► ข้อมูล BibTeX
► ข้อมูลอ้างอิง
[1] A. Auffinger และ W.-K. เฉิน. ว่าด้วยคุณสมบัติของมาตรการปาริสี arXiv:1303.3573, ดอย:10.1007/s00440-014-0563-y.
https://doi.org/10.1007/s00440-014-0563-y
arXiv: 1303.3573
[2] A. Auffinger และ W.-K. เฉิน. สูตร Parisi มีตัวย่อขนาดพิเศษที่ไม่เหมือนใคร 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 และ W.-K. เฉิน. สูตรปาริสีสำหรับพลังงานภาคพื้นดินในแบบจำลองพีสปินแบบผสม arXiv:1606.05335, ดอย:10.121416-aop1173.
https://doi.org/10.121416-aop1173
arXiv: 1606.05335
[4] AE Alaoui และ A. Montanari เกณฑ์อัลกอริธึมในแว่นสปินกลาง arXiv:2009.11481.
arXiv: 2009.11481
[5] AE Alaoui, A. Montanari และ M. Sellke การเพิ่มประสิทธิภาพของแว่นตาหมุนแบบมีเดียมฟิลด์ arXiv:2001.00904, ดอย:10.1214/21-aop1519.
https://doi.org/10.121421-aop1519
arXiv: 2001.00904
[6] S. Bravyi, A. Kliesch, R. Koenig และ E. Tang อุปสรรคในการจัดเตรียมสถานะและการเพิ่มประสิทธิภาพการเปลี่ยนแปลงจากการป้องกันสมมาตร พิมพ์ล่วงหน้า arXiv, 2019. arXiv:1910.08980.
https://doi.org/10.1103/PhysRevLett.125.260505
arXiv: 1910.08980
[7] B. Barak และ K. Marwaha. อัลกอริธึมแบบคลาสสิกและข้อจำกัดของควอนตัมสำหรับการตัดสูงสุดบนกราฟเส้นรอบวงสูง arXiv:2106.05900, ดอย: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 และคณะ เอาชนะการมอบหมายงานแบบสุ่มในปัญหาความพึงพอใจที่มีขอบเขตจำกัด arXiv:1505.03424.
arXiv: 1505.03424
[9] ว.-เค. Chen, D. Gamarnik, D. Panchenko และ M. Rahman ความเหมาะสมของอัลกอริธึมโลคัลสำหรับคลาสของปัญหาสูงสุด The Annals of Probability, 47(3), พฤษภาคม 2019. arXiv:1707.05386, doi:10.1214/18-aop1291.
https://doi.org/10.121418-aop1291
arXiv: 1707.05386
[10] ค.-น. Chou, PJ Love, JS Sandhu และ J. Shi ข้อจำกัดของอัลกอริธึมควอนตัมในพื้นที่บน Random Max-k-XOR และอื่นๆ arXiv:2108.06049.
arXiv: 2108.06049
[11] A. Crisanti และ T. Rizzo การวิเคราะห์โซลูชันการทำลายสมมาตร $infty$-replica ของโมเดล Sherrington-Kirkpatrick Physical Review E, 65(4), เมษายน 2002. arXiv:cond-mat/0111037, doi:10.1103/physreve.65.046137.
https://doi.org/10.1103/physreve.65.046137
arXiv:cond-mat/0111037
[12] ข. เดอริด้า. แบบจำลองพลังงานสุ่ม: แบบจำลองของระบบที่ไม่เป็นระเบียบที่แก้ไขได้ สรีรวิทยา 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 และ S. Sen. กราฟสุ่มกระจัดกระจายอย่างรุนแรง พงศาวดารของความน่าจะเป็น, 45(2):1190–1217, 2017. arXiv:1503.03923, doi:10.1214/15-aop1084.
https://doi.org/10.121415-aop1084
arXiv: 1503.03923
[14] แอล. เอลดาร์และเอดับเบิลยู แฮร์โรว์ ชาวแฮมิลตันในท้องที่ซึ่งสภาพพื้นดินยากต่อการประมาณ 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), ตุลาคม 2017. arXiv:1510.02082, doi:10.1109/focs.2017.46.
https://doi.org/10.1109/focs.2017.46
arXiv: 1510.02082
[15] อี. ฟาร์ฮี เจ. โกลด์สโตน และเอส. กัทมันน์ อัลกอริธึมการเพิ่มประสิทธิภาพโดยประมาณควอนตัม arXiv:1411.4028.
arXiv: 1411.4028
[16] อี. ฟาร์ฮี เจ. โกลด์สโตน และเอส. กัทมันน์ อัลกอริธึมการเพิ่มประสิทธิภาพโดยประมาณควอนตัมที่ใช้กับปัญหาข้อจำกัดการเกิดขึ้นที่มีขอบเขต arXiv:1412.6062.
arXiv: 1412.6062
[17] E. Farhi, D. Gamarnik และ S. Gutmann อัลกอริธึมการเพิ่มประสิทธิภาพโดยประมาณควอนตัมจำเป็นต้องดูกราฟทั้งหมด: กรณีทั่วไป arXiv:2004.09002.
arXiv: 2004.09002
[18] เจ. ฟรีดแมน. หลักฐานการคาดเดาค่าลักษณะเฉพาะที่สองของ Alon และปัญหาที่เกี่ยวข้อง arXiv:cs/0405020, ดอย:10.1090/memo/0910.
https://doi.org/10.1090/memo/0910
arXiv:cs/0405020
[19] เอส. แฮดฟิลด์. อัลกอริธึมควอนตัมสำหรับการคำนวณทางวิทยาศาสตร์และการเพิ่มประสิทธิภาพโดยประมาณ มหาวิทยาลัยโคลัมเบีย 2018, arXiv:1805.03265.
arXiv: 1805.03265
[20] เจ. ฮาสตัด. ผลลัพธ์การประมาณค่าไม่ได้ที่เหมาะสมที่สุด วารสาร 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] เอ็มบี เฮสติงส์ สถานะพลังงานต่ำเล็กน้อยสำหรับการเดินทางแฮมิลตันและการคาดเดา PCP ควอนตัม Quantum Information & Computation, 13, 2013. arXiv:1201.3387, ดอย:10.26421/qic13.5-6-3.
https://doi.org/10.26421/qic13.5-6-3
arXiv: 1201.3387
[22] เอ็มบี เฮสติงส์ อัลกอริธึมการประมาณความลึกขอบเขตแบบคลาสสิกและควอนตัม arXiv:1905.07047, ดอย:10.26421/qic19.13-14-3.
https://doi.org/10.26421/qic19.13-14-3
arXiv: 1905.07047
[23] WW Ho และ TH Hsieh การจำลองการเปลี่ยนแปลงอย่างมีประสิทธิภาพของสถานะควอนตัมที่ไม่สำคัญ arXiv:1803.00026, ดอย: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 และ J. Suomela การตัดขนาดใหญ่ด้วยอัลกอริธึมในพื้นที่บนกราฟที่ไม่มีรูปสามเหลี่ยม The Electronic Journal of Combinatorics, หน้า P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https://doi.org/10.37236/6862
arXiv: 1402.2543
[25] CY-Y Lin และ Y. Zhu ประสิทธิภาพของ QAOA ในกรณีทั่วไปของปัญหาความพึงพอใจจากข้อจำกัดที่มีขอบเขตจำกัด arXiv:1601.01744.
arXiv: 1601.01744
[26] เค. มาร์วาฮา. อัลกอริธึม MAX-CUT แบบคลาสสิกในพื้นที่มีประสิทธิภาพเหนือกว่า $p=2$ QAOA บนกราฟปกติที่มีเส้นรอบวงสูง Quantum, 5:437, เม.ย. 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] ก. มอนตานารี. การเพิ่มประสิทธิภาพของ Sherrington–Kirkpatrick Hamiltonian arXiv:1812.10897 ดอย:10.1109/focs.2019.00087
https://doi.org/10.1109/focs.2019.00087
arXiv: 1812.10897
[28] P. Obszarski และ A. Jastrzȩbski. การลงสีขอบของไฮเปอร์กราฟ 3 ชุด Discrete Applied Mathematics, 217:48–52, 2017, การเพิ่มประสิทธิภาพเชิงผสมผสาน: ทฤษฎี, การคำนวณ และการประยุกต์ใช้ ดอย:10.1016/j.dam.2016.06.009.
https://doi.org/10.1016/j.dam.2016.06.009
[29] ดี. พันเชนโก. ข้อมูลเบื้องต้นเกี่ยวกับโมเดล SK arXiv:1412.0170, ดอย:10.4310/cdm.2014.v2014.n1.a4.
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
arXiv: 1412.0170
[30] ดี. พันเชนโก. ในโมเดล $k$-sat ที่มีอนุประโยคจำนวนมาก arXiv:1608.06256, ดอย:10.1002/rsa.20748.
https://doi.org/10.1002/rsa.20748
arXiv: 1608.06256
[31] ก. ปาริซี่. ลำดับวิธีแก้ปัญหาโดยประมาณสำหรับรุ่น SK สำหรับแว่นหมุน Journal of Physics A: Mathematical and General, 13(4):L115–L121, เมษายน 1980. doi:10.1088/0305-4470/13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009
[32] S. Sen. การเพิ่มประสิทธิภาพบนไฮเปอร์กราฟสุ่มแบบกระจัดกระจายและแว่นตาหมุน arXiv:1606.02365, ดอย:10.1002/rsa.20774.
https://doi.org/10.1002/rsa.20774
arXiv: 1606.02365
[33] R. Shaydulin, S. Hadfield, T. Hogg และ I. Safro สมมาตรแบบคลาสสิกและอัลกอริธึมการเพิ่มประสิทธิภาพควอนตัมโดยประมาณ การประมวลผลข้อมูลควอนตัม, 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] ม.ตาลาแกรนด์. สูตรปาริซี่. 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 และ EG Rieffel อัลกอริธึมการเพิ่มประสิทธิภาพโดยประมาณของควอนตัมสำหรับ maxcut: มุมมองแบบเฟอร์มิโอนิก สรีรวิทยา Rev. A, 97:022304, ก.พ. 2018. arXiv:1706.02998, doi:10.1103/PhysRevA.97.022304.
https://doi.org/10.1103/PhysRevA.97.022304
arXiv: 1706.02998
อ้างโดย
[1] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga และ Leo Zhou, “อัลกอริทึมการเพิ่มประสิทธิภาพเชิงควอนตัมโดยประมาณที่ความลึกสูงสำหรับ MaxCut บนกราฟปกติเส้นรอบวงขนาดใหญ่และแบบจำลองเชอร์ริงตัน-เคิร์กแพทริก”, arXiv: 2110.14206.
[2] Nicolas PD Sawaya, Albert T Schmitz และ Stuart Hadfield “การเข้ารหัสการแลกเปลี่ยนและชุดเครื่องมือการออกแบบในอัลกอริทึมควอนตัมสำหรับการเพิ่มประสิทธิภาพแบบไม่ต่อเนื่อง: การระบายสี การกำหนดเส้นทาง การจัดกำหนดการ และปัญหาอื่นๆ”, arXiv: 2203.14432.
[3] Yash J. Patel, Sofiene Jerbi, Thomas Bäck และ Vedran Dunjko, “Reinforcement Learning Assisted Recursive QAOA”, arXiv: 2207.06294.
การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2022-07-26 13:36:03 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน
On บริการอ้างอิงของ Crossref ไม่พบข้อมูลอ้างอิงงาน (ความพยายามครั้งสุดท้าย 2022-07-26 13:36:00)
บทความนี้เผยแพร่ใน Quantum ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา
