1量子人工智能实验室 (QuAIL)，美国宇航局艾姆斯研究中心，加利福尼亚州莫菲特场
2USRA 高级计算机科学研究所 (RIACS)，加利福尼亚州山景城
3加州大学伯克利分校伯克利量子信息与计算中心
4芝加哥大学计算机科学系，伊利诺伊州芝加哥
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
我们考虑局部算法近似求解 Max $k$XOR 的能力，这是先前使用经典算法和量子算法（MaxCut 和 Max E3LIN2）研究的两个约束满足问题的概括。 在 Max $k$XOR 中，每个约束都是恰好 $k$ 变量和奇偶校验位的 XOR。 在具有随机符号（奇偶校验）或没有重叠子句和每个变量 $D+1$ 子句的实例上，我们计算来自 Farhi 等人 [arXiv:1] 的深度 1411.4028 QAOA 的预期满足分数，并与Hirvonen 等人 [arXiv:1402.2543] 的局部阈值算法。 值得注意的是，量子算法在 $k$$gt$$4$ 上优于阈值算法。
另一方面，我们强调了 QAOA 在这个问题上实现计算量子优势的潜在困难。 我们首先通过数值计算平均场$k$-spin glass的基态能量密度$P(k)$来计算几乎所有大型随机常规Max$k$XOR实例的最大满足部分的严格上限[ arXiv:1606.02365]。 上限以 $k$ 的速度增长，比这两种单局部算法的性能都要快得多。 我们还确定了 $k=3$ 时低深度量子电路（包括 QAOA）的新阻塞结果，概括了 $k=1910.08980$ 时 Bravyi 等人 [arXiv:2] 的结果。 我们推测所有$k$都存在类似的障碍。
特色图像：阈值算法的令人满意的分数（性能）与 Max kXOR 在大 $D$（和 $D gg k$）的深度 1 QAOA 的比较。 QAOA 的常数 $C_k$ 随着 $k$ 的增长比阈值算法更快。 尽管阈值算法在 {1}$ 中对于 $k 优于深度 2,3,4 QAOA，但在所有其他 k 中，QAOA 是更好的算法。
[嵌入的内容]
►BibTeX数据
►参考
[1] A.奥芬格和 W.-K。 陈。 关于帕里西措施的性质。 arXiv:1303.3573, doi:10.1007/s00440-014-0563-y。
https：/ / doi.org/ 10.1007 / s00440-014-0563-y
的arXiv：1303.3573
[2] A.奥芬格和 W.-K。 陈。 Parisi 配方有一个独特的最小化剂。 Communications in Mathematical Physics，335(3):1429–1444，2014 年 1402.5132 月。arXiv:10.1007, doi:00220/s014-2254-XNUMX-z。
https：/ / doi.org/ 10.1007 / s00220-014-2254-z
的arXiv：1402.5132
[3] A.奥芬格和 W.-K。 陈。 混合 p 自旋模型中基态能量的 Parisi 公式。 arXiv:1606.05335, doi:10.1214/16-aop1173。
https:///doi.org/10.1214/16-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, doi:10.1214/21-aop1519。
https:///doi.org/10.1214/21-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, 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 等人。 在有界度的约束满足问题上击败随机分配。 arXiv:1505.03424。
的arXiv：1505.03424
[9] W.-K。 Chen、D. Gamarnik、D. Panchenko 和 M. Rahman。 一类最大切问题的局部算法的次优性。 概率年鉴，47(3)，2019 年 1707.05386 月。arXiv:10.1214, doi:18/1291-aopXNUMX。
https:///doi.org/10.1214/18-aop1291
的arXiv：1707.05386
[10] C.-N。 Chou、PJ Love、JS Sandhu 和 J. Shi。 局部量子算法在随机 Max-k-XOR 及其他方面的局限性。 arXiv:2108.06049。
的arXiv：2108.06049
[11] A. Crisanti 和 T. Rizzo。 Sherrington-Kirkpatrick 模型的$infty$-replica 对称破坏解的分析。 物理评论 E，65(4)，2002 年 0111037 月。arXiv:cond-mat/10.1103，doi:65.046137/physreve.XNUMX。
https：/ / doi.org/ 10.1103 / physreve.65.046137
arXiv：cond-mat / 0111037
[12] B.德里达。 随机能量模型：无序系统的完全可解模型。 物理。 Rev. B，24:2613–2626，1981 年 10.1103 月。doi:24.2613/PhysRevB.XNUMX。
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.1214/15-aop1084
的arXiv：1503.03923
[14] L. Eldar 和 AW Harrow。 基态难以近似的局部哈密顿量。 2017 年 IEEE 第 58 届计算机科学基础 (FOCS) 年度研讨会，2017 年 1510.02082 月。arXiv:10.1109, doi:2017.46/focs.XNUMX。
https：/ / doi.org/ 10.1109 / focs.2017.46
的arXiv：1510.02082
[15] E. Farhi、J. Goldstone 和 S. Gutmann。 一种量子近似优化算法。 arXiv：1411.4028。
的arXiv：1411.4028
[16] E. Farhi、J. Goldstone 和 S. Gutmann。 一种应用于有界出现约束问题的量子近似优化算法。 arXiv:1412.6062。
的arXiv：1412.6062
[17] E. Farhi、D. Gamarnik 和 S. Gutmann。 量子近似优化算法需要看全图：典型案例。 arXiv:2004.09002。
的arXiv：2004.09002
[18] J.弗里德曼。 阿隆第二特征值猜想及相关问题的证明。 arXiv:cs/0405020，doi:10.1090/memo/0910。
https:///doi.org/10.1090/memo/0910
arXiv：cs / 0405020
[19] S.哈德菲尔德。 用于科学计算和近似优化的量子算法。 哥伦比亚大学，2018，arXiv:1805.03265。
的arXiv：1805.03265
[20] J. 哈斯塔德。 一些最优的不可近似性结果。 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黑斯廷斯。 通勤哈密顿量的平凡低能态和量子 PCP 猜想。 量子信息与计算，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黑斯廷斯。 经典和量子有界深度近似算法。 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 和 TH Hsieh。 非平凡量子态的有效变分模拟。 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 和 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。 林和Y.朱。 QAOA 在有限度约束满足问题的典型实例上的性能。 arXiv：1601.01744。
的arXiv：1601.01744
[26] K.马尔瓦哈。 局部经典 MAX-CUT 算法在高周长正则图上优于 $p=2$ QAOA。 量子，5:437，2021 年 2101.05513 月。arXiv:10.22331，doi:2021/q-04-20-437-XNUMX。
https://doi.org/10.22331/q-2021-04-20-437
的arXiv：2101.05513
[27] A.蒙塔纳里。 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 和 A. Jastrzȩbski。 3-均匀超图的边缘着色。 离散应用数学，217：48-52，2017，组合优化：理论、计算和应用。 doi:10.1016/j.dam.2016.06.009。
https：///doi.org/10.1016/j.dam.2016.06.009
[29] D.潘琴科。 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.潘琴科。 在具有大量子句的 $k$-sat 模型上。 arXiv:1608.06256, doi:10.1002/rsa.20748。
https：/ / doi.org/ 10.1002 / rsa.20748
的arXiv：1608.06256
[31] G.帕里西。 旋转玻璃 SK 模型的一系列近似解。 Journal of Physics A: Mathematical and General, 13(4):L115–L121, 1980 年 10.1088 月。doi:0305/4470-13/4/009/XNUMX。
https://doi.org/10.1088/0305-4470/13/4/009
[32] S. Sen. 稀疏随机超图和自旋眼镜的优化。 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 和 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] M.塔拉格兰德。 帕里西公式。 数学年鉴, 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 年 1706.02998 月。arXiv:10.1103，doi:97.022304/PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.97.022304
的arXiv：1706.02998
被引用
[1] Joao Basso、Edward Farhi、Kunal Marwaha、Benjamin Villalonga 和 Leo Zhou，“MaxCut 在大周长正则图和 Sherrington-Kirkpatrick 模型上的高深度量子近似优化算法”， 的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，“强化学习辅助递归 QAOA”， 的arXiv：2207.06294.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-07-26 13:36:03）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-07-26 13:36:00）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
