5.1 量子 Fourier 变换¶

练习 5.1¶

练习 5.1

给出式 (5.2) 定义的线性变换是酉变换的直接证明。

\[ |j\rangle \rightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2 i \pi j k / N} |k\rangle \tag{5.2} \]

首先，依据该式，可以给出 Fourier 变换的矩阵元 \(F_{jk}\) 可以写为

\[ F_{jk} = \frac{1}{\sqrt{N}} e^{2 i \pi j k / N} \]

为了证明该变换是酉变换，我们尝试求取其自伴矩阵 \(F^\dagger\) 与 \(F\) 之间的乘积，以验证是否 \(F^\dagger F = I\)。回顾到自伴矩阵 \(F^\dagger\) 是 \(F\) 的共轭转置。我们对矩阵元 \(jk\) 作考察：

\[\begin{split} \begin{align*} (F^\dagger F)_{jk} &= \sum_{l=0}^{N-1} (F^\dagger)_{jl} F_{lk} = \sum_{l=0}^{N-1} F_{lj}^* F_{lk} \\ &= \frac{1}{N} \sum_{l=0}^{N-1} e^{- 2 i \pi lj / N} e^{2 i \pi lk / N} = \frac{1}{N} \sum_{l=0}^{N-1} e^{2 i \pi (k-j) l / N} \end{align*} \end{split}\]

下面要分两种情况考虑。若 \(k = j\)，则上式化为

\[ (F^\dagger F)_{jj} = \frac{1}{N} \sum_{l=0}^{N-1} e^{0 \times 2 i l / N} = \frac{1}{N} \sum_{l=0}^{N-1} 1 = 1 \]

若 \(k \neq j\)，那么若将 \(e^{2 i \pi (k-j) l / N}\) 看作关于自然数 \(l\) 的数列，那么它是等比数列，且比例 \(\omega\) 是 \(\omega = e^{2 i \pi (k-j) / N}\)。又由于 \(0 \leqslant j, k \leqslant N-1\)，因此易推知 \(0 < |k-j| < N\)，即 \(\omega = e^{2 i \pi (k-j) / N} \neq e^{2 \pi i} = 1\)。因此，该等比数列的求和可以套用公式

\[ (F^\dagger F)_{jk} = \frac{1}{N} \sum_{l=0}^{N-1} \omega^l = \frac{1}{N} \frac{1 - \omega^N}{1 - \omega} \]

但由于 \(k-j\) 是整数，因此 \(\omega^N = e^{2 i \pi (k-j)} = 1\)。因此，当 \(j \neq k\) 时，\((F^\dagger F)_{jk} = 0\)。综上，

\[ (F^\dagger F)_{jk} = \delta_{jk} \quad \text{i.e.} \quad F^\dagger F = I \]

练习 5.2¶

练习 5.2

具体计算 \(n\) 量子比特状态 \(|00\cdots0\rangle\) 的 Fourier 变换。

直接套用式 (5.2)，代入 \(j = 0\)，得到

\[ |00\cdots0\rangle \rightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} |k\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} |k\rangle \]

但这里需要说明，首先作为 \(n\) 量子比特状态，因此 \(|k\rangle\) 有 \(2^n\) 种可能构造，因此 \(N = 2^n\)。其次，在原先的式 (5.2) 中，\(|k\rangle\) 代表的是态，而 \(e^{2 i \pi jk / N}\) 中的 \(k\) 是该态对应的、可以用于运算的二进制数。

我们换一个更具体、且与原题不同的例子。对于 \(|j\rangle = |01\rangle\) 时，其量子比特数 \(n = 2\)，其态对应的数值是 \(j = 1\)，其 Fourier 变换则会是

\[ |01\rangle \rightarrow \frac{1}{\sqrt{2^2}} \sum_{k=0}^{2^2 - 1} e^{2 i \pi \times 1 \times k / N} |k\rangle = \frac{1}{2} \big( |00\rangle + e^{\frac{1}{4} 2 i \pi} |01\rangle + e^{\frac{2}{4} 2 i \pi} |10\rangle + e^{\frac{3}{4} 2 i \pi} |11\rangle \big) \]

有时为了方便和简洁起见，会用 \(\omega = e^{\frac{1}{4} 2 i \pi}\) 对上式作记号简化，即 Fourier 变换是

\[ |01\rangle \rightarrow \frac{1}{2} \big( |00\rangle + \omega |01\rangle + \omega^2 |10\rangle + \omega^3 |11\rangle \big) \]

练习 5.3 (经典快速 Fourier 变换)¶

练习 5.3

在一个经典计算机上进行一个包含 \(2^n\) 个复数向量的 Fourier 变换，验证基于式 (5.1) 的直接方法进行 Fourier 变换，需要 \(\Theta (2^{2n})\) 个基本算术运算。验证基于式 (5.4) 的运算方法，算术运算数量降低到 \(\Theta (n 2^n)\) 个。

我们不严格分析 \(\Theta\) 与 \(\text{big-}O\) 的区别，只是大致作讨论。

对于 \(n\) 比特的运算 (即 \(N = 2^n\) 的离散向量 Fourier 变换)

\[ y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2 i \pi j k / N} \tag{5.1} \]

我们若认为 \(j \times k\) 的乘法运算是 \(O(1)\) 的，那么

\(e^{2 i \pi j k / N}\) 的运算是 \(O(1)\) 的；
求和操作 \(\sum_{j=0}^{N-1}\) 需要 \(N=2^n\) 次运算；
我们需要求得 \(y_1, y_2, \cdots, y_N\)，因此一共要求取 \(N=2^n\) 个值。

综上，运算数是 \(2^n \times 2^n \times O(1) = O(2^{2n})\)。但需要指出，若 \(n\) 比特乘法 \(j \times k\) 的运算被认为是 \(O(n)\) 的 (因为我们需要处理类似于 \(j \times k, j \times (k+1)\) 等连续乘法，因此乘法完全可以当作加法来处理；否则不使用加法的话，应该至少是 \(O(n \log n \log \log n)\))，那么运算数应该是 \(O(n 2^{2n})\)。

若使用下式，

\[ |j_1j_2 \cdots j_n \rangle \rightarrow \frac{1}{2^{n/2}} \big( |0\rangle + e^{2 i \pi \times 0.j_n} |1\rangle \big) \big( |0\rangle + e^{2 i \pi \times 0.j_{n-1} j_n} |1\rangle \big) \cdots \big( |0\rangle + e^{2 i \pi \times 0.j_1j_2 \cdots j_n} |1\rangle \big) \tag{5.4} \]

构造 \(|0\rangle + e^{2 i \pi \times 0.j_lj_{l+1}\cdots j_n} |1\rangle\) 的时间至多是 \(O(n)\)，且相比后续计算，可以忽略；
乘法表达式还不是 \(N = 2^n\) 个向量分量的线性组合，我们最后还要求线性组合的系数 (相当于式 (5.1) 中的 \(y_k\))；
对于线性组合系数，我们需要进行至多 \(n\) 次或平均 \(n/2\) 次乘法求出，即 \(\Theta (n)\) 次乘法。

因此，运算数是 \(O(n) + 2^n \Theta (n) = \Theta (n 2^n)\)。

练习 5.4¶

练习 5.4

给出受控 \(R_k\) 门到单量子比特门和受控非门的一个分解。

为了解该题，我们要回顾图 4.6。我们需要找到三个算符 \(A, B, C\) 与相位因子 \(\alpha\)，使得 \(R_k = e^{- i \alpha} AXBXC\)，且 \(ABC = I\)。

我们回顾到 \(R_k\) 的表达式

\[\begin{split} R_k = \begin{bmatrix} 1 & 0 \\ 0 & e^{2 \pi i / 2^k} \end{bmatrix} = e^{\pi i / 2^k} \begin{bmatrix} e^{- \pi i / 2^k} & 0 \\ 0 & e^{\pi i / 2^k} \end{bmatrix} = e^{\pi i / 2^k} R_z \left( \frac{\pi}{2^{k-1}} \right) \end{split}\]

我们回顾到 \(X R_z(\theta) X = R_z (- \theta)\) (可以参考练习 4.7 的证明)，那么

\[ R_k = e^{\pi i / 2^k} R_z \left( \frac{\pi}{2^{k-1}} \right) = e^{\pi i / 2^k} R_z \left( \frac{\pi}{2^{k}} \right) R_z \left( \frac{\pi}{2^{k}} \right) = e^{\pi i / 2^k} X R_z \left( - \frac{\pi}{2^{k}} \right) X R_z \left( \frac{\pi}{2^{k}} \right) \]

因此，我们可以令

\[ \alpha = \pi/2^k, \; A = I, \; B = R_z (- \pi/2^k), \; C = R_z (\pi/2^k) \]

我们若令 \(P_{\alpha}\) 是下述门路：

\[\begin{split} P_\alpha = \begin{bmatrix} 1 & 0 \\ 0 & e^{i \alpha} \end{bmatrix} = e^{- i \alpha/2} R_z (\alpha) \end{split}\]

那么其对应的线路图，依据书中的图 4.6，可以绘制为

ex-5.4.1

练习 5.5¶

练习 5.5

给出进行逆量子 Fourier 变换的一个量子线路。

对比式 (5.1)，逆 Fourier 变换可以如下定义：

\[ x_j = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} y_k e^{- 2 i \pi jk / N} \]

这实际上就是与 Fourier 变换的所有相位取负而已。因此，将图 5.1 Fourier 变换的量子线路的所有 \(R_k\) 替换为 \(R_k^\dagger\) 即得到逆 Fourier 变换的线路了。

另一种做法如书中后文所述，将线路对调也可以实现。

练习 5.6 (量子 Fourier 变换的近似)¶

练习 5.6

量子 Fourier 变换的量子线路结构，表面上需要用到的门路个数为量子比特数目的指数量级；然而，多项式规模的量子线路永远不需要这样的精度。例如，令 \(U\) 是 \(n\) 量子比特上的理想 Fourier 变换，而 \(V\) 是以精度 \(\Delta = 1 / p(n)\) 完成受控 \(R_k\) 门得到的结果，其中 \(p(n)\) 是某个多项式。证明误差

\[ E(U, V) = \max_{|\psi\rangle} \Vert (U-V) |\psi\rangle \Vert = \Theta (n^2 / p(n)) \]

因此每个门的多项式精度对保证输出状态的多项式精度就够了。

首先，回顾盒子 4.1 的式 (4.69) 结论，若量子 Fourier 变换使用图 5.1 实现，且我们假设 Hadamard 门与 swap 门可以精确实现，那么 \(E(U, V)\) 的误差可以拆分为各 \(R_k\) 门路误差的和。由于对于 \(n\) 量子比特，Fourier 变换线路需要 \(n(n-1)/2\) 个 \(R_k\) 门 (书中所说的 \(n(n+1)/2\) 个门路包含了 \(n\) 个 Hadamard 门，在误差分析中要剔除这些门路的误差贡献)，因此

\[ E(U, V) = \frac{n(n-1)}{2} \Delta = \Theta (n^2 / p(n)) \]

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