经典与量子算法的复杂度理论

理解算法的扩展能力对评估其实用性很基本，尤其是在处理机器学习 (machine learning)中常见的大型数据集时。计算复杂度理论提供了分析算法随着输入规模增长所需的资源（主要是时间（基本操作次数）和空间（内存））的工具。这种分析对比较经典算法以及评估量子方法可能带来的益处很重要。

经典复杂度：快速回顾

在经典计算中，我们通常根据所需资源随输入规模（通常用 $n$ 表示）的增长方式来对问题进行分类。我们使用大O符号来描述这种增长行为在最坏情况下的上限。

常见复杂度类别包括：

• $O(1)$： 常数时间。算法运行时间与输入规模无关。
• $O(\log n)$： 对数时间。常见于反复将搜索空间减半的算法，如二分查找。
• $O(n)$： 线性时间。运行时间与输入规模成正比（例如，在一个未排序列表中查找最大元素）。
• $O(n \log n)$： 对数线性时间。高效的排序算法如归并排序或堆排序属于此类。
• $O(n^k)$，其中 $k \ge 1$： 多项式时间。算法运行时间是输入规模的多项式函数（例如，矩阵乘法通常是 $O(n^3)$ 或略优）。
• $O(2^n)$ 或 $O(k^n)$： 指数时间。运行时间随输入规模呈指数增长。这类算法即使对于中等规模的输入，也很快变得难以处理。

一个核心思想是可处理问题和不可处理问题之间的区别。可通过多项式时间算法求解的问题通常被认为是可处理的。

经典复杂度类别有：

• P（多项式时间）： 能够由确定性图灵机在多项式时间内解决的判定问题类别。这些问题被认为是经典计算中可以高效解决的。例子：判断一个数是否为素数（已被证明在P中）。
• NP（非确定性多项式时间）： 对于这类判定问题，其提出解可以由确定性图灵机在多项式时间内验证。例子：整数因式分解（给定因子，验证乘法很容易）。虽然普遍认为P ≠ NP，但P是否等于NP仍是未知数。
• NP-hard： 至少与NP中最难的问题一样难的问题。如果NP中的每个问题L都可以在多项式时间内规约到问题H，则问题H是NP-hard的。NP-hard问题本身不一定在NP中（例如，停机问题）。
• NP-完全： 既在NP中又是NP-hard的问题。这些是NP中最难的问题。例子：旅行商问题（判定版本）。

理解这些类别有助于明确量子计算机可能提供优势的场合。如果一个量子算法能比任何已知经典算法明显更快地解决一个被认为不在P中的问题（例如，可能是NP-完全问题，尽管量子计算机尚未被证明能解决），这便显示出量子计算的优势。

量子复杂度：BQP的出现

量子计算遵循不同的规则，从而形成不同的复杂度类别。量子计算最重要的类别是BQP。

• BQP（有界误差量子多项式时间）： 能够由量子计算机在多项式时间内解决的判定问题类别，其对所有实例的错误概率上限为1/3。这意味着量子算法产生正确答案的概率至少为2/3。选择1/3是任意的；任何小于1/2的常数都可以通过重复放大到任意接近0。

BQP被认为是量子计算机可高效解决的问题类别。

BQP与经典类别有何关联？

• P \u2286 BQP： 任何能被经典计算机高效解决的问题，也能被量子计算机高效解决（量子计算机可以模拟经典逻辑）。
• BQP 对比 NP： BQP与NP之间的关系是一个主要悬而未决的问题。强烈怀疑NP不包含在BQP之内；也就是说，量子计算机不被认为能够高效解决所有NP-完全问题。反之，BQP中有些问题被认为不在NP中（尽管证明这种分离很困难）。

一个图示，显示了复杂度类别P、NP和BQP之间的关系。P包含在NP和BQP中。BQP和NP之间的确切关系和重叠仍是未知，但通常认为它们是互异的集合，P是它们的交集。NP-完全问题存在于NP中。

BQP中不被认为是P类问题的重要例子包括：

• 整数因式分解： 使用Shor算法可以高效解决。已知最好的经典算法是超多项式的。这对RSA密码学有影响。
• 离散对数问题： 同样可以使用Shor算法的变体高效解决。
• 模拟量子系统： 模拟量子系统 $e^{-iHt}|\psi\rangle$ 的演化在经典计算中被认为是困难的（常需要指数级资源），但在量子计算机上可以高效完成（BQP-完全）。

Grover算法为非结构化搜索问题提供了二次加速（$O(\sqrt{N})$ 对比经典 $O(N)$）。尽管这很重要，但这种二次加速本身并不能将问题从指数时间转变为多项式时间（它通常不会将NP-完全问题归入BQP）。

经典与量子机器学习 (machine learning)中的复杂度

经典机器学习算法的复杂度各不相同：

• 训练支持向量 (vector)机（SVM）： 复杂度范围从 $O(N^2 d)$ 到 $O(N^3 d)$，取决于实现和核函数，其中 $N$ 是数据点数量，$d$ 是维度。核函数计算可能占据主导。
• 训练神经网络 (neural network)： 变化很大。对于密集网络，一个训练周期大致可按 $O(N \cdot |\text{权重}|)$ 扩展。复杂度在很大程度上取决于架构、数据集大小和训练周期数。
• 主成分分析（PCA）： 通常涉及矩阵对角化或SVD，成本通常约为 $O(\min(N d^2, N^2 d))$。

对于较大的 $N$ 或 $d$，这些多项式成本可能变得过高。这促使人们寻找可能提供加速的量子算法。

量子算法可能影响机器学习复杂度的潜在方面包括：

1. 线性代数子程序： HHL算法（以Harrow、Hassidim和Lloyd命名）在特定条件下（稀疏矩阵 $A$、高效的 $b$ 态制备、能够测量解 $x$ 的函数）可以在矩阵维度 $N$ 的对数时间内解决线性方程组 $Ax=b$。这暗示了对严重依赖线性代数的算法（如高斯过程、SVM或PCA）潜在的加速。然而，态制备和测量步骤通常会带来显著的额外开销或限制，使得直接应用具有挑战性。
2. 优化： 许多机器学习任务涉及通过最小化成本函数来找到最优参数 (parameter)。Grover算法和相关的量子优化技术（如QAOA或量子梯度下降 (gradient descent)变体）可能为在复杂“地形”中寻找最小值提供二次或可能更大的加速。
3. 采样： 量子模型，如量子电路玻尔兹曼机（QCBMs），可能能够自然地从经典算法（如经典玻尔兹曼机）难以高效表示或采样的概率分布中进行采样。这可能对生成式建模有利。

量子机器学习 (machine learning)复杂度的注意事项与考量

尽管某些子程序中存在量子加速的潜力，但将其转化为QML任务的实际端到端优势面临多项挑战：

• 数据加载： 将大型经典数据集编码为量子态（$|\psi_{data}\rangle$）可能成为瓶颈。如果此步骤所需时间是数据大小或维度的多项式或指数函数，它可能会抵消后续的量子加速。高效的编码方案是一个活跃的研究方向（第2章）。
• 测量开销： 从量子态中提取有用的经典信息通常需要多次测量，其开销随所需精度或待估计参数 (parameter)数量而变化。这会增加显著的额外开销。
• NISQ限制： 近期中等规模量子（NISQ）设备存在噪声、有限的量子比特数和短相干时间的问题。理论上的加速通常假定容错量子计算机。在NISQ硬件上运行算法会引入噪声，从而降低性能，并且纠错技术（第7章）会增加其自身的计算成本。
• 贫瘠高原： 变分量子算法（VQA）在QML中很常见，可能会遇到贫瘠高原问题，即梯度随量子比特数量呈指数级消失，使得大型问题的优化变得极其困难（第4章）。
• 可证明与启发式加速： 使用量子计算机为实际机器学习问题展示严格、可证明的指数级加速是非常具有挑战性的。许多提议的QML算法提供启发式加速，或基于潜在的不同特征空间（例如，量子核，第3章）的优势，而非严格的计算复杂度优势。

因此，尽管复杂度理论为分析QML算法提供了一个重要的框架，但在评估潜在的量子益处时，重要的是要考虑整个流程，包括数据编码、计算、测量以及当前硬件的限制。寻找能够提供比经典方法更可证明和实际加速的QML算法，仍然是该领域的核心难题。