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

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）组合优化的变分启发式

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

最后，我们把注意力放在设计方法上，以解决基本的数据移植问题。