5.4 量子 Fourier 变换的一般应用¶

练习 5.20¶

练习 5.20

设 \(f(x+r) = f(x)\)，且 \(0 \leqslant x < N\)，\(N\) 是 \(r\) 的一个整倍数；计算

\[ \hat f(l) = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} e^{-2 \pi i l x / N} f(x) \tag{5.68} \]

并将此结果与式 (5.63) 联系起来。其中用到的事实是

\[\begin{split} \sum_{k \in \{0, r, 2r, \cdots, N-r\}} e^{2 \pi i k l / N} = \left\{\begin{alignat*}{10} & N/r, \quad && \text{if } l \text{ is an integer multiple of } N/r \\ & 0， && \text{otherwise} \end{alignat*}\right. \end{split}\]

上式编号为式 (5.69)。

警告

英文原版中，式 (5.69) 是错误的。中文版是正确的。

书中提到，之所以算法求周期的第 (3) 步是近似的，是因为 \(N = 2^t\) 不一定是 \(r\) 的整数倍数；但若确实是整数倍数，那么这个近似其实就是等价了。我们在这里证明的是 \(N\) 是 \(r\) 倍数时的等价情况。

什么情况下，算法的第 (3) 步的近似是有效的呢？若 \(\lfloor N/r \rfloor \times r\) 到 \(N - 1\) 之间的求和在总求和区间即 \(0\) 到 \(N-1\) 内占比很小时，那么近似是有效的。为了达到一个较好的近似，\(N\) 应当要取得足够大。

式 (5.69) 验证

为了之后证明的方便，我们也要试一下将 (5.69) 的记号进行简化，并对其进行验证。首先，依题目的假设，我们可以定义整数 \(j = \frac{k}{r}\)，并定义整数 \(\lambda, c\) 为 \(l = \lambda N/r + c\)，其中 \(c\) 是小于 \(N/r\) 的自然数。那么，待证式 (5.69) 可以写为

\[\begin{split} \sum_{j=0}^{N/r-1} e^{2 \pi i j r l / N} = \sum_{j=0}^{N/r-1} e^{2 \pi i (j \lambda + jrc / N)} = \left\{\begin{alignat*}{10} & \frac{N}{r}, \quad && \frac{N}{r} \mid l \\ & 0， && \frac{N}{r} \nmid l \end{alignat*}\right. \end{split}\]

若 \(c = 0\)，即 \(l = \lambda N / r\) 即 \(l\) 是 \(N/r\) 的整倍数，那么被求和项是 \(e^{2 \pi i j \lambda} = 1\)。由于总共有 \(N/r\) 个求和项，因此总和就是 \(N/r\)。
若 \(c \neq 0\)，那么被求和项是 \(e^{2 \pi i j \lambda} e^{2 \pi i j r c / N} = e^{2 \pi i j r c / N}\)；因此依据以比例为 \(\omega = e^{2 \pi i r c / N}\) 等比数列的求和方法，

\[ \sum_{j=0}^{N/r-1} e^{2 \pi i jrc / N} = \frac{1 - \omega^{N/r}}{1 - \omega} = \frac{1 - e^{2 \pi i c}}{1 - \omega} = \frac{0}{1 - \omega} = 0 \]

式 (5.68) 验证

首先，我们可以用 \(x = j r + d\) 的形式表示指标；那么在当前的问题下，恰好 \(j\) 可以取遍 \(0, 1, \cdots, N/r-1\)，而 \(d\) 恰好可以取遍 \(0, 1, \cdots, r-1\)。那么，我们将 (5.68) 对 \(x\) 的求和化为对 \(j\) 与 \(d\) 的求和了。同时注意到 \(f(x+r) = f(x)\) 的周期性条件，因此 \(f(x) = f(jr+d) = f(d)\)：

\[ \begin{align*} \hat f(l) = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} e^{-2 \pi i l x / N} f(x) = \frac{1}{\sqrt{N}} \sum_{j=0}^{N/r-1} \sum_{d=0}^{r-1} e^{-2 \pi i l (jr+d) / N} f(d) \end{align*} \]

我们现在回顾到 \(\sum_{j=0}^{N/r-1} e^{2 \pi i j r l / N}\) 只有在 \(l\) 是 \(N/r\) 整倍数时非零且为 \(N/r\) 的结论，那么将上式整理可得

\[\begin{split} \hat f(l) = \frac{1}{\sqrt{N}} \sum_{d=0}^{r-1} \left( \sum_{j=0}^{N/r-1} e^{-2 \pi i l jr / N} \right) e^{-2 \pi i l d / N} f(d) = \left\{\begin{alignat*}{10} &\frac{\sqrt{N}}{r} \sum_{d=0}^{r-1} e^{-2 \pi i l d / N} f(d), \quad && \frac{N}{r} \mid l \\ & 0, && \frac{N}{r} \nmid l \end{alignat*} \right. \end{split}\]

与式 (5.63) 的联系

该式与 (5.63) 看起来相差了归一化因子。我们作如下说明。

将上面答案中的被求和角标 \(d\) 替换为 \(x\)；并且将 \(f(x)\) 表示为右矢空间的态 \(|f(x)\rangle\)。
由于不是所有 \(l\) 都需要考虑，因为只有 \(l\) 是 \(N/r\) 的情况下结果是非平凡的。那么我们就只考虑这些非平凡的 \(l\)。我们使用 \(r\) 维度的向量空间 \(|\hat g(\lambda)\rangle\) 来储存这些 \(|\hat f (l) \rangle = |\hat g (\lambda N/r) \rangle\)：

\[ |\hat g (\lambda)\rangle = \frac{\sqrt{N}}{r} \sum_{x=0}^{r-1} e^{-2 \pi i (\lambda N / r) x / N} |f(x)\rangle \left/ \sqrt{\frac{r}{N}} \right. = \frac{1}{\sqrt{r}} \sum_{x=0}^{r-1} e^{-2 \pi i \lambda x / r} |f(x)\rangle \]

之所以要除以 \(\sqrt{r/N}\)，是因为我们之前的 \(|\hat f (l)\rangle\) 的空间是 \(l = 0, 1, \cdots, N-1\) 的 \(N\) 维空间；而 \(|\hat g(\lambda)\rangle\) 则是 \(\lambda = 1, 2, \cdots, r\) 的 \(r\) 维空间。因此，并非把 \(|\hat f (l)\rangle\) 的所有非零元素放到 \(|\hat g(\lambda)\rangle\) 就好了，还需要作合适的归一化。

上式其实就是式 (5.63) 了。需要注意，本题的 \(l\) 是可以取 \(l = 0, 1, \cdots, N-1\) 的；但式 (5.63) 的 \(l\) 其实只能取 \(l = 0, 1, \cdots, r-1\)，这也能从式 (5.64) 的求和角标取值范围看出。式 (5.63) 的 \(l\) 其实是这道题的 \(\lambda = l / (N / r)\)。

练习 5.21 (求周期与相位估计)¶

练习 5.21

设为上述周期函数，给定一个执行变换 \(U_y |f(x)\rangle = |f(x+y)\rangle\) 的酉算符 \(U_y\)。

证明 \(U_y\) 的特征向量是 \(|\hat f(l)\rangle\)，并计算其特征值；
证明对某个 \(x_0\) 所给定的 \(|f(x_0)\rangle\)，\(U_y\) 可被用来实现和求周期问题中的 \(U\) 一样有用的黑箱。

第一问

我们使用式 (5.63) 所定义的 \(|\hat f(l)\rangle\)。同时，令变量 \(u = x + y\)，\(u' = u - r\)。因此，

\[\begin{split} \begin{align*} U_y |\hat f(l)\rangle &= \frac{1}{\sqrt{r}} \sum_{x=0}^{r-1} e^{- 2 \pi i l x / r} |f(x+y)\rangle \\ &= \frac{1}{\sqrt{r}} \sum_{u=y}^{r-1+y} e^{- 2 \pi i l (u-y) / r} |f(u)\rangle \\ &= e^{2 \pi i l y / r} \frac{1}{\sqrt{r}} \sum_{u=y}^{r-1+y} e^{- 2 \pi i l u / r} |f(u)\rangle \\ &= e^{2 \pi i l y / r} \frac{1}{\sqrt{r}} \left( \sum_{u=y}^{r-1} e^{- 2 \pi i l u / r} |f(u)\rangle + \sum_{u=r}^{r-1+y} e^{- 2 \pi i l u / r} |f(u - r)\rangle \right) \\ &= e^{2 \pi i l y / r} \frac{1}{\sqrt{r}} \left( \sum_{u=y}^{r-1} e^{- 2 \pi i l u / r} |f(u)\rangle + \sum_{u'=0}^{y-1} e^{- 2 \pi i l (u' + r) / r} |f(u')\rangle \right) \\ &= e^{2 \pi i l y / r} |\hat f(l)\rangle \end{align*} \end{split}\]

第四个等号利用的是 \(|f(x)\rangle\) 以 \(r\) 为周期的性质；第六个等号则利用了 \(e^{- 2 \pi i l} = 1\)，且回顾 \(|\hat f(l)\rangle\) 的定义就可以推导出来。因此我们验证了 \(|\hat f(l)\rangle\) 是 \(U_y\) 的本征态，且本征值是 \(e^{2 \pi i l y / r}\)。

第二问

对于特定的 \(x_0\)，我们先要对其依据式 (5.64)，将其拆解为 \(U_y\) 本征态的线性组合 (注意对于第一寄存器比特数 \(t\)，若 \(r \nmid 2^t\)，那么下式在实际实现过程中会成为近似)：

\[ |f(x_0)\rangle = \frac{1}{\sqrt{r}} \sum_{l=0}^{r-1} e^{2 \pi i l x_0 / r} |\hat f(l)\rangle \]

那么就可以利用算符的线性性质，将 \(U_y\) 作用在 \(|f(x_0)\rangle\) 上得到

\[ |x_0\rangle U_y |f(x_0)\rangle = \frac{1}{\sqrt{r}} \sum_{l=0}^{r-1} e^{2 \pi i l x_0 / r} |x_0\rangle U_y |\hat f(l)\rangle = \frac{1}{\sqrt{r}} \sum_{l=0}^{r-1} e^{2 \pi i l x_0 / r} e^{- 2 \pi i l y / r} |x_0\rangle |\hat f(l)\rangle \]

对于实际线路中，\(x\) 是要被求和的，即两个寄存器实际状态是

\[ \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t - 1} |x\rangle U_y |f(x)\rangle = \frac{1}{\sqrt{r 2^t}} \sum_{l=0}^{r-1} e^{-2 \pi i l y / r} \sum_{x=0}^{2^t-1} e^{2 \pi i l x / r} |x\rangle |\hat f(l)\rangle \]

需要注意，由于逆向 Fourier 变换只在第一寄存器上计算，该过程可以写为

\[ \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} e^{2 \pi i l x / r} |x\rangle \rightarrow |\widetilde{l/r}\rangle \]

因此，在逆向 Fourier 变换后，所有寄存器上的状态表示为

\[ \frac{1}{\sqrt{r}} \sum_{l=0}^{r-1} e^{-2 \pi i l y / r} |\widetilde{l/r}\rangle |\hat f(l)\rangle \]

随后对第一寄存器测得分数 \(\widetilde{l/r}\)。因此，我们注意到尽管使用 \(U_y: |f(x)\rangle \mapsto |f(x+y)\rangle\) 相比于 \(U: |f(x)\rangle \mapsto |y \oplus f(x)\rangle\) 在最终的寄存器表达式中多了 \(e^{-2 \pi i l y / r}\) 一项，但它只是个相位。测得的 \(\widetilde{l/r}\) 是相同的，而且对于每个 \(l = 0, 1, \cdots, r-1\)，其出现的概率也相同。

练习 5.22¶

练习 5.22

证明

\[\begin{split} \begin{align*} |\hat f(l_1, l_2)\rangle &= \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{x_2=0}^{r-1} e^{- 2 \pi i (l_1 x_1 + l_2 x_2) / r} |f(x_1, x_2)\rangle \\ &= \sum_{j=0}^{r-1} e^{-2 \pi l_2 j / r} |f(0, j)\rangle \end{align*} \end{split}\]

且这个表达式不为零的限制条件是，\((l_1/s)-l_2\) 是 \(r\) 的整倍数。

警告

原书中的公式表述有些错误。式 (5.70) 其实不包含 \(1/\sqrt{r}\) 的系数。对 \(|f(x_1, x_2)\rangle\) 的 Fourier \(|\hat f(l_1, l_2)\rangle\) 的变换空间其实是 \((l_1, l_2)\) 构成的 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 空间，因此归一化系数应该取为 \((1/\sqrt{r})^2 = 1/r\)。

首先我们回顾到，我们现在的函数是 \(f(x_1, x_2) = a^{s x_1 + x_2} \; (\text{mod } N)\)，因此，该函数也可以写为 \(f(0, sx_1 + x_2)\)。因此代入待证等式，得到

\[ |\hat f(l_1, l_2)\rangle = \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{x_2=0}^{r-1} e^{- 2 \pi i (l_1 x_1 + l_2 x_2) / r} |f(0, s x_1 + x_2)\rangle \]

随后将 \(x_2\) 用 \(j = s x_1 + x_2\) 替换，那么

\[ |\hat f(l_1, l_2)\rangle = \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{j=s x_1}^{r-1 + s x_1} e^{- 2 \pi i (l_1 x_1 + l_2 j - l_2 s x_1) / r} |f(0, j)\rangle \]

利用 \(f(0, j) = f(0, j+r)\) 的周期性，上式化为

\[\begin{split} \begin{align*} |\hat f(l_1, l_2)\rangle &= \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{j=0}^{r-1} e^{- 2 \pi i (l_1 x_1 + l_2 j - l_2 s x_1) / r} |f(0, j)\rangle \\ &= \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{j=0}^{r-1} e^{- 2 \pi i x_1 (l_1 - l_2 s) / r} e^{- 2 \pi i l_2 j / r} |f(0, j)\rangle \end{align*} \end{split}\]

我们以前已经多次证明到，

\[\begin{split} \sum_{x_1=0}^{r-1} e^{- 2 \pi i x_1 (l_1 - l_2 s) / r} = \left\{\begin{alignat*}{10} & r, \quad && r \mid (l_1 - l_2 s) \\ & 0, \quad && r \nmid (l_1 - l_2 s) \end{alignat*}\right. \end{split}\]

因此，

\[\begin{split} |\hat f(l_1, l_2)\rangle = \left\{\begin{alignat*}{10} & \sum_{j=0}^{r-1} e^{- 2 \pi i l_2 j / r} |f(0, j)\rangle, \quad && r \mid (l_1 - l_2 s) \\ & 0, \quad && r \nmid (l_1 - l_2 s) \end{alignat*}\right. \end{split}\]

练习 5.23¶

练习 5.23

用式 (5.70) 证明，

\[ \frac{1}{r} \sum_{l_1 = 0}^{r-1} \sum_{l_2=0}^{r-1} e^{2 \pi i (l_1 x_1 + l_2 x_2) / r} |\hat f (l_1, l_2) \rangle = f(x_1, x_2) \]

警告

原来题目里 \(e\) 幂指数上是有负号的。但作为 Fourier 变换，其符号应该是正的才对。参考式 (5.64)，我决定将题目中的幂指数上的负号去掉。

首先，我们知道 \(l_1 = s l_2 (\text{mod } r)\) 的 \(|\hat f(l_1, l_2)\rangle\) 的值可能非零。同时，由于 \(l_1\) 的可取值范围是 \(0, 1, \cdots, r-1\)，因此 \(\sum_{l_1=0}^{r-1}\) 与其说是求和，不如说只能取 \(s l_2 (\text{mod } r)\)。但出于周期性，因此我们代入 \(l_1 = s l_2\) 也无妨。那么得到待证等式左为

\[ \mathrm{LHS} = \frac{1}{r} \sum_{l_2=0}^{r-1} e^{2 \pi i l_2 (s x_1 + x_2) / r} |\hat f (l_1, l_2) \rangle \]

随后我们代入练习 5.22 的结论：

\[ \mathrm{LHS} = \frac{1}{r} \sum_{l_2=0}^{r-1} \sum_{j=0}^{r-1} e^{2 \pi i l_2 (s x_1 + x_2 - j) / r} |f(0, j)\rangle \]

我们首先对 \(l_2\) 求和。利用我们以前一直证明过的结论，知道

\[\begin{split} \sum_{l_2=0}^{r-1} e^{2 \pi i l_2 (s x_1 + x_2 - j) / r} = \left\{\begin{alignat*}{10} & r, \quad && r \mid (s x_1 + x_2 - j) \\ & 0, \quad && r \nmid (s x_1 + x_2 - j) \end{alignat*}\right. \end{split}\]

因此，对待证等式左有实质贡献的项必然满足 \(j = s x_1 + x_2 \; (\text{mod } r)\)。在这种情况下，\(f(0, j) = f(0, s x_1 + x_2) = f(x_1, x_2)\)。考虑到这些后，待证等式就证明完毕了。

练习 5.24¶

练习 5.24

建立离散对数算法第 6 步所需要的，从 \(s l_2/r\) 和 \(l_2 / r\) 的估计确定 \(s\) 的推广的连分式算法。

警告

下述做法其实是很直白的，没有使用推广连分式。但需要一次量子算法，因此实现稍困难一些。

首先，这个算法是合理的。我们至少有 \(1/4\) 概率通过对 \(\widetilde{l_2/r}\) 作连分式，得到正确的 \(r\)；因此不必担心因为 \(s\) 是 \(r\) 的因子，而无法从 \(\widetilde{s l_2 / r}\) 获得正确分母的情况。因此，\(\widetilde{s l_2 / r}\) 的分子、分母都可以正常地估计，即使它们并不互质。

算法困难之处在于 \(s l_2\) 可能因为大于 \(r\)，因此我们实际估计到的分子不是 \(s l_2\)，而是 \(s l_2 \; (\text{mod } r)\)。不能将 \(\widetilde{s l_2 / r}\) 的分子与 \(\widetilde{l_2/r}\) 的分子直接相除。当然，如果 \(s l_2 \; (\text{mod } r)\) 恰好是 \(l_2\) 的倍数，那么我们可以直接输出两者的比例作为 \(s\) 的值。

如果 \(s l_2 \; (\text{mod } r)\) 不是是 \(l_2\) 的倍数，那么解决方案是，既然我们通过 \(\widetilde{l_2/r}\) 可以获得正确的 \(l_2\) (回顾到它与 \(r\) 需要是互质的，才能给出正确的 \(r\))，并且假设 \(r\) 是 \(L\) 比特数，那么

通过 \(O(L^3)\) 量子算法和连分式算法，获得 \(l_2\) 模 \(r\) 的阶 \(k\)，即 \(l_2^k = 1 (\text{mod } r)\)；我们注意到因为上面的过程要求 \(l_2\) 与 \(r\) 互质，因此这里的阶的存在性是能保证的。
通过 \(O(L^3)\) 的幂运算，获得 \(l_2^{k-1} \; (\text{mod } r)\)。
从而可以计算 \(s l_2 \times l_2^{k-1} = s \; (\text{mod } r)\)。

整个过程仍然是 \(O(L^3)\) 的，但需要一次额外的量子算法。

练习 5.25¶

练习 5.25

为用于两子离散对数算法的黑箱 \(U\) 构造一个量子线路；该黑箱以 \(a, b\) 为参数，执行酉变换 \(|x_1\rangle |x_2\rangle |y\rangle \rightarrow |x_1\rangle |x_2\rangle |y \oplus b^{x_1} a^{x_2} \rangle\)，需要多少基本运算？

假定 \(x_1, x_2, y, a, b\) 均是不大于 \(L\) 的比特数。

幂次运算 \(b^{x_1}\)、\(a^{x_2}\) 是 \(O(L^3)\) 计算复杂度，它们可能需要用到额外 \(L\) 个寄存器用于储存临时变量；
乘法 \(b^{x_1} a^{x_2}\) 是 \(O(L^2)\) 计算复杂度；
加法 \(y \oplus b^{x_1} a^{x_2}\) 是 \(O(L)\) 计算复杂度。

总得来说是 \(O(L^3)\) 复杂度。

练习 5.26¶

练习 5.26

因为 \(K\) 是 \(G\) 的一个子群，当我们把 \(G\) 分解为素幂阶循环群的乘积时，也分解了 \(K\)。重新表达式 (5.77)，证明为确定 \(l_i'\)，可以在对应于 \(K\) 的循环子群 \(K_{p_i}\) 中采样。

\[ \sum_{h \in K} e^{- 2 \pi i l h / |G|} = |K| \tag{5.77} \]

设 \(K\) 的分解是 \(K = Z_{p_1} \times Z_{p_2} \times \cdots \times Z_{p_N} \subseteq Z\)，那么式 (5.77) 可以写为

\[ \prod_{j=1}^N \sum_{h_j = 0}^{p_j - 1} e^{2 \pi i l_j' h_j / p_j} = |K| = \prod_{j=1}^N p_j \]

那么对于上式的任何一个 \(j\)，目标是要寻找能使下式非零的 \(l_j'\)：

\[ \sum_{h_j = 0}^{p_j - 1} e^{2 \pi i l_j' h_j / p_j} = p_j \]

一般来说，这会要求 \(l_j' = 0\)；否则依等比数列求和公式，若 \(l_j' / p_j\) 不是整数，那么上式必然为零。

我对抽象的群论只有一些了解，但没有把握掌握这些。下面是我对这道题的理解。

我想这道题是说，如果 Abel 群 \(G\) 是可以拆分为有限素幂阶循环群，那么对于 Fourier 变换后的变量 \(l\) 并非可以是任意的，而必须要满足一定形式，才会使 \(|\hat f(l)\rangle\) 的贡献非零。

假设说，\(G = G_1 \times G_2 \times K_1 \times K_2\)，其中 \(K = K_1 \times K_2\) 是 \(G\) 的隐含子群，那么对应地，\(l = (l_{G_1}, l_{G_2}, l_{K_1}, l_{K_2})\)。只有 \(l_{K_1}, l_{K_2} = 0\) 时 (或类似地，\(l_{K_1}\) 是 \(|K_1|\) 的倍数、\(l_{K_2}\) 是 \(|K_2|\) 的倍数)，那么这样的 \(|\hat f(l)\rangle\) 对 \(|f(x)\rangle\) 的贡献才是非零的。

一个例子可以是离散对数问题，即 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 下的循环函数 \(f(x_1, x_2) = f(x_1 + l, x_2 - ls)\)。我们使用数对 \((x_1, x_2)\) 表示函数 \(f(x_1, x_2)\)，由此在求 Fourier 变换时对应地使用 \((l_1, l_2)\) 给出

\[ \begin{align*} |\hat f(l_1, l_2)\rangle = \frac{1}{r} \sum_{x_1=0}^{r-1} \sum_{x_2=0}^{r-1} e^{- 2 \pi i (l_1 x_1 + l_2 x_2) / r} |f(x_1, x_2)\rangle \end{align*} \]

进而发现，必须要有限制条件 \(l_1 - l_2 s\) 是 \(r\) 的倍数。因此，\(l_1, l_2\) 就缺少了一个自由度。

换个角度来考虑问题。如果我们用数对 \((x_1, x_2)\) 表示 \(f(x_1 + l x_2, x_1 - ls x_2)\) (需要指出，我们一开始并不知道周期常数 \(l, s\)，因此它不能使用在实际的量子算法中，但现在只是写写公式而已)。为了讨论方便 (因此这里的讨论其实相当不严谨，但我想大致思路是对的)，我们假设现在恰巧 \(l, s, r\) 互质，那么 \(x_1, x_2\) 可以取遍所有 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 下的二元数组。令群 \(x_1 \in G_1\)、\(x_2 \in G_2\)，那么 \((x_1, x_2) \in G_1 \times G_2 = G = \mathbb{Z}_r \times \mathbb{Z}_r\)。那么不论 \(x_2\) 的值是多少，函数的值只受 \(x_1\) 的影响而变化。如果我们在求 Fourier 变换时对应地使用 \((l_1, l_2)\)，那么可以给出

\[\begin{split} \begin{align*} |\hat f(l_1, l_2)\rangle &= \frac{1}{\sqrt{|G_1| |G_2|}} \sum_{x_1=0}^{|G_1|-1} \sum_{x_2=0}^{|G_2|-1} e^{- 2 \pi i l_1 x_1 / |G_1|} e^{- 2 \pi i l_2 x_2 / |G_2|} |f(x_1 + l x_2, x_1 - ls x_2)\rangle \\ &= \frac{1}{\sqrt{|G_1|}} \sum_{x_1=0}^{|G_1|-1} e^{- 2 \pi i l_1 x_1 / |G_1|} |f(x_1, x_1)\rangle \frac{1}{\sqrt{|G_2|}} \sum_{x_2=0}^{|G_2|-1} e^{- 2 \pi i l_2 x_2 / |G_2|} \end{align*} \end{split}\]

我们注意到关于 \(x_2\) 的求和式中，若 \(l_2 / |G_2|\) 不为整数，那么这一项就为零。因此，\(l_2\) 必须要是零，即

\[ \begin{align*} |\hat f(l_1, l_2)\rangle = \frac{\sqrt{|G_2|}}{\sqrt{|G_1|}} \sum_{x_1=0}^{|G_1|-1} e^{- 2 \pi i l_1 x_1 / |G_1|} |f(x_1, x_1)\rangle \end{align*} \]

或者如果我们剔除 \(l_2\)，则可以少去一个归一化因子：

\[ \begin{align*} |\hat f(l_1)\rangle = \frac{1}{\sqrt{|G_1|}} \sum_{x_1=0}^{|G_1|-1} e^{- 2 \pi i l_1 x_1 / |G_1|} |f(x_1, x_1)\rangle \end{align*} \]

依据定义，\(x_2\) 的取值空间 \(G_2\) 其实同构于隐含子群 \(K\)，即二元数组 \((l, -ls)\) 依关于 \(r\) 的模生成的群。从这个角度来考察这道练习 5.26，我想应该就会更直观一些。

但现实中，\(l, s, r\) 互质并不一定成立；因此对于 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 问题，可能不能真的依这种方法简化。但若可以拆成多个不同素数的素幂阶循环群，那么可能就有算法提升的空间。

未完成题目¶

危险

练习 5.27-5.29 未完成。

练习 5.27 可以参考下述文献：

https://arxiv.org/abs/cs/0101004

练习 5.28, 5.29 可以参考下述文献：

https://arxiv.org/abs/quant-ph/9903071

量子计算与量子信息 习题解答 文档