事实证明，采用定制混频器的热启动 QAOA 可以收敛，并在低电路深度的计算上击败 Goemans-Williamson 的 Max-Cut

事实证明，采用定制混频器的热启动 QAOA 可以收敛，并在低电路深度的计算上击败 Goemans-Williamson 的 Max-Cut

时间戳记：26年2023月9日上午22:XNUMX

鲁本·泰特1, 杰·蒙德拉2, 布莱恩·加德3, 格雷格·莫勒3及 斯瓦蒂古普塔4

1CCS-3 信息科学，洛斯阿拉莫斯国家实验室，洛斯阿拉莫斯，NM 87544，美国
2佐治亚理工学院，亚特兰大，GA 30332，美国
3佐治亚理工学院研究所，亚特兰大，GA 30332，美国
4麻省理工学院斯隆管理学院，剑桥，MA 02142，美国

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

抽象

我们推广了 Farhi 等人的量子近似优化算法（QAOA）。 （2014）允许具有相应混合器的任意可分离初始状态，使得起始状态是混合哈密顿量的最激发状态。 我们通过在加权图上模拟 Max-Cut 来演示这个版本的 QAOA，我们称之为 $QAOA-warmest$。 我们使用通过 Max-Cut 半定程序解的随机投影获得的 $2$ 和 $3$ 维近似值将起始状态初始化为 $warm-start$，并定义一个依赖于热启动的 $custom Mixer$。 我们表明，对于具有非负边权重的图，这些热启动使用 $0.658$ 维的常数因子近似值 $2$ 和 $0.585$ 维的热启动 $3$ 来初始化 QAOA 电路，从而改进了先前已知的琐碎（即，$0.5$ 用于标准初始化）最坏情况边界为 $p=0$。 这些因素实际上降低了在较高电路深度下获得的 Max-Cut 的近似值，因为我们还表明，任何可分离初始状态的 QAOA-warmest 都会在绝热极限下收敛到 Max-Cut，即 $prightarrow infty$。 然而，热启动的选择会显着影响 Max-Cut 的收敛速度，并且我们根据经验表明，与现有方法相比，我们的热启动实现了更快的收敛。 此外，对于 $1148$ 图（最多 $11$ 节点）和深度 $p=8 的实例库，与标准 QAOA、经典 Goemans-Williamson 算法和不带自定义混合器的热启动 QAOA 相比，我们的数值模拟显示出更高质量的切割$。 我们进一步表明，QAOA-warmest 优于 Farhi 等人的标准 QAOA。 在当前 IBM-Q 和 Quantinuum 硬件上进行实验。

事实证明，带有定制混合器的热启动 QAOA 可以收敛并在计算上击败 Goemans-Williamson 的低电路深度 PlatoBlockchain 数据智能的 Max-Cut。垂直搜索。人工智能。

特色图像：QAOA-最热（带热启动）和标准 QAOA 的性能作为理想（虚线）和噪声模拟（点线）的 QAOA 深度的函数。 对于所选的 20 节点图，GW 的近似比为 0.912，而在理想情况下，QAOA-warmest 在 $p geq 2$ 上优于 GW，而标准 QAOA 要求 $p > 4$。 噪声模拟基于 IBM-Q 的 Guadalupe 设备的校准数据。

热门摘要

量子近似优化算法（QAOA）是一种用于组合优化的混合量子经典技术，有望比任何经典优化器更强大。 在这项工作中，我们举例说明了它在基本组合优化问题（称为 Max-Cut）上的潜力，其中最好的经典算法是 Goemans 和 Williamson (GW) 的算法。 我们通过将经典获得的热启动引入到 QAOA 中并使用修改后的混合算子来实现这一点，并通过计算表明这优于 GW。 我们对量子算法进行适当修改，以保持与量子绝热计算的联系； 我们讨论理论并提供数字和实验证据来证明我们的方法的前景。

►BibTeX数据

►参考

[1] 约翰·普雷斯基尔。 “NISQ 时代及以后的量子计算”。 量子 2, 79 (2018)。
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] 阿拉姆·W·哈罗 (Aram W. Harrow) 和阿什利·蒙塔纳罗 (Ashley Montanaro)。 “量子计算霸权”。 自然 549, 203–209 (2017)。
https：/ / doi.org/10.1038/nature23458

[3] 爱德华·法尔希、杰弗里·戈德斯通和萨姆·古特曼。 “量子近似优化算法”（2014）。

[4] 伊恩·邓宁、斯瓦蒂·古普塔和约翰·西尔伯霍兹。 “什么时候最有效？ 对 Max-Cut 和 QUBO 启发式的系统评估”。 INFORMS 计算杂志 30 (2018)。
https：/ / doi.org/ 10.1287 / ijoc.2017.0798

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

[6] 塞缪尔·布雷尔和雷纳托·DC·蒙泰罗。 “一种通过低阶因式分解求解半定程序的非线性规划算法”。 数学规划 95, 329–357 (2003)。
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

[7] Héctor Abraham、AduOffei、Rochisha Agarwal、Ismail Yunus Akhalwaya、Gadi Aleksandrowicz 等。 “Qiskit：量子计算的开源框架”（2019）。

[8] 玛德琳·凯恩、爱德华·法希、萨姆·古特曼、丹尼尔·拉纳德和尤金·唐。 “QAOA 从一根好的古典弦开始就陷入困境”（2022）。

[9] 丹尼尔·J·艾格、雅库布·马雷切克和斯特凡·沃尔纳。 “热启动量子优化”。 量子 5, 479 (2021)。
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack、Raimel A Medina、Richard Kueng 和 Maksym Serbyn。 “具有保证改进的量子近似优化算法的递归贪婪初始化”。 物理评论 A 107, 062404 (2023)。
https：/ / doi.org/ 10.1103 / PhysRevA.107.062404

[11] 斯特凡·H·萨克 (Stefan H Sack) 和马克西姆·瑟宾 (Maksym Serbyn)。 “量子近似优化算法的量子退火初始化”。 量子 5, 491 (2021)。
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou、王胜涛、Soonwon Choi、Hannes Pichler 和 Mikhail D Lukin。 “量子近似优化算法：性能、机制和近期设备上的实现”。 物理评论 X 10, 021067 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevX.10.021067

[13] 鲁斯兰·谢杜林、菲利普·C·洛肖、杰弗里·拉尔森、詹姆斯·奥斯特罗夫斯基和特拉维斯·S·亨布尔。 “加权 maxcut 的量子近似优化的参数传递”。 ACM 量子计算汇刊 4, 1–15 (2023)。
https：/ / doi.org/10.1145/ 3584706

[14] 阿列克谢·加尔达、刘晓媛、丹尼洛·雷科夫、尤里·阿列克谢耶夫和伊利亚·萨夫罗。 “随机图之间最佳 QAOA 参数的可传递性”。 2021 年 IEEE 国际量子计算与工程会议 (QCE)。 第 171-180 页。 IEEE（2021）。
https：/ / doi.org/ 10.1109 / QCE52317.2021.00034

[15] 约翰内斯·魏登费勒、露西娅·C·瓦洛尔、朱利安·加孔、卡罗琳·托诺、卢西亚诺·贝洛、斯特凡·沃尔纳和丹尼尔·J·艾格。 “在基于超导量子位的硬件上扩展量子近似优化算法”。 量子 6, 870 (2022)。
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

[16] 菲利普·C·洛肖、Thien Nguyen、安东尼·桑塔纳、亚历山大·麦卡斯基、丽贝卡·赫尔曼、詹姆斯·奥斯特罗夫斯基、乔治·西奥普西斯和特拉维斯·S·亨布尔。 “在近期硬件上扩展量子近似优化”。 科学报告 12, 12388 (2022)。
https：/ / doi.org/ 10.1038 / s41598-022-14767-w

[17] 吉安·贾科莫·格雷斯基和安妮·Y·松浦。 “用于最大切割的 QAOA 需要数百个量子位来实现量子加速”。 科学报告 9, 1–7 (2019)。
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] 查尔斯·穆萨、亨利·卡兰德拉和维德兰·杜尼科。 “量子还是不量子：近期量子优化中的算法选择”。 量子科学与技术 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] 科林·坎贝尔和爱德华·达尔。 “最高级别的 QAOA”。 2022 年 IEEE 第 19 届软件架构同伴国际会议 (ICSA-C)。 第 141-146 页。 IEEE（2022）。
https://doi.org/10.1109/ICSA-C54293.2022.00035

[20] 丽贝卡·赫尔曼、洛娜·特里弗特、詹姆斯·奥斯特罗夫斯基、菲利普·C·洛肖、特拉维斯·S·亨布尔和乔治·西奥普西斯。 “QAOA 图结构对 maxcut 的影响”。 量子信息处理 20, 1–21 (2021)。
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra、Fred Jendrzejewski、Philipp Hauke 和 Daniel J Egger。 “压缩和量子近似优化”（2022）。

[22] 鲁斯兰·谢杜林、斯图尔特·哈德菲尔德、泰德·霍格和伊利亚·萨夫罗。 “经典对称性和量子近似优化算法”。 量子信息处理 20, 1–28 (2021)。
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] 乔纳森·伍尔茨和彼得·洛夫。 “Maxcut 量子近似优化算法性能保证 p> 1”。 物理评论 A 103, 042612 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevA.103.042612

[24] 爱德华·法尔希、杰弗里·戈德斯通和萨姆·古特曼。 “固定量子位架构的量子算法”（2017）。

[25] 谢尔盖·布拉维、亚历山大·克里施、罗伯特·科尼格和尤金·唐。 “对称性保护对变分量子优化的障碍”。 物理评论快报 125, 260505 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] 爱德华·法尔希、大卫·加马尼克和萨姆·古特曼。 “量子近似优化算法需要看到整个图：一个典型案例”（2020）。

[27] 谢尔盖·布拉维、亚历山大·克里施、罗伯特·科尼格和尤金·唐。 “用于近似图着色的混合量子经典算法”。 量子 6, 678 (2022)。
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] 马修·B·黑斯廷斯. “经典和量子有界深度近似算法”（2019）。

[29] 库纳尔·玛瓦哈。 “局部经典最大割算法在高周长正则图上优于 $ p= 2$ QAOA”。 量子 5, 437 (2021)。
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] 波阿斯·巴拉克和库纳尔·玛瓦哈。 “高周长图最大切割的经典算法和量子限制”（2021）。
https：///doi.org/10.4230/LIPIcs.ITCS.2022.14

[31] 鲁本·塔特、马吉德·法哈迪、克雷斯顿·赫罗德、格雷格·莫勒和斯瓦蒂·古普塔。 “通过 SDP 初始化的 QAOA 热启动来桥接经典和量子”。 ACM 量子计算交易 (2022)。
https：/ / doi.org/10.1145/ 3549554

[32] Stuart Hadfield、王志辉、Bryan O'Gorman、Eleanor G. Rieffel、Davide Venturelli 和 Rupak Biswas。 “从量子近似优化算法到量子交替算子 ansatz”。 算法 12 (2019)。
https：/ / doi.org/ 10.3390 / a12020034

[33] 王志辉、尼古拉斯·C·鲁宾、杰森·M·多米尼和埃莉诺·G·里菲尔。 “$xy$ 混合器：量子交替算子 ansatz 的分析和数值结果”。 物理。 修订版 A 101, 012320 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevA.101.012320

[34] Linghua Zhu、Ho Lun Tang、George S. Barron、FA Calderon-Vargas、Nicholas J. Mayhall、Edwin Barnes 和 Sophia E. Economou。 “在量子计算机上解决组合问题的自适应量子近似优化算法”。 物理。 修订研究 4, 033029 (2022)。
https：/ / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] 安德烈亚斯·巴特斯基和斯蒂芬·艾登本茨。 “用于 QAOA 的 Grover 混合器：将复杂性从混合器设计转移到状态准备”。 2020 年 IEEE 量子计算与工程国际会议 (QCE)。 第 72-82 页。 IEEE（2020）。
https：/ / doi.org/ 10.1109 / QCE49297.2020.00020

[36] 张江，埃莉诺·G·里菲尔，王志辉。 “使用横向场进行格罗弗非结构化搜索的近乎最佳量子电路”。 物理评论 A 95, 062317 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevA.95.062317

[37] 洛夫·格罗弗。 “一种用于数据库搜索的快速量子力学算法”。 在第 212 届年度 ACM 计算理论研讨会论文集中。 第 219-1996 页。 (XNUMX)。
https：/ / doi.org/10.1145/ 237814.237866

[38] 张寅、塞缪尔·布雷尔和雷纳托·DC·蒙泰罗。 “最大割和其他二元二次规划的 Rank-2 松弛启发式”。 SIAM 优化杂志 12, 503–521 (2001)。
https：/ / doi.org/ 10.1137 / S1052623400382467

[39] 宋梅、Theodor Misiakiewicz、Andrea Montanari 和 Roberto Imbuzeiro Oliveira。 “通过格罗腾迪克不等式解决 sdps 的同步和 maxcut 问题”。 在学习理论会议上。 第 1476-1515 页。 PMLR（2017）。
https://doi.org/10.48550/arXiv.1703.08729

[40] 奥哈斯·帕里克和凯文·汤普森。 “具有正项的 2 局部量子哈密顿量的最佳乘积状态近似”（2022）。 arXiv：2206.08342。
的arXiv：2206.08342

[41] 鲁本·泰特和斯瓦蒂·古普塔。 “Ci-qube”。 GitHub 存储库 (2021)。 网址：https://github.com/swati1729/CI-QuBe。
https://github.com/swati1729/CI-QuBe

[42] 霍华德·卡洛夫. “Goemans-Williamson MAX-CUT 算法有多好？”。 SIAM 计算杂志 29, 336–350 (1999)。
https：/ / doi.org/ 10.1137 / S0097539797321481

[43] Matthew P Harrigan、Kevin J Sung、Matthew Neeley、Kevin J Satzinger、Frank Arute、Kunal Arya、Juan Atalaya、Joseph C Bardin、Rami Barends、Sergio Boixo 等。 “平面超导处理器上非平面图问题的量子近似优化”。 自然物理学 17, 332–336 (2021)。
https：/ / doi.org/ 10.1038 / s41567-020-01105-y

[44] 谢尔盖·布拉维 (Sergey Bravyi)、莎拉·谢尔顿 (Sarah Sheldon)、阿比纳夫·坎达拉 (Abhinav Kandala)、大卫·C·麦凯 (David C. Mckay) 和杰伊·M·甘贝塔 (Jay M. Gambetta)。 “减少多量子位实验中的测量误差”。 物理。 修订版 A 103, 042605 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevA.103.042605

[45] 乔治·S·巴伦和克里斯托弗·J·伍德。 “变分量子算法的测量误差缓解”（2020）。

[46] 马丁·阿巴迪、阿什什·阿加瓦尔、保罗·巴勒姆、尤金·布雷夫多、陈志峰、克雷格·西特罗、格雷格·S·科拉多、安迪·戴维斯、杰弗里·迪恩、马蒂厄·德文、桑杰·格马瓦特、伊恩·古德费洛、安德鲁·哈普、杰弗里·欧文、迈克尔·伊萨德、贾扬清、拉法尔·约瑟夫维茨、卢卡斯·凯泽、曼朱纳斯·库德鲁尔、乔什·莱文博格、蒲公英·马内、拉贾特·蒙加、雪莉·摩尔、德里克·默里、克里斯·奥拉、迈克·舒斯特、乔纳森·施伦斯、伯努瓦·施泰纳、伊利亚·苏茨克韦尔、库纳尔·塔尔瓦、保罗·塔克、文森特·范霍克、维杰·瓦苏德万、 Fernanda Viégas、Oriol Vinyals、Pete Warden、Martin Wattenberg、Martin Wicke、Yuan Yu 和小强郑。 “TensorFlow：异构系统上的大规模机器学习”（2015 年）。

[47] 迪德里克·P·金马 (Diederik P. Kingma) 和吉米·巴 (Jimmy Ba)。 “Adam：一种随机优化方法”（2014）。

[48] 罗杰·弗莱彻。 《实用优化方法（第二版）》。 约翰·威利父子。 美国纽约州纽约市（2 年）。
https：/ / doi.org/10.1002/ 9781118723203

[49] MJD 鲍威尔. “一种通过线性插值对目标函数和约束函数进行建模的直接搜索优化方法”。 优化和数值分析进展 275, 51–67 (1994)。
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] 艾伦·J·劳布 (Alan J. Laub) “科学家和工程师的矩阵分析”。 卷 91. 暹罗。 （2005）。
https：/ / doi.org/10.1137/ 1.9780898717907

[51] 格奥尔格·弗洛贝尼乌斯. “Ueber matrizen aus nicht negativen elementen”。 普鲁士国王科学院院士档案第 456–477 页 (1912)。

[52] A. Kaveh 和 H. Rahami。 “图产品特征分解的统一方法”。 工程数值方法与生物医学应用的通讯 21, 377–388 (2005)。
https:// / doi.org/ 10.1002/ cnm.753

[53] 西蒙·斯帕卡潘. “图的笛卡尔积的连通性”。 应用数学快报 21, 682–685 (2008)。
https：///doi.org/10.1016/j.aml.2007.06.010

[54] 雅采克·冈齐奥和安德烈亚斯·格罗蒂。 “在大规模并行架构上解决具有 109 个决策变量的非线性财务规划问题”。 WIT 建模与仿真交易 43 (2006)。
https:/ / doi.org/ 10.2495/ CF060101

[55] 范 RK 钟. “谱图论”。 第 92 卷。美国数学学会。 （1997）。
https:/ / doi.org/ 10.1090/ cbms/ 092

[56] MA 尼尔森和 IL Chang。 《量子计算与量子信息：十周年纪念版》。 剑桥大学出版社，纽约。 （10）。
https：/ / doi.org/ 10.1017 / CBO9780511976667

[57] Vincent R. Pascuzzi、Andre He、Christian W. Bauer、Wibe A. de Jong 和 Benjamin Nachman。 “用于减轻量子门错误的计算有效的零噪声外推”。 物理评论 A 105, 042406 (2022)。
https：/ / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg、Zlatko K Minev、Abhinav Kandala 和 Kristan Temme。 “在噪声量子处理器上使用稀疏 pauli-lindblad 模型进行概率误差消除”。 《自然物理学》第 1–6 页 (2023)。
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] 内森·克里斯洛克、杰罗姆·马利克和弗雷德里克·鲁潘。 “BiqCrunch：解决二元二次问题的半定分支定界方法”。 ACM 数学软件汇刊 43 (2017)。
https：/ / doi.org/10.1145/ 3005345

[60] Andries E. Brouwer、Sebastian M. Cioabă、Ferdinand Ihringer 和 Matt McGinnis。 “汉明图、约翰逊图和其他具有经典参数的距离正则图的最小特征值”。 组合理论杂志，B 系列 133, 88–121 (2018)。
https：///doi.org/10.1016/j.jctb.2018.04.005

[61] 唐纳德·高德纳. “组合矩阵”。 离散数学论文选（2000）。
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

被引用

[1] Johannes Weidenfeller、Lucia C. Valor、Julien Gacon、Caroline Tornow、Luciano Bello、Stefan Woerner 和 Daniel J. Egger，“在基于超导量子位的硬件上扩展量子近似优化算法”， 量子6，870（2022）.

[2] Zichang He、Ruslan Shaydulin、Shouvanik Chakrabarti、Dylan Herman、Changhao Li、Yue Sun 和 Marco Pistoia，“初始状态和混合器之间的对齐提高了约束投资组合优化的 QAOA 性能”， 的arXiv：2305.03857, (2023).

[3] V. Vijendran、Aritra Das、Dax Enshan Koh、Syed M. Assad 和 Ping Koy Lam，“低深度量子优化的富有表现力的 Ansatz”， 的arXiv：2302.04479, (2023).

[4] Andrew Vlasic、Salvatore Certo 和 Anh Pham，“补充 Grover 的搜索算法：振幅抑制实现”， 的arXiv：2209.10484, (2022).

[5] Mara Vizzuso、Gianluca Passarelli、Giovanni Cantele 和 Procolo Lucignano，“数字化反非绝热 QAOA 的收敛：电路深度与自由参数”， 的arXiv：2307.14079, (2023).

[6] Phillip C. Lotshaw、Kevin D. Battles、Bryan Gard、Gilles Buchs、Travis S. Humble 和 Creston D. Herold，“应用于量子近似优化的全局 Mølmer-Sørensen 相互作用中的噪声建模”， 物理评论A 107 6，062406（2023）.

[7] 王国明，《经典增强量子优化算法》， 的arXiv：2203.13936, (2022).

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

On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2023-09-27 01:31:17）。

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

时间戳记：

更多来自 量子杂志