高级量子计算与Shor算法详解
1. 高级量子计算基础
在量子计算中，为了计算状态的振幅，需要存储一定数量的振幅值。具体来说，每个振幅 $a_{i + 1,p\cdot r}$ 可通过公式 $a_{i + 1,p\cdot r} = \sum_{q = 0}^{2^d - 1} u_{qr}a_{i,p\cdot q}$ 计算得出，且只有前一状态的 $2^d$ 个振幅 $a_{i,pq}$ 与之相关。为了计算状态 $|i\rangle$ 的单个振幅，需要存储 $i2^d$ 个振幅。
在计算过程中，为了达到所需的精度，在任何给定阶段都需要最大精度为 $M$。最终叠加后，任何基向量的振幅可在 $M2^dM$ 空间中确定，且 $M$ 仅随所需步骤数线性增长。由于假设 $k$ 是关于 $n$ 的多项式，且 $d$ 上限为 3，因此可以在多项式时间内计算最终状态 $|k\rangle$ 的单个值。
为了验证该方法，可以创建一个随机基向量 $|j\rangle$ 并计算其振幅。若生成的数字在 0 到 1 之间且小于 $|a_{kj}|$，则结果为 $|j\rangle$；否则，清空整个区域，选择一个新的基向量并重新开始。若时间不是问题，可以多次迭代直至得到一个基向量。因此，可以在多项式时间内实现任何 BQP 计算的经典近似。
2. 量子傅里叶变换
2.1 经典傅里叶变换
离散傅里叶变换（DFT）可将具有离散复值的函数转换为另一个瞬时复值。对于函数 $a:[0,\ldots,N - 1] \to \mathbb{C}$，其离散傅里叶变换得到的函数 $A:[0,\ldots,N - 1] \to \mathbb{C}$ 定义为：
