14、量子算法：原理、复杂度与应用

量子算法：原理、复杂度与应用

1. 量子算法概述

量子算法常被描述为比常规算法快得多。这种加速源于能够将输入置于所有可能输入的叠加态，然后对该叠加态执行算法。然而，这也带来了许多问题，比如测量时可能随机得到一个答案，且错误答案可能远多于正确答案。

实际上，构建量子算法的真正艺术在于能够操纵这些叠加态，以便在测量时得到有用的答案。接下来将介绍三种量子算法，它们都巧妙地利用了潜在的数学模式，难度逐渐增加。

2. 算法复杂度的衡量

2.1 复杂度类 P 和 NP

为了理解算法的速度，我们先看两组问题：
-第一组问题：找出两个大于 1 的整数，使其乘积等于给定的数，如 35、187、2407、88631 等。随着数字位数（用 n 表示）的增加，解决问题所需的步骤和时间显著增加。
-第二组问题：验证两个给定整数的乘积是否等于给定的数。这些问题相对容易，且随着 n 的增加，所需时间增长较慢。

我们用 (T(n)) 表示解决输入长度为 n 的问题所需的时间或步骤数。如果存在正数 k 和 p，使得 (T(n) \leq kn^p) 对所有 n 成立，则称该问题可以在多项式时间内解决；如果存在正数 k 和 (c > 1)，使得 (T(n) > kc^n) 对所有 n 成立，则称该问题需要指数时间。

在计算机科学中，能在多项式时间内解决的问题属于复杂度类 P，如两个数相乘的问题。而如果验证一个答案是否正确可以在多项式时间内完成，则该问题属于复杂度类 NP，如将一个大数分解为两个质数的乘积。

显然