1摩根大通
2IBM Quantum，IBM Research –苏黎世
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
在本文中，作为特例，我们讨论了约束多项式二进制优化（CPBO）问题的Grover自适应搜索（GAS），尤其是二次无约束二进制优化（QUBO）问题。 与蛮力搜索相比，GAS可以为组合优化问题提供二次加速。 但是，这需要开发高效的预言机来表示问题和满足某些搜索条件的标记状态。 通常，这可以使用量子算术来实现，但是，就Toffoli门以及所需的辅助量子位而言，这是昂贵的，这在短期内可能会被禁止。 在这项工作中，我们开发了一种使用GAS算法构造有效的Oracle解决CPBO问题的方法。 我们使用在真实量子硬件上获得的仿真和实验结果证明了这种方法以及投资组合优化问题（即QUBO）的潜在加速。 但是，我们的方法适用于高阶多项式目标函数以及约束优化问题。
特色图片：GAS两次迭代的输出概率在真实的量子硬件上运行，并且使用Grover运算符分别应用了阈值$ y $和$ r $。 有效的测量结果以蓝色显示，而无效的测量结果以灰色显示。
热门摘要
►BibTeX数据
►参考
[1] 洛夫·格罗弗（Lov K. 一种用于数据库搜索的快速量子力学算法。 在第二十八届ACM年度计算机理论研讨会论文集中，STOC '96，第212-219页，纽约，纽约，美国，1996年。ACM。 ISBN 0-89791-785-5。 10.1145 / 237814.237866。
https：/ / doi.org/10.1145/ 237814.237866
[2] 彼得·W·舒尔用于量子计算机上素数分解和离散对数的多项式时间算法。 SIAM计算杂志，26（5）：1484-1509，1997年1095月。ISSN7111-10.1137。 0097539795293172 / sXNUMX。
https：/ / doi.org/ 10.1137 / s0097539795293172
[3] BP Lanyon，JD Whitfield，GG Gillett，ME Goggin，MP Almeida，I.Kassal，JD Biamonte，M.Mohseni，BJ Powell，M.Barbieri等。 在量子计算机上迈向量子化学。 Nature Chemistry，2（2）：106-111，2010年1755月。ISSN4349-10.1038。 483 / nchem.XNUMX。
https：///doi.org/10.1038/nchem.483
[4] Aram W. Harrow，Avinatan Hassidim和Seth Lloyd。 线性方程组的量子算法。 物理评论快报，103（15），2009年1079月。ISSN7114-10.1103。 103.150502 / physrevlett.XNUMX。
https：///doi.org/10.1103/physrevlett.103.150502
[5] 卡洛斯·布拉沃·普里托（Carlos Bravo-Prieto），瑞安·拉罗斯（Ryan LaRose），塞雷佐（M. 变分量子线性求解器，2020年.URL https://arxiv.org/abs/1909.05820。
的arXiv：1909.05820
[6] Patrick Rebentrost，Brajesh Gupt和Thomas R.Bromley。 量子计算金融：金融衍生工具的蒙特卡洛定价。 物理Rev.A，98：022321，2018年10.1103月.98.022321 / PhysRevA.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevA.98.022321
[7] Stefan Woerner和Daniel J.Egger。 量子风险分析。 npj Quantum Information，5：15，2019 / s10.1038-41534-019-0130。
https://doi.org/10.1038/s41534-019-0130-6
[8] DJ Egger，R。Garcia Gutierrez，J。Cahue Mestre和S. Woerner。 使用量子计算机的信用风险分析。 IEEE电脑事务，第1-1页，2020年.10.1109 / TC.2020.3038063。
https：///doi.org/10.1109/TC.2020.3038063
[9] Nikitas Stamatopoulos，Daniel J.Egger，Sun Sun，Christa Zoufal，Raban Iten，Ning Shen和Stefan Woerner。 使用量子计算机的期权定价。 Quantum，4：291，2020年2521月。ISSN327-10.22331X。 2020 / q-07-06-291-XNUMX。
https://doi.org/10.22331/q-2020-07-06-291
[10] 爱德华·法西，杰弗里·戈德斯通和山姆·古特曼。 量子近似优化算法，2014年.URL https://arxiv.org/abs/1411.4028。
的arXiv：1411.4028
[11] Alberto Peruzzo，Jarrod McClean，Peter Shadbolt，Man Hong Yung，Xia Qi Zhou，Peter J.Love，AlánAspuru-Guzik和Jeremy L.O'Brien。 光子量子处理器上的变分特征值求解器。 Nature Communications，5：4213，2014.ISSN 20411723 / ncomms10.1038。
https：///doi.org/10.1038/ncomms5213
[12] 贾科莫·南尼西尼（Giacomo Nannicini）。 组合优化的混合量子经典变分启发法的性能。 物理评论E，99：013304，2019年10.1103月.99.013304 / PhysRevE.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevE.99.013304
[13] 帕纳吉奥蒂斯（Panagiotis Kl。） Barkoutsos，Giacomo Nannicini，Anton Robert，Ivano Tavernelli和Stefan Woerner。 使用cvar改进变分量子优化。 量子，4：256，2020年2521月.ISSN 327-10.22331X。 2020 / q-04-20-256-XNUMX。
https://doi.org/10.22331/q-2020-04-20-256
[14] L. Braine，DJ Egger，J。Glick和S. Woerner。 用于交易结算的混合二进制优化的量子算法。 IEEE Transactions on Quantum Engineering，2：1–8，2021 / TQE.10.1109。
https：///doi.org/10.1109/TQE.2021.3063635
[15] Andrew M Childs，Edward Farhi和John Preskill。 绝热量子计算的鲁棒性。 物理评论A，65（1）：012322，2001 / PhysRevA.10.1103。
https：/ / doi.org/ 10.1103 / PhysRevA.65.012322
[16] Mark W Johnson，Mohammad HS Amin，Suzanne Gildert，Trevor Lanting，Firas Hamze，Neil Dickson，Richard Harris，Andrew J Berkley，Jan Johansson，Paul Bunyk等。 用制造的自旋进行量子退火。 Nature，473（7346）：194–198，2011 / nature10.1038。
https：/ / doi.org/10.1038/nature10012
[17] 克里斯托弗·杜尔（ChristophDürr）和彼得·霍耶（PeterHøyer）。 一种寻找最小值的量子算法，1996年.URL https://arxiv.org/abs/quant-ph/9607014。
arXiv：quant-ph / 9607014
[18] D. Bulger，WP Baritompa和GR Wood。 使用grover的量子算法实现纯自适应搜索。 优化理论与应用杂志，116（3）：517–529，2003年1573月。ISSN2878-10.1023。 1023061218864 / A：XNUMX
https：/ / doi.org/ 10.1023 / A：1023061218864
[19] WP Baritompa，DW Bulger和GR Wood。 Grover的量子算法应用于全局优化。 SIAM J. on Optimization，15（4）：1170-1184，2005年1052月。ISSN6234-10.1137。 040605072 / XNUMX。
https：/ / doi.org/10.1137/ 040605072
[20] 奥斯汀·吉利亚姆（Austin Gilliam），夏琳·芬奇（Charlene Venci），斯雷拉曼·穆拉利达拉恩（Sreraman Muralidharan），维塔利·杜伦（Vitaliy Dorum），埃里克·梅（Eric May），拉杰什·纳拉辛汉（Rajesh Narasimhan）和君士坦丁·冈西里阿（Constantin Gonciulea）。 高效量子计算的基础模式，2019年.URL https://arxiv.org/abs/1907.11513。
的arXiv：1907.11513
[21] 托马斯·德雷珀（Thomas G. 在量子计算机上添加，2000.URL https://arxiv.org/abs/quant-ph/0008033。
arXiv：quant-ph / 0008033
[22] RománOrús，Samuel Mugel和Enrique Lizaso。 金融量子计算：概述和前景。 物理评论，4年100028月，2019：2405.ISSN 4283-10.1016。 2019.100028 / j.revip.XNUMX。
https：///doi.org/10.1016/j.revip.2019.100028
[23] 丹尼尔·艾格（Daniel J. 金融业的量子计算：最新技术和未来前景。 IEEE Transactions on Quantum Engineering，1：1–24，2020a。 ISSN 2689-1808。 10.1109 / tqe.2020.3030314。
https：///doi.org/10.1109/tqe.2020.3030314
[24] 帕特里克·伦本斯特（Patrick Rebentrost）和塞思·劳埃德（Seth Lloyd）。 量子计算金融：用于投资组合优化的量子算法，2018年.URL https://arxiv.org/abs/1811.03975。
的arXiv：1811.03975
[25] Davide Venturelli和Alexei Kondratyev。 投资组合优化问题的反向量子退火方法。 量子机器智能，1年2019月.10.1007 / s42484-019-00001-w。
https：/ / doi.org/ 10.1007 / s42484-019-00001-w
[26] Daniel J. Egger，Jakub Marecek和Stefan Woerner。 暖启动量子优化，2020b。 网址https：///arxiv.org/abs/2009.10095。
的arXiv：2009.10095
[27] 赫克托·亚伯拉罕（HéctorAbraham）等。 等Qiskit：量子计算的开源框架。 2019 / zenodo.10.5281。
https：///doi.org/10.5281/zenodo.2562110
[28] 米歇尔·莫斯卡（Michele Mosca）。 通过特征向量分析进行量子搜索，计数和幅度放大。 90年，计算机科学数学基础研讨会，随机算法学报，第100-1998页.URL https://eccc.weizmann.ac.il/resources/pdf/moscafi.pdf。
https：// https：//eccc.weizmann.ac.il/resources/pdf/moscafi.pdf
[29] Gilles Brassard，Peter Hoyer，Michele Mosca和Alain Tapp。 量子幅度放大和估计。 当代数学，305，2002 / conm / 10.1090。
https：/ / doi.org/ 10.1090 / conm / 305
[30] 铃木洋一（Yohichi Suzuki），尚平Uno（Shumpei Uno），鲁迪·雷蒙德（Rudy Raymond），田中智树（Tomoki Tanaka），田宫田宫（Tamiya Onodera）和山本直树（Naoki Yamamoto）。 没有相位估计的幅度估计。 量子信息处理，19（2），2020年1573月.ISSN 1332-10.1007。 11128 / s019-2565-2-XNUMX。
https://doi.org/10.1007/s11128-019-2565-2
[31] 斯科特·亚伦森（Scott Aaronson）和帕特里克·拉尔（Patrick Rall）。 量子近似计数，简化。 算法简化研讨会，第24-32页，2020年10.1137月.1.9781611976014.5 / XNUMX。
https：/ / doi.org/10.1137/ 1.9781611976014.5
[32] Michel Boyer，Gilles Brassard，PeterHøyer和Alain Tapp。 量子搜索的严格界限。 物理物理学报，46（4-5）：493-505，1998年1521月。ISSN3978-10.1002。 1521 /（SICI）3978-199806（46）4：5 / ‐493 <493 :: AID-PROP3.0> 2.CO; XNUMX-P。
[33] 本杰明·巴兰（BenjamínBarán）和马科斯·维拉格拉（Marcos Villagra）。 多目标优化Grover自适应搜索，第191–211页。 Springer International Publishing，Cham，2019年。ISBN978-3-319-99648-6。 10.1007 / 978-3-319-99648-6_11。
https://doi.org/10.1007/978-3-319-99648-6_11
[34] Yunseong Nam，Yuan Su和Dmitri Maslov。 具有o（n log（n））t个门的近似量子傅立叶变换。 npj量子信息，6（1），2020年2056月.ISSN 6387-10.1038。 41534 / s020-0257-5-XNUMX。
https://doi.org/10.1038/s41534-020-0257-5
[35] 史蒂文·库卡罗（Steven A. Cuccaro），托马斯·德雷珀（Thomas G.Draper），塞缪尔·库丁（Samuel A. 一个新的带有量子纹波的加法电路，2004年.URL https://arxiv.org/abs/quant-ph/0410184。
arXiv：quant-ph / 0410184
[36] Thomas G. Draper，Samuel A. Kutin，Eric M. Rains和Krysta M. Svore。 对数深度量子超前超前加法器。 量子信息计算，6（4）：351-369，2006年1533月。ISSN7146-10.26421。 6.4 / QIC5-4-XNUMX。
https：/ / doi.org/ 10.26421 / QIC6.4-5-4
[37] 克雷格·吉尼（Craig Gidney）。 将量子加成的成本减半。 Quantum，2:74，2018年2521月.ISSN 327-10.22331X。 2018 / Q-06-18-74-XNUMX。
https://doi.org/10.22331/q-2018-06-18-74
[38] Andrew W. Cross，Lev S. Bishop，Sarah Sheldon，Paul D. Nation和Jay M. Gambetta。 使用随机模型电路验证量子计算机。 物理评论A，100（3），2019年2469月.ISSN 9934-10.1103。 100.032328 / physreva.XNUMX。
https：///doi.org/10.1103/physreva.100.032328
[39] A. Dewes，FR Ong，V.Schmitt，R.Lauro，N.Boulant，P.Bertet，D.Vion和D.Esteve。 具有单个单次qubit读数的双转门处理器的特性。 物理Rev.Lett。，108：057002，2012年10.1103月.108.057002 / PhysRevLett.XNUMX。
https：/ / doi.org/ 10.1103 / PhysRevLett.108.057002
[40] 斯万特·詹森（Svante Janson）。 伽玛类型的时刻和布朗至上过程区域。 Probab。 Surveys，7：1–52，2010 / ‐10.1214-PS10。
https：/ / doi.org/ 10.1214 / 10-PS160
[41] 迈克尔·尼尔森（Michael A.Nielsen）和艾萨克·庄（Isaac L.Chuang）。 量子计算和量子信息：十周年纪念版。 剑桥大学出版社，纽约，美国纽约，10年第10版.ISBN 2011，1107002176 / CBO9781107002173。
https：/ / doi.org/ 10.1017 / CBO9780511976667
被引用
[1] Daniel J. Egger，Claudio Gambella，Jakub Marecek，Scott McFaddin，Martin Mevissen，Rudy Raymond，Andrea Simonetto，Stefan Woerner和Elena Yndurain，“金融的量子计算：最新的技术和未来的前景”， 的arXiv：2006.14510.
[2] Claudio Gambella和Andrea Simonetto，“经典和量子计算机上用于混合二进制优化的多块ADMM启发式算法”， 的arXiv：2001.02069.
[3] Austin Gilliam，Marco Pistoia和Constantin Gonciulea，“使用格罗弗算法的广义版本优化量子搜索”， 的arXiv：2005.06468.
[4] Austin Gilliam，Marco Pistoia和Constantin Gonciulea，“量子甲骨文的规范构造”， 的arXiv：2006.10656.
[5] Austin Gilliam，Marco Pistoia和Constantin Gonciulea，“使用Grover算法的二项式优化量子搜索”， 的arXiv：2007.10894.
[6] Julien Gacon，Christa Zoufal，Giuseppe Carleo和Stefan Woerner，“量子Fisher信息的同时扰动随机逼近”， 的arXiv：2103.09232.
[7] Sayantan Pramanik，M Girish Chandra，Shampa Sarkar和Manoj Nambiar，“使用改进的Grover算法的近似相位搜索和本征估计”， 的arXiv：2012.11497.
[8] Su Yeon Chang，Steven Herbert，Sofia Vallecorsa，ElíasF. Combarro和Ross Duncan，“高能物理中的双参数量子电路GAN模型”， 的arXiv：2103.15470.
[9] Marika Svensson，Martin Andersson，MattiasGrönkvist，PontusVikstål，Devdatt Dubhashi，Giulia Ferrini和GöranJohansson，“一种启发式方法，通过将分支价格与量子算法相结合来解决大规模整数线性程序”， 的arXiv：2103.15433.
[10]廖一栋，谢敏秀和克里斯·费里，“用于训练量子神经网络的量子优化”， 的arXiv：2103.17047.
以上引用来自 SAO / NASA广告 （最近成功更新为2021-04-10 02:42:05）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2021-04-10 02:42:03）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
