无三角形图量子最大割的改进逼近算法

无三角形图量子最大割的改进逼近算法

时间戳记：9年2023月6日上午44:XNUMX

罗比·金

加州理工学院计算与数学科学系

觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.

抽象

我们给出了量子最大割的近似算法，其工作原理是将 SDP 弛豫舍入到纠缠量子态。 SDP 用于选择变分量子电路的参数。 然后，纠缠态被表示为应用于乘积态的量子电路。 它在无三角形图上实现了 0.582 的近似比。 Anshu、Gosset、Morenz 和 Parekh, Thompson 之前最好的算法分别达到了 0.531 和 0.533 的近似比。 此外，我们研究了 EPR 哈密顿量，我们认为这是一个自然的中间问题，它隔离了局部哈密顿问题的一些关键量子特征。 对于 EPR 哈密顿量，我们给出了所有图上的近似比率为 $1 / sqrt{2}$ 的近似算法。

无三角图上量子最大割的改进近似算法 PlatoBlockchain 数据智能。垂直搜索。人工智能。

特色图像：无三角形图中边缘的局部邻域。

[嵌入的内容]

热门摘要

我们如何将 SDP 弛豫舍入到纠缠量子态？ 我们应该如何优化变分电路 ansatz？ 在这项工作中，我们将这两个问题结合起来解决：使用SDP解决方案来选择变分电路的参数。

►BibTeX数据

►参考

[1] 阿努拉格·安舒、大卫·戈塞特和凯伦·莫伦茨。 超越最大割的量子模拟的乘积状态近似。 15 年第 2020 届量子计算、通信和密码学理论会议。https://​/​doi.org/​10.4230/​LIPIcs.TQC.2020.7。
https：/ / doi.org/ 10.4230 / LIPIcs.TQC.2020.7

[2] 阿努拉格·安舒、大卫·戈塞特、凯伦·莫伦茨和迈赫迪·索莱马尼法。 改进了有界度局部哈密顿量的近似算法。 物理评论快报，127(25):250502，2021。https://doi.org/10.1103/PhysRevLett.127.250502。
https：/ / doi.org/ 10.1103 / PhysRevLett.127.250502

[3] 乔普·布里埃、费尔南多·马里奥·德奥利维拉·菲略和弗兰克·瓦伦丁。 具有秩约束的半定规划的格洛腾迪克不等式。 计算理论，10(4):77–105, 2014。https:/​/​doi.org/​10.4086/​toc.2014.v010a004。
https：///doi.org/10.4086/toc.2014.v010a004

[4] 谢尔盖·布拉维、大卫·戈塞特、罗伯特·科尼格和克里斯坦·特梅。 量子多体问题的近似算法。 数学物理杂志，60（3）：032203，2019。https：/​/​doi.org/​10.1063/​1.5085428。
https：/ / doi.org/10.1063/ 1.5085428

[5] 费尔南多·GSL·布兰道 (Fernando GSL Brandao) 和阿拉姆·W·哈罗 (Aram W Harrow)。 量子态的乘积态近似。 数学物理通讯，342：47-80，2016。https：/​/​doi.org/​10.1007/​s00220-016-2575-1。
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[6] 托比·库比特和阿什利·蒙塔纳罗。 局部哈密顿问题的复杂性分类。 SIAM 计算杂志，45(2):268–316，2016。https://doi.org/10.1137/140998287。
https：/ / doi.org/10.1137/ 140998287

[7] 乌列尔·费奇和吉迪恩·谢克特曼。 关于最大割的随机超平面舍入技术的最优性。 随机结构与算法，20(3):403–440, 2002。https:/​/​doi.org/​10.1002/​rsa.10036。
https：/ / doi.org/ 10.1002 / rsa.10036

[8] 塞瓦格·加里比安和朱莉娅·肯佩。 qma 完全问题的近似算法。 SIAM 计算杂志，41(4):1028–1050, 2012。https:/​/​doi.org/​10.1137/​110842272。
https：/ / doi.org/10.1137/ 110842272

[9] 塞瓦格·加里比安 (Sevag Gharibian) 和奥哈斯·帕雷克 (Ojas Parekh)。 用于最大割的量子推广的几乎最佳经典近似算法。 近似、随机化和组合优化。 算法和技术（APPROX/​RANDOM 2019）。 Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik，2019。https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31。
https：///doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31

[10] 米歇尔·戈曼斯和大卫·威廉姆森。 使用半定规划改进了最大割和可满足性问题的近似算法。 ACM 杂志 (JACM)，42(6)：1115–1145，1995。https：/​/​doi.org/​10.1145/​227683.227684。
https：/ / doi.org/10.1145/ 227683.227684

[11] 约翰·哈斯塔德。 一些最优的不可逼近性结果。 ACM 杂志 (JACM)，48(4):798–859，2001。https:/​/​doi.org/​10.1145/​502090.502098。
https：/ / doi.org/10.1145/ 502090.502098

[12] Yeongwoo Hwang、Joe Neeman、Ojas Parekh、Kevin Thompson 和 John Wright。量子最大割的独特博弈硬度，以及推测的向量值博雷尔不等式。 2023 年年度 ACM-SIAM 离散算法研讨会 (SODA) 论文集，第 1319-1384 页。暹罗，2023。https://doi.org/10.1137/1.9781611977554.ch48。
https：/ / doi.org/ 10.1137 / 1.9781611977554.ch48

[13] 苏巴什·科特、盖伊·金德勒、埃尔查南·莫塞尔和瑞安·奥唐纳。 最大割和其他 2 变量 csp 的最佳不可逼近性结果？ SIAM 计算杂志，37(1):319–357, 2007。https:/​/​doi.org/​10.1137/​S0097539705447372。
https：/ / doi.org/ 10.1137 / S0097539705447372

[14] 尤努·李. 通过 sdp 优化量子电路参数。 第 33 届国际算法与计算研讨会 (ISAAC 2022)。 Schloss Dagstuhl-Leibniz-Zentrum für Informatik，2022 年。https://doi.org/10.4230/LIPIcs.ISAAC.2022.48。
https:/ / doi.org/ 10.4230/ LIPIcs.ISAAC.2022.48

[15] 斯蒂芬·皮多克和阿什利·蒙塔纳罗。 反铁磁相互作用和二维晶格的复杂性。 量子信息与计算，2(17-7):8–636，672。https:/​/​dl.acm.org/​doi/​abs/​2017/​10.5555。
https：///.dl.acm.org/doi/abs/10.5555/3179553.3179559

[16] 奥哈斯·帕里克和凯文·汤普森。 2级量子lasserre层次结构在量子逼近算法中的应用。 第 48 届自动机、语言和编程国际学术研讨会 (ICALP 2021)。 Schloss Dagstuhl-Leibniz-Zentrum für Informatik，2021 年。https://doi.org/10.4230/LIPIcs.ICALP.2021.102。
https：///doi.org/10.4230/LIPIcs.ICALP.2021.102

[17] 奥哈斯·帕里克和凯文·汤普森。 击败随机分配来近似量子 2-局部哈密顿问题。 第 29 届欧洲算法年度研讨会 (ESA 2021)。 Schloss Dagstuhl-Leibniz-Zentrum für Informatik，2021 年。https://doi.org/10.4230/LIPIcs.ESA.2021.74。
https：///doi.org/10.4230/LIPIcs.ESA.2021.74

[18] 奥哈斯·帕里克和凯文·汤普森。 具有正项的 2 局部量子哈密顿量的最优乘积态近似。 arXiv 预印本 arXiv:2206.08342, 2022。https:/​/​doi.org/​10.48550/​arXiv.2206.08342。
https://doi.org/10.48550/arXiv.2206.08342
的arXiv：2206.08342

被引用

[1] Nicolas PD Sawaya、Daniel Marti-Dafcik、Yang Ho、Daniel P Tabor、David Bernal、Alicia B Magann、Shavindra Premaratne、Pradeep Dubey、Anne Matsuura、Nathan Bishop、Wibe A de Jong、Simon Benjamin、Ojas D Parekh、 Norm Tubman、Katherine Klymko 和 Daan Camps，“HamLib：用于对量子算法和硬件进行基准测试的哈密顿量库”， 的arXiv：2306.13126, (2023).

[2] Dmitry Grinko 和 Maris Ozols，“具有酉等变约束的线性规划”， 的arXiv：2207.05713, (2022).

[3] Charlie Carlson、Zackary Jorquera、Alexandra Kolla、Steven Kordonowy 和 Stuart Wayland，“量子 Max-$d$-Cut 的近似算法”， 的arXiv：2309.10957, (2023).

[4] Adam Bene Watts、Anirban Chowdhury、Aidan Epperly、J. William Helton 和 Igor Klep，“通过交换算子的代数结构实现量子最大切割的松弛和精确解”， 的arXiv：2307.15661, (2023).

[5] Andrew Zhao 和 Nicholas C. Rubin，“利用费米子嵌入扩展量子优化的范围”， 的arXiv：2301.01778, (2023).

[6] Steven Heilman，“球面值噪声稳定性和量子 MAX-CUT 硬度”， 的arXiv：2306.03912, (2023).

以上引用来自 SAO / NASA广告 （最近成功更新为2023-11-09 11:49:09）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。

无法获取 Crossref引用的数据 在上一次尝试2023-11-09 11:49:08期间：无法从Crossref获取10.22331 / q-2023-11-09-1180的引用数据。 如果DOI是最近注册的，这是正常的。

该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。

时间戳记：

更多来自 量子杂志