在 Shor 算法中，为了找到一个函数 f(x) 的周期 r，核心步骤是对其输入量子态施加量子傅里叶变换（Quantum Fourier Transform，QFT）。周期态的叠加使得不同输入之间发生干涉，从而在频域中产生振幅峰，便于提取周期信息。
对于周期为 r、长度为 N 的函数 f(x)，对其输入量子态基于 QFT 变换：
\ket{x} \xrightarrow{\mathrm{QFT}_N} \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i k x / N} \ket{k}由于存在叠加态，对于任意叠加态的振幅有：
A(k) = \frac{1}{\sqrt{L N}} \sum_{j=0}^{L-1} e^{2\pi i k (x_0 + j r) / N}
= \frac{e^{2\pi i k x_0 / N}}{\sqrt{L N}} \sum_{j=0}^{L-1} \left( e^{2\pi i k r / N} \right)^j其中
L = \frac{N}{r}为了产生干涉峰，需满足条件：
e^{2\pi i k r / N} = 1 \quad \Longleftrightarrow \quad \frac{k r}{N} \in \mathbb{Z} \quad \Longleftrightarrow \quad \frac{k r}{N} = m, \; m \in \mathbb{Z}此时振幅峰概率为：
\lvert A(k) \rvert^2
= \frac{1}{L N} \left\lvert \sum_{j=0}^{L-1} \left( e^{2\pi i k r / N} \right)^j \right\rvert^2
= \frac{1}{L N} \left\lvert \frac{1 - \left( e^{2\pi i k r / N} \right)^L}{1 - e^{2\pi i k r / N}} \right\rvert^2根据公式
1 - e^{i \theta} = e^{i \theta / 2} \bigl( e^{-i \theta / 2} - e^{i \theta / 2} \bigr) = e^{i \theta / 2} \bigl( -2 i \sin(\theta / 2) \bigr)可得模长为：
\lvert 1 - e^{i \theta} \rvert^2 = 4 \sin^2(\theta / 2)因此：
\begin{aligned}
\lvert A(k) \rvert^2
&= \frac{1}{L N} \left\lvert \frac{1 - \left( e^{2\pi i k r / N} \right)^L}{1 - e^{2\pi i k r / N}} \right\rvert^2 \\
&= \frac{1}{L N} \frac{\sin^2 \left( \pi L k r / N \right)}{\sin^2 \left( \pi k r / N \right)} \\
&\propto \frac{\sin^2(\pi Lkr/N)}{\sin^2(\pi kr/N)}
\end{aligned}由此可知，经过 QFT 变换后，振幅峰位置满足
\frac{\pi k r}{N} = m \pi, \quad m \in \mathbb{Z}事实上，这里使用“约等于”，是因为通常 r 不一定能整除 N，而量子测量只能得到整数 k。此时，概率峰形集中，从而实现周期信息的集中与提取。通过测量这些峰值，可以有效地获得周期 r，这是 Shor 算法中实现整数因式分解的关键步骤。
发表回复