16、量子计算：算法、复杂度与加密影响

量子计算：算法、复杂度与加密影响

量子算法复杂度相关概念

在复杂度理论中，主要的分类是基于解决问题所需的时间。能在多项式时间内解决的问题和需要超过多项式时间的问题有着本质区别。多项式时间算法即使对于非常大的 n 值也被认为是可行的，而非多项式时间算法对于大的 n 值则被认为是不可行的。

经典算法能在多项式时间内解决的问题用 P 表示，量子算法能在多项式时间内解决的问题用 QP（有时也用 EQP 表示精确量子多项式时间）表示。这里我们还引入了一种新的复杂度衡量方式——查询复杂度，它计算的是向神谕询问问题的次数。

以 Deutsch - Jozsa 问题为例，它不属于 P 类，但在查询复杂度上属于 QP 类。这意味着该问题可以用量子算法在多项式时间内解决，但经典算法无法做到，它将 P 类和 QP 类区分开来。

我们来看经典算法的最坏情况。假设一个函数有 10 个输入，且该函数要么是平衡的，要么是常量的。总共有 (2^{10} = 1024) 种可能的输入。最坏的情况是函数为平衡函数，但前 512 次评估得到相同的答案，直到第 513 次评估才得到另一个值。不过，这种情况发生的概率极小，就像抛 512 次公平硬币每次都得到正面的概率是 ((\frac{1}{2})^{512})，小于 1 除以古戈尔（(10^{100})）。

为了处理这种情况，我们引入了有界误差复杂度类。我们选择一个可以接受的误差概率界限，然后寻找能在这个误差界限内回答问题的算法。以 Deutsch - Jozsa 问题为例，如果我们希望成功率至少达到 99.9%，即误差率小于 0.1%。当函数为平衡函数时，对函数进行 11 次评估每次都得到 0 的概率精确到五位小数是 0.00