16、量子算法：从Grover到Shor的探索

量子算法：从Grover到Shor的探索

1. Grover算法

1.1 相位反转

在量子力学中，态 $|\xi\rangle$ 被归一化为 1。为了将双量子比特的结果推广到 $n$ 个量子比特的情况，需要进行大量的代数运算。考虑 $n$ 个量子比特和一个辅助量子比特，对 $|0\rangle^{\otimes n}$ 应用哈达玛门（Hadamard gate），会得到所有可能的量子比特计算基的组合，且振幅相等。
相关公式如下：
- $|\psi(t_1)\rangle = H^{\otimes n}|0\rangle^{\otimes n}H|1\rangle = \frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}|x\rangle\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$，其中 $N = 2^n$。
- $|\psi(t_2)\rangle = U_f|\psi(t_1)\rangle = \frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}(-1)^{f(x)}|x\rangle H|1\rangle$。

定义算符 $O$ 和量子比特态 $|\varphi\rangle$：
- $|\psi(t_2)\rangle = O(\frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}|x\rangle)H|1\rangle$。
- $|\varphi\rangle = \frac{1}{\sqrt{N}}\sum_{x = 0}^{N - 1}|x\rangle = \frac{1}{\sqrt{N}}\sum_{