科学家破解了谷歌的量子优化算法

来源：量子认知

谷歌一直在争相开发量子增强型的处理器，这种处理器使用量子力学效应来增进数据处理速度。谷歌为此的短期目标是已经设计出了一种新型的量子增强算法，可以在有真实噪声的情况下运行。所谓的量子近似优化算法（Quantum Approximate Optimisation Algorithm，简称 QAOA）是谷歌目前开发的抗噪声量子增强算法的基础。

谷歌在量子近似优化算法中采用的这一著名方法引发了广泛的商业兴趣，并激发了全球研究界探索其新颖应用的兴趣。但是，对于谷歌的量子近似优化算法的最终性能限制知之甚少。

最近，俄罗斯斯科尔科沃科技学院（Skoltech）深量子实验室（Deep Quantum Laboratory）的一组科学家应对此提出了挑战。研究团队发现并量化了谷歌广泛采用的量子算法方法中的基本限制。研究团队在论文报告中详细介绍了所发现的可达性缺陷（reachability deficits）。作者表明，这些缺陷对量子近似优化算法甚至近似解决问题的能力产生了根本性的限制。这一研究发表在最近的《物理评论通讯》上。

研究团队的发现报告了变分量子近似优化算法的明显局限性。由于其内部的从量子到经典的反馈过程，量子近似优化算法和其他变分量子算法已经证明使用已知的数学技术极其难以分析。也就是说，给定的量子计算只能运行固定的时间量。在此固定时间内，可以执行固定数量的量子运算。量子近似优化算法试图通过形成一系列越来越近的最佳逼近，以最小化目标函数来迭代利用这些量子运算。该研究发现了在该过程所体现的新的限制。

研究人员发现，对于任何固定深度的量子电路，量子近似优化算法逼近最佳解的能力从根本上取决于问题“密度”。 对于称为MAX-SAT的问题，可以将所谓的密度定义为问题约束与变量计数的比率，有时也称为子句密度（clause density）。研究人员发现了具有高密度解决方案的问题实例，这些最优解决方案无论算法的运行时间如何，都无法保证成功地近似估计。

如图所示，表示在问题密度增加的情况下，随机生成的MAX-SAT实例上固定深度量子近似优化算法电路的性能，即量子近似优化算法最优值与精确最优值之间的差异。 尽管较高深度的版本可实现更好的性能，但它们仍显示出可达性缺陷。

基于这个研究结果，看来谷歌宣称的量子至上，其支撑基础之一的量子增强算法，还不是那么乐观，还有一段更长的路要走。

介绍完了这篇研究论文，有人会觉得量子近似优化算法具体是什么还是不太清楚，下面给感兴趣的读者再进一步具体介绍一下。

量子近似优化算法是可以在近期量子计算机中实现的算法之一，并且曾被视为证明量子至上性的最有希望的算法之一。量子近似优化算法是一种近似算法，这意味着它不会提供“最准确”、“最佳”的结果，而只会提供“足够好”的结果，其特征在于达到所需要的近似率。

量子近似优化算法的数学基础之一是数学优化处理，即从一组可能的解决方案中，根据一定标准，找出问题的最佳解决方案。通常，优化问题即被表述为最小化问题，试图根据解决方案寻求最小化误差，最优解决方案具有最小误差。数学优化处理广泛应用于许多科技领域中。随着所涉及数据的复杂性和数据量的增加，需要更有效的方法来解决优化问题。

量子计算能力可以解决经典计算机上实际上不可行的问题，或者相对于经典算法而言可以大大提高速度。量子优化算法主要涉及到下面方面的基本问题。

量子数据拟合

数据拟合是构建最适合一组数据点的数学函数的过程。拟合的质量是通过某些标准，如通常是函数与数据点之间的距离来进行衡量的。

量子最小二乘拟合

数据拟合的最常见类型之一是解决最小二乘问题，以最小化数据点与拟合函数之间的平方差。许多人都知道，最小二乘法是回归分析的一种标准方法，它通过最小化每个方程式结果中的残差平方和来近似超定系统，其中

量子最小二乘拟合算法使用量子算法的线性方程组（HHL）版本，并输出系数 λ 和拟合质量估计 E。 它由三个基本部分组成：一个用于执行伪逆运算的算法，一个用于拟合质量估计的例程，以及一个用于学习拟合参数的算法。由于量子算法主要基于HHL算法，因此在以下情况下提出了指数改进。F是稀疏的，并且两者的条件数，即最大特征值与最小特征值之比 FF 和 FF 都小。

量子半定编程（Quantum semidefinite programming）

半定编程（Semidefinite programming，简称 SDP）是一种优化子区域，用于处理正半定矩阵的圆锥与仿射空间的交点上的线性目标函数，即要最小化或最大化的用户指定函数的优化。目标函数是矩阵的内积 C 作为输入与变量 X。 表示为 Sn 所有空间 n x n 对称矩阵。变量 X 必须位于正半定对称矩阵的（闭合凸）锥中。两个矩阵的内积定义为：

该问题可能具有其他约束（作为输入），通常也被表述为内积。每个约束迫使矩阵的内积，其中Ak作为输入，优化变量X小于指定值bk（作为输入）。最后，半定编程问题可以写成：

量子算法

算法输入为：A1 ... Am，C，b1 ... bm以及与关于解的迹的参数，有关精度和最佳值，即最佳点处目标函数的值有关的参数。

量子算法由几个迭代组成。在每次迭代中，它都会解决一个可行性问题，即找到满足以下条件，给出一阈值 t 的任何解决方案：

在每次迭代中，不同的阈值 t 被选择，并且算法输出解决方案 X 这样其他约束也得到满足，或表明不存在这样的解决方案。该算法执行二进制搜索以找到最小阈值 t 为此解决方案 X 仍然存在：这为半定编程问题提供了最起码的解决方案。

在一般情况下，量子算法提供了优于最佳经典算法的二次改进，而当输入矩阵的维度较低时，则会提供指数级的改进。

量子组合优化

组合优化问题旨在从一组有限的对象中找到一个最佳对象。问题可以表述为目标函数的最大值，该目标函数是布尔函数之和。每个布尔函数 Cα：{0，1} → {0，1} 作为输入 n 位字符串 = z1 z2 ...... zn 并给出一位（0或1）作为输出。 n 比特位和 m 子集的组合优化问题是寻求 n 位字符串 z，使下述函数最大化：

量子近似优化算法

对于组合优化，量子近似优化算法具有比任何已知的多项式时间经典算法，对于某个问题，具有更好的逼近率，直到提出一种更有效的经典算法。

量子近似优化算法的核心依赖于与2p角度相关的幺正算符的运用。在泛函分析中，幺正算符（unitary operator，或称酉算符）是定义在希尔伯特空间上的有界线性算符。其中，p>1 是输入整数。这些算子被迭代地应用到一个状态上，该状态是计算基础上所有可能状态的均等权重的量子叠加。在每次迭代中，状态都是在计算基础上测量的，计算C(z) 。 经过足够的重复次数后，C(z) 几乎是最佳状态，并且被测状态也接近最佳状态。

最后简单地小结一下。量子近似优化算法是否有用？量子近似优化算法是否比经典算法更好？目前答案是未知的。尽管量子近似优化算法还不可能完全肯定超越传统算法，但它确实也显示出一定的量子优越性。量子近似优化算法能够解决传统计算机无法解决的问题。换句话说，如果可以经典地模拟量子近似优化算法，则 P = NP。

最后，量子近似优化算法实施受门保真度的限制。在当前的噪声量子计算机中，p的层数很可能会导致更差的精度，因为门误差会抵消较高p的好处。但是，这并不排除量子近似优化算法可以在嘈杂的中型量子计算机中使用，以在不久的将来协助达到量子至上。

（图文来自网络，仅供学习与交流，版权归原作者所有，如有侵权，请联系删除）