加权问题的量子近似优化中的参数设置

加权问题的量子近似优化中的参数设置

时间戳记：18年2024月7日，凌晨23:XNUMX
源节点： 3070550

什里·哈里·苏雷什巴布1, 迪伦·赫尔曼1, 鲁斯兰·谢杜林1若昂·巴索2, 舒瓦尼克·查克拉巴蒂1, 孙悦1和马可·皮斯托亚1

1全球技术应用研究，摩根大通，纽约，NY 10017
2加州大学数学系，伯克利，CA 94720

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

抽象

量子近似优化算法（QAOA）是解决量子计算机上组合优化问题的领先候选算法。然而，在许多情况下，QAOA 需要计算密集型参数优化。在加权问题的情况下，参数优化的挑战尤其严峻，因为相位算子的特征值是非整数，并且 QAOA 能量景观不是周期性的。在这项工作中，我们开发了应用于一般类别加权问题的 QAOA 参数设置启发式方法。首先，我们推导出 QAOA 的最佳参数，深度 $p=1$ 应用于不同权重假设下的加权 MaxCut 问题。特别是，我们严格证明了传统观点，即在平均情况下，接近零的第一个局部最优值给出了全局最优的 QAOA 参数。其次，对于 $pgeq 1$，我们证明加权 MaxCut 的 QAOA 能量景观在简单的参数调整下接近未加权情况。因此，我们可以使用之前为未加权 MaxCut 获得的参数来解决加权问题。最后，我们证明，对于 $p=1$，QAOA 目标急剧集中于其期望，这意味着我们的参数设置规则对于随机加权实例具有很高的概率。我们在一般加权图上对这种方法进行了数值验证，结果表明，平均而言，所提出的固定参数的 QAOA 能量与优化参数的 QAOA 能量仅相差 1.1 个百分点。第三，我们提出了一种受加权 MaxCut 分析结果启发的通用启发式重新缩放方案，并使用 QAOA 和应用于投资组合优化问题的 XY Hamming 保重混合器证明了其有效性。我们的启发式改进了局部优化器的收敛性，平均减少了 7.4 倍的迭代次数。

特色图片：将最佳 QAOA 参数从 Sherrington-Kirkpatrick (SK) 模型转移到相同大小的正则图上的加权 MaxCut 问题的过程。 $gamma^{text{inf}}$ 参数根据所提出的方法进行缩放，而 $beta^{text{inf}}$ 是固定的。该图显示，采用新颖的缩放技术的 QAOA 比现有技术实现了更高的近似比，并且与优化参数相当。

热门摘要

这项工作研究了 QAOA 的参数设置规则，QAOA 是一种领先的量子启发式算法，应用于一般类型的组合优化问题。参数优化是近期应用的一个重要瓶颈。提出了一种用于在加权问题实例之间传输 QAOA 参数的通用参数缩放启发式方法，并给出了显示该过程在 MaxCut 上的有效性的严格结果。此外，数值显示该过程显着减少了用于投资组合优化的 QAOA 训练时间，这是金融工程中的一个重要问题

►BibTeX数据

►参考

[1] 迈克尔·A·尼尔森和艾萨克·L·庄。 “量子计算和量子信息”。剑桥大学出版社。 （2010）。
https：/ / doi.org/ 10.1017 / CBO9780511976667

[2] 迪伦·赫尔曼、科迪·古金、刘晓媛、阿列克谢·加尔达、伊利亚·萨夫罗、孙悦、马可·皮斯托亚和尤里·阿列克谢耶夫。 “金融量子计算调查”（2022 年）。网址：https://doi.org/10.48550/arXiv.2201.02773。
https://doi.org/10.48550/arXiv.2201.02773

[3] 泰德·霍格和德米特里·波特诺夫。 “量子优化”。信息科学 128, 181–197 (2000)。
https:/​/​doi.org/​10.1016/​s0020-0255(00)00052-9

[4] 爱德华·法尔希、杰弗里·戈德斯通和萨姆·古特曼。 “量子近似优化算法”（2014）。 网址：https://doi.org/10.48550/arXiv.1411.4028。
https://doi.org/10.48550/arXiv.1411.4028

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

[6] 萨米·布勒布纳和阿什利·蒙塔纳罗。 “使用量子近似优化算法解决布尔可满足性问题”（2022）。网址：https://doi.org/10.48550/arXiv.2208.06909。
https://doi.org/10.48550/arXiv.2208.06909

[7] 若昂·巴索、爱德华·法尔希、库纳尔·玛瓦哈、本杰明·维拉隆加和 Leo Zhou。 “大周长正则图和谢林顿-柯克帕特里克模型上 maxcut 的高深度量子近似优化算法”。量子计算、通信和密码学理论会议论文集 7, 1–21 (2022)。
https://doi.org/10.4230/LIPICS.TQC.2022.7

[8] 马修·B·黑斯廷斯。 “一种经典算法，在高周长最大切割方面也击败了 $frac{1}{2}+frac{2}{pi}frac{1}{sqrt{d}}$”（2021 年）。网址：https://doi.org/10.48550/arXiv.2111.12641。
https://doi.org/10.48550/arXiv.2111.12641

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

[10] 萨米·布勒布纳、泽维尔·卢卡斯、艾格尼丝·梅德、斯坦尼斯瓦夫·阿达谢夫斯基和阿什利·蒙塔纳罗。 “使用量子近似优化算法进行肽构象采样”。 npj 量子信息 9, 70 (2023)。网址：https://doi.org/10.1038/s41534-023-00733-5。
https:/​/​doi.org/​10.1038/​s41534-023-00733-5

[11] 塞巴斯蒂安·布兰德霍费尔、丹尼尔·布劳恩、凡妮莎·德恩、格哈德·赫尔斯特恩、马蒂亚斯·赫尔斯、季彦军、伊利亚·波利安、阿曼迪普·辛格·巴蒂亚和托马斯·韦伦斯。 “使用 qaoa 对投资组合优化的性能进行基准测试”。量子信息处理 22, 25 (2022)。
https:/​/​doi.org/​10.1007/​s11128-022-03766-5

[12] 萨米·布勒布纳和阿什利·蒙塔纳罗。 “从无限大小限制中预测最大切割的量子近似优化算法的参数”（2021）。网址：https://doi.org/10.48550/arXiv.2110.10685。
https://doi.org/10.48550/arXiv.2110.10685

[13] 爱德华·法尔希、杰弗里·戈德斯通、萨姆·古特曼和周利奥。 “量子近似优化算法和无限尺寸的 Sherrington-Kirkpatrick 模型”。量子 6, 759 (2022)。
https:/​/​doi.org/​10.22331/​q-2022-07-07-759

[14] Amir Dembo、Andrea Montanari 和 Subhabrata Sen。“稀疏随机图的极值切割”。概率年鉴 45 (2017)。
https:///​doi.org/​10.1214/​15-aop1084

[15] 加文·E·克鲁克斯. “量子近似优化算法在最大割问题上的性能”（2018）。网址：https://doi.org/10.48550/arXiv.1811.08419。
https://doi.org/10.48550/arXiv.1811.08419

[16] 迈克尔·斯特里夫和马丁·莱布。 “在不访问量子处理单元的情况下训练量子近似优化算法”。 量子科学与技术 5, 034008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8c2b

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

[18] 鲁斯兰·谢杜林、伊利亚·萨弗罗和杰弗里·拉尔森。 “量子近似优化的多启动方法”。在 IEEE 高性能极限计算会议上。第 1-8 页。 （2019）。
https://doi.org/10.1109/hpec.2019.8916288

[19] 李新伟、斋藤义幸、蔡东升、浅井伸义。 “量子近似优化算法的参数固定策略”。 2021 年 IEEE 量子计算与工程国际会议 (QCE) (2021)。
https://doi.org/10.1109/qce52317.2021.00016

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

[21] 奥哈德·阿莫西、塔穆兹·但泽、伊利·波拉特、加尔·切奇克和阿迪·马克马尔。 “使用神经网络的免迭代量子近似优化算法”（2022）。网址：https://doi.org/10.48550/arXiv.2208.09888。
https://doi.org/10.48550/arXiv.2208.09888

[22] Danylo Lykov、Roman Schutski、Alexey Galda、Valeri Vinokur 和 Yuri Alexeev。 “具有步进并行化的张量网络量子模拟器”。 2022 年 IEEE 量子计算与工程国际会议 (QCE)。 第 582-593 页。 (2022)。
https：/ / doi.org/ 10.1109 / QCE53715.2022.00081

[23] 马蒂亚·梅德维多维奇和朱塞佩·卡里奥。 “量子近似优化算法的经典变分模拟”。 npj 量子信息 7 (2021)。
https：/ / doi.org/ 10.1038 / s41534-021-00440-z

[24] 鲁斯兰·谢杜林 (Ruslan Shaydulin) 和斯特凡·M·怀尔德 (Stefan M. Wild)。 “利用对称性降低了 QAOA 的训练成本”。 IEEE 量子工程汇刊 2, 1–9 (2021)。
https：///doi.org/10.1109/tqe.2021.3066275

[25] 鲁斯兰·谢杜林和尤里·阿列克谢耶夫。 “评估量子近似优化算法：案例研究”。第十届国际绿色与可持续计算会议（2019）。
https:/ / doi.org/ 10.1109/ IGSC48788.2019.8957201

[26] 费尔南多·G·S·L·布兰达奥、迈克尔·布劳顿、爱德华·法希、萨姆·古特曼和哈特穆特·内文。 “对于固定控制参数，量子近似优化算法的目标函数值集中于典型实例”（2018）。网址：https://doi.org/10.48550/arXiv.1812.04170。
https://doi.org/10.48550/arXiv.1812.04170

[27] V. Akshay、D. Rabinovich、E. Campos 和 J. Biamonte。 “量子近似优化中的参数集中”。物理评论 A 104 (2021)。
https://doi.org/10.1103/physreva.104.l010401

[28] 菲利普·C·洛肖、特拉维斯·S·亨布尔、丽贝卡·赫尔曼、詹姆斯·奥斯特罗夫斯基和乔治·西奥普斯。 “量子近似优化的经验性能界限”。量子信息处理 20, 403 (2021)。
https:/​/​doi.org/​10.1007/​s11128-021-03342-3

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

[30] 李新伟、谢宁一、蔡东升、斋藤义行和浅井伸义。 “量子近似优化算法的深度渐进初始化策略”。数学 11, 2176 (2023)。
https:///​doi.org/​10.3390/​math11092176

[31] Sami Khairy、Ruslan Shaydulin、Lukasz Cincio、Yuri Alexeev 和 Prasanna Balaprakash。 “学习优化变分量子电路以解决组合问题”。 AAAI 人工智能会议论文集 34, 2367–2375 (2020)。
https：/ / doi.org/ 10.1609 / aaai.v34i03.5616

[32] Guillaume Verdon、Michael Broughton、Jarrod R. McClean、Kevin J. Sung、Ryan Babbush、张江、Hartmut Neven 和 Masoud Mohseni。 “通过经典神经网络学习量子神经网络”（2019）。网址：https://doi.org/10.48550/arXiv.1907.05415。
https://doi.org/10.48550/arXiv.1907.05415

[33] 萨米·凯里、鲁斯兰·谢杜林、卢卡斯·辛西奥、尤里·阿列克谢耶夫和普拉萨娜·巴拉普拉卡什。 “基于强化学习的组合问题的变分量子电路优化”（2019）。网址：https://doi.org/10.48550/arXiv.1911.04574。
https://doi.org/10.48550/arXiv.1911.04574

[34] Matteo M. Wauters、Emanuele Panizon、Glen B. Mbeng 和 Giuseppe E. Santoro。 “强化学习辅助量子优化”。物理评论研究 2 (2020)。
https：///doi.org/10.1103/physrevresearch.2.033446

[35] 马哈布布尔·阿拉姆、阿卜杜拉·阿什-萨基和斯瓦鲁普·戈什。 “使用机器学习加速量子近似优化算法”。 2020 年欧洲设计、自动化和测试会议暨展览（日期）（2020 年）。
https://doi.org/10.23919/date48585.2020.9116348

[36] 姚家豪、琳琳和马林·布科夫。 “受反糖尿病驾驶启发的多体基态准备的强化学习”。物理评论 X 11 (2021)。
https：/ / doi.org/ 10.1103 / physrevx.11.031070

[37] 王志辉、斯图尔特·哈德菲尔德、张江和埃莉诺·G·里菲尔。 “MaxCut 的量子近似优化算法：费米子视图”。物理评论 A 97 (2018)。
https：///doi.org/10.1103/physreva.97.022304

[38] 乔纳森·伍尔茨和丹尼洛·雷科夫。 “常规 MaxCut 图上 QAOA 的固定角度猜想”（2021）。网址：https://doi.org/10.48550/arXiv.2107.00677。
https://doi.org/10.48550/arXiv.2107.00677

[39] 斯图尔特·哈德菲尔德. “科学计算和近似优化的量子算法”（2018）。网址：https://doi.org/10.48550/1805.03265。
https：/ / doi.org/10.48550/ 1805.03265

[40] 保罗·格拉瑟曼. “金融工程中的蒙特卡罗方法”。第 53 卷。施普林格。 （2004）。
https:/​/​doi.org/​10.1007/​978-0-387-21617-1

[41] 沃尔特·鲁丁. “真实而复杂的分析”。麦格劳-希尔。 （1974）。

[42] 沃尔特·鲁丁. 《数学分析原理》。麦格劳-希尔。 （1976）。

[43] 科林·麦克迪阿米德。 《论有界差异法》。第 148–188 页。伦敦数学会讲座系列。剑桥大学出版社。 （1989）。
https：/ / doi.org/ 10.1017 / CBO9781107359949.008

[44] 卢茨·沃恩克。 “关于典型有界差异的方法”。组合学、概率和计算 25, 269–299 (2016)。
https：/ / doi.org/ 10.1017 / S0963548315000103

[45] 罗曼·维尔希宁。 “高维概率：数据科学应用简介”。剑桥统计与概率数学系列。剑桥大学出版社。 （2018）。
https：/ / doi.org/10.1017/ 9781108231596

[46] 若昂·巴索、大卫·加马尼克、宋梅和周利奥。 “QAOA 在大型稀疏超图和自旋玻璃模型上的恒定水平的性能和局限性”。 2022 年 IEEE 第 63 届计算机科学基础年度研讨会 (FOCS) (2022)。
https:///doi.org/10.1109/focs54457.2022.00039

[47] G帕里西。 “自旋玻璃 s-k 模型的一系列近似解”。物理学杂志 A：数学与一般 13，L115 (1980)。
https:/​/​doi.org/​10.1088/​0305-4470/​13/​4/​009

[48] 米歇尔·塔拉格兰. “帕里西公式”。数学年鉴（2006）。
https：///doi.org/10.4007/annals.2006.163.221

[49] 德米特里·潘琴科。 “谢林顿-柯克帕特里克模型”。施普林格科学与商业媒体。 （2013）。
https:/​/​doi.org/​10.1007/​978-1-4614-6289-7

[50] 鲁斯兰·谢杜林 (Ruslan Shaydulin)、库纳尔·玛瓦哈 (Kunal Marwaha)、乔纳森·伍尔茨 (Jonathan Wurtz) 和菲利普·C·洛肖 (Phillip C Llotshaw)。 “QAOAKit：用于可重复研究、应用和验证 QAOA 的工具包”。第二届国际量子计算软件研讨会（2021 年）。
https://doi.org/10.1109/QCS54837.2021.00011

[51] 若昂·巴索、爱德华·法尔希、库纳尔·玛瓦哈、本杰明·维拉隆加和 Leo Zhou。 “大周长正则图和谢林顿-柯克帕特里克模型上 maxcut 的高深度量子近似优化算法”（2021）。网址：https://doi.org/10.48550/arXiv.2110.14206。
https://doi.org/10.48550/arXiv.2110.14206

[52] 迪伦·赫尔曼、鲁斯兰·谢杜林、孙悦、Shouvanik Chakrabarti、胡少涵、皮埃尔·明森、阿瑟·拉图、罗米娜·亚洛维茨基和马可·皮斯托亚。 “通过量子芝诺动力学进行约束优化”。通信物理 6, 219 (2023)。
https:/​/​doi.org/​10.1038/​s42005-023-01331-9

[53] N. Slate、E. Matwiejew、S. Marsh 和 J. B. Wang。 “基于量子行走的投资组合优化”。量子 5, 513 (2021)。
https:/​/​doi.org/​10.22331/​q-2021-07-28-513

[54] 马克·霍德森、布伦丹·鲁克、休·翁、大卫·加文和斯特凡·杜尔曼。 “使用量子交替算子 ansatz 进行投资组合再平衡实验”（2019）。网址：https://doi.org/10.48550/arXiv.1911.05296。
https://doi.org/10.48550/arXiv.1911.05296

[55] 郝天一、鲁斯兰·谢杜林、马可·皮斯托亚和杰弗里·拉尔森。 “在约束变分量子优化中利用约束内能量”。 2022 年 IEEE/​ACM 第三届量子计算软件 (QCS) 国际研讨会 (2022)。
https://doi.org/10.1109/qcs56647.2022.00017

[56] 何子长、Ruslan Shaydulin、Shouvanik Chakrabarti、Dylan Herman、李昌浩、孙悦和 Marco Pistoia。 “初始状态和混合器之间的对齐提高了约束优化的 qaoa 性能”。 npj 量子信息 9, 121 (2023)。
https:/​/​doi.org/​10.1038/​s41534-023-00787-5

[57] “Qiskit金融”。 https://qiskit.org/documentation/finance/。
https://qiskit.org/documentation/finance/​

[58] 史蒂文·G·约翰逊。 “NLopt 非线性优化包”（2022）。 http://github.com/stevengj/nlopt。
http://github.com/stevengj/nlopt

[59] 迈克尔·JD·鲍威尔。 “用于无导数的边界约束优化的 BOBYQA 算法”。剑桥北美报告 NA2009/​06 26 (2009)。

[60] 鲁斯兰·谢杜林 (Ruslan Shaydulin) 和斯特凡·M·怀尔德 (Stefan M. Wild)。 “内核带宽在量子机器学习中的重要性”。物理评论 A 106 (2022)。
https：///doi.org/10.1103/physreva.106.042407

[61] 阿卜杜勒卡迪尔·卡纳塔、埃文·彼得斯、Cengiz Pehlevan、斯特凡·M·怀尔德和鲁斯兰·谢杜林。 “带宽使量子内核模型能够泛化”（2022）。网址：https://doi.org/10.48550/arXiv.2206.06686。
https://doi.org/10.48550/arXiv.2206.06686

[62] 张凯宁、刘刘、谢敏秀、陶大成。 “通过深度变分量子电路中的高斯初始化逃离贫瘠的高原”。神经信息处理系统的进展。第 35 卷，第 18612–18627 页。 Curran Associates, Inc. (2022)。

被引用

[1] Dylan Herman、Cody Googin、Xiaoyuan Liu、Yue Sun、Alexey Galda、Ilya Safro、Marco Pistoia 和 Yuri Alexeev，“金融领域的量子计算”， 自然评论物理学5 8，450（2023）.

[2] Abid Khan、Bryan K. Clark 和 Norm M. Tubman，“使用张量网络预优化变分量子本征解算器”， 的arXiv：2310.12965, (2023).

[3] Igor Gaidai 和 Rebekah Herrman，“p > 1 的多角度 QAOA 性能分析”， 的arXiv：2312.00200, (2023).

[4] Dylan Herman、Ruslan Shaydulin、Yue Sun、Shouvanik Chakrabarti、Shaohan Hu、Pierre Minssen、Arthur Ra​​ttew、Romina Yalovetzky 和 ​​Marco Pistoia，“通过量子芝诺动力学进行约束优化”， 通讯物理学6 1，219（2023）.

[5] Ruslan Shaydulin、Changhao Li、Shouvanik Chakrabarti、Matthew DeCross、Dylan Herman、Niraj Kumar、Jeffrey Larson、Danylo Lykov、Pierre Minssen、Yue Sun、Yuri Alexeev、Joan M. Dreiling、John P. Gaebler、Thomas M. Gatterman 、贾斯汀·A·格伯、凯文·吉尔摩、丹·格雷什、内森·休伊特、钱德勒·V·霍斯特、胡绍瀚、雅各布·约翰森、米切尔·马瑟尼、坦纳·蒙格尔、迈克尔·米尔斯、史蒂文·A·摩西、布莱恩·内恩休斯、彼得·西格弗里德、罗米娜·亚洛维茨基，以及Marco Pistoia，“针对经典棘手问题的量子近似优化算法的缩放优势的证据”， 的arXiv：2308.02342, (2023).

[6] Filip B. Maciejewski、Stuart Hadfield、Benjamin Hall、Mark Hodson、Maxime Dupont、Bram Evert、James Sud、M. Sohaib Alam、王志辉、Stephen Jeffrey、Bhuvanesh Sundar、P. Aaron Lott、Shon Grabbe、Eleanor G Rieffel、Matthew J. Reagor 和 Davide Venturelli，“使用数十个超导量子位和数千个门来设计和执行密集伊辛优化问题的量子电路”， 的arXiv：2308.12423, (2023).

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

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

On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2024-01-19 00:28:44）。

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

时间戳记：

更多来自 量子杂志