推荐!【量子算法设计、应用】《不确定性条件下用于决策的量子计算算法》IBM、美国空军109页技术报告

2022 年 10 月 9 日 专知
量子计算在提供渐进的计算优势方面有着巨大的前景。量子算法高效的一个必要(但不是充分)条件是有目的地利用独特的量子特性(叠加、纠缠、不确定性)。现实世界的问题引入了前所未有的复杂程度。这个基础研究项目的主要目标是构思新的有效的量子算法,同时避免做出不现实的假设。

1 算法设计、实施和测试

(1)变分量子k-本征求解器

该算法的数学表述已经建立,并在IBM量子计算开发环境中的实现已经结束。该算法已经过数值测试。该算法的一个关键创新点是通过重新表述变量优化问题,将其作为一个元级优化问题,同时搜索特征值和其变量形式,从而搜索k个特征对。

(2)变异量子蒙特卡洛最小化器

该算法的数学表述已经建立,随后使用IBM量子计算开发环境进行实施,并在IBM Q量子计算机上进行实验。其中心思想是围绕着计算高阶时刻的混合量子-经典变分框架的制定。在这种框架的朴素设计中,计算第𝑝个时刻需要多项式增加𝒪(𝑑𝑝)量子设备要计算的变量项数量,其中𝑑是哈密尔顿表示中张量积项数量。建立在矩阵函数结构基础上的公式可以避免这种计算开销。

(3)鲁棒优化

鲁棒优化是量子计算的一个意料之中的候选者。鉴于决策,表征效用函数的概率分布传达了可能是无限的分布中最差的分布。我们假设决策向量𝑥和概率分布𝜉∈𝐷(𝜉̅)都可以通过参数化单元得到。这种表述包含了一个鞍点问题,对于这个问题存在经典的算法。决策向量𝑥=𝑈(𝜃)|0〉可以进行变分编码。每个元素为0或1且具有给定概率的向量可以用单层𝑌旋转进行编码;改变旋转角度直接决定了0或1的概率。向量元素之间的相关性可以用双比特纠缠门来引入。

(4)结构化马尔科夫过程

许多不同形式的不确定性问题下的决策的计算复杂性限制了这些基本问题在经典计算环境中的解决程度。这对于不确定性问题下的一般形式的决策来说尤其如此,这些问题涉及马尔科夫过程作为不确定性下系统的随机建模框架,在这个框架内必须做出决策。我们已经确定并调查了此类问题的广泛范围,我们认为这些问题对于开发不同类型的量子算法来说是很有潜力的,这些算法有可能在计算复杂性方面提供重大改进。其中一个原因是快速傅里叶变换的广泛使用,它是最先进和高效的经典计算算法的基础。另一个原因是强大的概率特性和结构,我们相信这些特性和结构可能使我们能够从第一原理中开发出更有效的量子算法。除了识别和研究这类计算问题之外,我们已经开始追求开发量子算法的两个方向,推动经典和量子计算环境之间的重大差距。

(5)量子游走

量子游走是定义在希尔伯特空间ℋ𝑠⊗ℋ𝑐中,该空间由离散位置状态ℋ𝑠和大小为2的掷硬币空间ℋ𝑐构成。因此,在每一个一次性步骤中,一枚硬币和一个移位算子执行量子随机游走演化𝑈=𝑆(𝐼⊗𝐶)。与经典随机游走相比,量子游走的独特优点是有可能开发出叠加硬币的解决方法,从而有效地同时探索多条路径。选择Hadamard门作为叠加硬币,我们可以考虑其他各种选择(平衡的或不平衡的),这将影响步行者的动态。在第3.6节中,我们描述了我们对量子游走算法的初步设计以及对硬币算子不同选择的影响。

(6)基于量子游走的群组检测

作为我们在量子算法背景下随机游走领域持续研究的一部分,扩展了与量子游走有关的算法,特别是群组检测的量子游走。我们通过使用不同的位置和硬币空间,考虑到各种硬币,包括与Hadamard硬币、Fourier硬币和Grover硬币有关的硬币,将我们原来对线上量子游走空间的定义扩展到任意的无向图。对于群组检测,经典图被一个预备电路编码为量子对象。量子随机游走电路通过反复应用游走算子(硬币算子和阶梯算子的组合)来进行群组分析。测量电路将量子信息从量子比特传递到经典世界进行分析。这种量子计算方法可以带来比经典类似物更高的多项式计算速度。

(7)结构化随机游走

除了我们在量子游走领域的持续研究(上文),还有另一类普遍而重要的随机游走值得关注,即那些具有某些结构特性的随机游走。计算这类结构化随机游走均衡分布最著名的经典算法叫做循环还原,其计算复杂度主要是在适应于结构化随机游走循环还原算法的每次迭代中需要解决多个线性方程组。在第3.5节中,我们描述了我们初步设计的用于计算结构化随机游走均衡分布的量子算法,该算法在循环还原算法的每次迭代中对这些计算复杂性瓶颈的线性系统大小提供了指数级的加速。在第4.4节中,我们进一步表明,我们对结构化随机游走的量子算法比对量子游走的相应算法提供了显著的速度提升。我们还注意到,循环还原是一些重要的数值方法的核心,远远超出了我们在这里对结构化随机游走的兴趣,因此这里设计的量子算法可以用来解决更大的一类数值问题。

(8)主动学习-量子相位估计

本研究考虑了一种变分量子相位估计(QPE)方法,它结合了与拒绝滤波和神经网络推理有关的想法。根据可用的计算资源,该方法允许在变分量子求解器(VQE)和QPE之间进行几乎连续的转换。使用混合量子经典方法的优点是,它利用每个领域的优势来获得误差ϵ和计算复杂性之间的最佳权衡。该方法的数学表述已被开发出来,并实施了一个原型算法。

(9)量子期望估计

根据主动学习的特征,将VQE与更复杂的振幅估计版本相结合,我们报告了一种新颖的无塌陷的量子振幅估计方法,它与Knill的真实和复杂提取技术一起,构成了一种新颖的量子期望估计算法。

(10)拓扑数据分析

在量子计算吸引人的应用领域中,我们发现了拓扑数据分析,特别是持久同源性领域,可以考虑大幅度(达到指数级)加速。追踪贝蒂数如何随着尺度𝞮的变化而变化,揭示了在不同的𝞮分析数据时,拓扑特征是如何产生和消失的。在许多长度尺度上持续存在的拓扑学特征可以被识别为结构化的"真正"特征:持续性同源性。在第3.8节中,我们提供了理论基础,并涵盖了诸如边界图、链复合体、同源组和复合滤波以及BarCodes等主题。在此之前,我们报告了重要的实现细节,特别是受控的变换操作的设计和实现。在此期间,我们开发了一种新的快速量子算法来计算基于切比雪夫多项式近似的贝蒂数。该方法只需要计算矩阵矩,而不需要计算矩阵的特征分解(使用QPE)。我们提出了许多数值结果,表明新方法在估计贝蒂数方面非常有效。
研究工作的另一条主线是围绕确定量子计算可以提供可行优势的应用领域。

2 已经探索的具体应用

(1)拓扑分类器

拓扑数据分析和持久同构的应用之一是在机器学习中用于分类问题。我们可以利用给定数据的拓扑学特征来训练分类器,我们称之为拓扑学分类器。我们的想法是,不同尺度上的点的贝蒂数形成了持久性的条形码。我们可以使用这些不同尺度的贝蒂数ϵ作为分类器的(拓扑)输入特征。我们展示了这些想法如何被用于数字分类。特别是,我们计算了10个数字(0-9)在不同尺度下的贝蒂数𝞮,并展示了我们如何仅用拓扑学特征来区分这些数字。

(2)定价和风险分析

定价和风险管理在金融系统中发挥着核心作用,并代表了该领域中一些计算要求最高的问题。这是由于经典蒙特卡洛模拟的收敛速度相对较慢,这往往导致大规模并行化的隔夜模拟。使用量子振幅估计,有可能建立量子算法,导致比经典蒙特卡洛模拟快4倍的速度。这可以将数以百万计的经典样本减少到数以千计的量子样本,有可能将隔夜模拟减少到接近实时应用。这可能会对金融系统产生重大影响,因为即使是边际加速也会带来巨大的好处。所研究的量子算法不仅适用于金融应用,例如,将其应用于库存管理问题也是很简单的。

(3)组合优化的变分启发式

变分方法已被应用于各种领域,如化学、机器学习、优化。通常情况下,效用函数是一个编码系统总能量的哈密顿,需要最小化。这与优化背景直接相关:同样的想法可以应用于经典的组合优化问题,只要我们能够构建一个编码优化问题的目标函数的哈密尔顿。在我们的研究中,我们采用经典的无导数优化方法来寻求这些问题的良好解决方案,并揭示了一些应该克服的限制,以提高变分方法的有效性。
最后,我们把注意力放在设计方法上,以解决基本的数据移植问题。

数据移植

(1)稀疏和窄带量子傅里叶变换

我们超越了近似的QFT,提出了一种新的稀疏QFT(SQFT)算法。该算法的构造对于理解和实现近期设备上的QFT具有吸引力。我们报告了对稀疏信号的AQFT的一种新的重述和应用。我们将该算法扩展到窄带信号,并通过采用较新的并行化版本来提高复杂性。

(2)近似量子傅里叶变换

量子傅里叶变换(QFT)是众多量子算法中的关键成分。对于大多数潜在的应用,QFT的复杂性很高,因此,降低复杂性的近似方案的潜在应用可以产生巨大的影响。
我们在几个不同的流行框架(qiskit、qutip和pyquil)上用python实现并彻底测试了均值场近似量子傅里叶变换(AQFT)。这导致了在正文中提出的一系列初步的基准测试结果。我们已经表明,与几乎线性的复杂度(与完整的QFT的立方体相反)相比,测量的波函数的误差是可以忽略的。

报告提纲

IBM量子计算算法基础研究项目的重点是为近期噪声量子系统设计可行的量子计算算法。重点是设计算法,避免采取不现实的假设,同时提供关于预期计算优势的理论严谨性。有三个主要的开发项目,如下所示:
  • 算法设计、实施和测试
  • 应用
  • 数据移植
上述的每一个项目,都涉及几个任务。
算法设计活动包括
  • 任务1.1 - 推导和设计一个综合的基于量子变分期望估计器的特征值和蒙特卡洛最小化算法
  • 任务1.2 - 使用IBM QISKit开发算法
  • 任务1.3 - 算法测试
  • 任务1.4 - 探索组合优化的变异算法的性能
  • 任务1.5 - 无空间变异特征求解器的制定和评估
  • 任务1.6 - 开发主动学习𝛽-QPE算法,结合变量量子特征解算器和量子相位估计的优势
  • 任务1.7 - 对主动学习𝛽-QPE算法进行评估
  • 任务1.8 - 完善主动学习𝛽-QPE算法
  • 任务1.9 - 对近似量子傅里叶变换算法进行分析
  • 任务1.10 - 完善近似量子傅里叶变换算法
应用范围界定活动包括对以下领域问题的探索
  • 任务2.1 - 界定与AFRL相关的现实问题,可在综合量子蒙特卡洛框架中表示出来
  • 任务2.2 - 在实际的(非容错的)量子计算机上进行性能评估
  • 任务2.3 - 设计基于量子游走的群组检测算法
  • 任务2.4 - 测试基于量子游走的群组检测算法
作为数据移植工作的一部分,开展了以下活动
  • 任务3.1 - 探讨亚线性(特别是基于草图的)经典(隐式或显式)到量子数据映射的数学计算公式
  • 任务3.2 - 涵盖理论和实施细节的技术报告
  • 任务3.3 - 在实际的量子计算机上演示算法
  • 任务3.4 - 基于𝛽-QPE算法的拓扑学特征(贝蒂数)的初步描述
  • 任务3.5 - 细化拓扑学特征(贝蒂数)的描述
  • 任务3.6 - 基于拓扑学特征的初始拓扑学分类器
  • 任务3.7 - 完善拓扑学分类器算法
本报告剩下章节将详细描述每个项目所涉及活动的摘要。
 

专知便捷查看

便捷下载,请关注专知人工智能公众号(点击上方蓝色专知关注)

  • 后台回复“QCA” 就可以获取《推荐!【量子算法设计、应用】《不确定性条件下用于决策的量子计算算法》IBM、美国空军109页技术报告》专知下载链接


                       
专知,专业可信的人工智能知识分发 ,让认知协作更快更好!欢迎注册登录专知www.zhuanzhi.ai,获取100000+AI(AI与军事、医药、公安等)主题干货知识资料!
欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程资料和与专家交流咨询
点击“ 阅读原文 ”,了解使用 专知 ,查看获取100000+AI主题知识资料
登录查看更多
3

相关内容

《通信和导航中的优化算法设计》美国空军研究实验室
专知会员服务
36+阅读 · 2022年8月19日
破旧立新:美国空军的高效决策和有效系统
专知会员服务
62+阅读 · 2022年6月8日
一种基于神经网络的策略,可增强量子模拟
机器之心
0+阅读 · 2022年10月8日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
66+阅读 · 2022年4月13日
Arxiv
56+阅读 · 2021年5月3日
CSKG: The CommonSense Knowledge Graph
Arxiv
18+阅读 · 2020年12月21日
已删除
Arxiv
32+阅读 · 2020年3月23日
VIP会员
相关VIP内容
《通信和导航中的优化算法设计》美国空军研究实验室
专知会员服务
36+阅读 · 2022年8月19日
破旧立新:美国空军的高效决策和有效系统
专知会员服务
62+阅读 · 2022年6月8日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员