量易简

量子傅里叶变换

背景介绍

傅里叶变换（Fourier Transform，傅立叶变换），是将函数表示成一组三角函数的线性组合的过程，是一种信号分析的重要方法。傅里叶变换有离散傅里叶变换和连续傅里叶变换等多种变体形式。本节将会从离散傅里叶变换出发，重点讨论其量子版本量子傅里叶变换。

离散傅里叶变换

离散傅里叶变换（Discrete Fourier Transform, DFT）是分析有限长序列的重要工具，在诸多领域，比如频谱分析，信号处理，数据压缩，偏微分方程，长整数与多项式乘法等中，有着广泛的应用。

（ $N$ 维）离散傅里叶变换是一个 $C^{N}$ 到 $C^{N}$ 的线性映射，其将复列向量 $x := (x_{0}, \dots, x_{N - 1})$ 映射为相同维数的复列向量 $y := (y_{0}, \dots, y_{N - 1})$ ，其中

\begin{matrix} y_{k} = \frac{1}{\sqrt{N}} N - 1 \sum j = 0 x_{j} e^{2 π i j k / N} . \\ (1) \end{matrix}

如果记傅里叶变换在计算基 ${| 0 ⟩, | 1 ⟩, \dots, | N - 1 ⟩}$ 下的矩阵表示为 $F$ ，那么有：

\begin{matrix} y = F \cdot x, \\ (2) \end{matrix}

此时 $F$ 是一个 $N \times N$ 的方阵，也称离散傅里叶变换矩阵，它的第 $k$ 行第 $j$ 列元素为

\begin{matrix} F_{k j} := \frac{1}{\sqrt{N}} e^{2 π i j k / N} . \\ (3) \end{matrix}

快速傅里叶变换

基于矩阵乘法的定义，给定输入复向量 $x$ ，计算输出其离散傅里叶变换的像 $y$ 所需的时间复杂度为 $O (N^{2})$ 。库利和图基充分利用变换中的对称性和周期性，在 1965 年提出了一种复杂度低至 $O (N log N)$ 的计算傅里叶变换的算法，它和其它高效、快速计算离散傅里叶变换的方法被统称为快速傅里叶变换（Fast Fourier Transform, FFT）。我们需要注意的是，在经典计算机上，即使采用快速傅里叶变换，所需的时间复杂度依然跟维数 $N$ 是多项式相关的。

量子傅里叶变换原理

量子傅里叶变换（Quantum Fourier Transform, QFT）是离散傅里叶变换的量子对应版本，在量子算法设计中也扮演着重要角色，经常作为关键的子程序出现在各种量子算法中。已有的应用包括整数分解问题，隐子群问题（Hidden Subgroup Problem）等。

基本原理

记 ${| 0 ⟩, \dots, | N - 1 ⟩}$ 为 $N$ 维希尔伯特空间中的计算基，量子傅里叶变换 $U_{F}$ 定义为：

\begin{matrix} U_{F} | j ⟩ := \frac{1}{\sqrt{N}} N - 1 \sum k = 0 e^{2 π i j k / N} | k ⟩, j = 0, \dots, N - 1. \\ (4) \end{matrix}

因为要使用量子比特来编码，我们假设 $N = 2^{n}$ ，这里 $n$ 是编码需要使用的量子比特的数量。

习题 1. 证明式 $(4)$ 定义的矩阵 $U_{F}$ 是一个酉矩阵，即 $U_{F}^{†} U_{F} = U_{F} U_{F}^{†} = I$ 。

证明. 由式 $(4)$ 定义可知， $U_{F}$ 的矩阵形式为

\begin{matrix} U_{F} = \frac{1}{\sqrt{N}} N - 1 \sum j = 0 N - 1 \sum k = 0 e^{2 π i j k / N} | k ⟩ ⟨ j |, \\ (5) \end{matrix}

其共轭转置矩阵为

\begin{matrix} U_{F}^{†} = \frac{1}{\sqrt{N}} N - 1 \sum j^{'} = 0 N - 1 \sum k^{'} = 0 e^{- 2 π i j^{'} k^{'} / N} | j^{'} ⟩ ⟨ k^{'} | . \\ (6) \end{matrix}

因此有

\begin{matrix} U_{F}^{†} U_{F} & = ⎛ ⎝ \frac{1}{\sqrt{N}} N - 1 \sum j^{'} = 0 N - 1 \sum k^{'} = 0 e^{- 2 π i j^{'} k^{'} / N} | j^{'} ⟩ ⟨ k^{'} | ⎞ ⎠ (\frac{1}{\sqrt{N}} N - 1 \sum j = 0 N - 1 \sum k = 0 e^{2 π i j k / N} | k ⟩ ⟨ j |) = \frac{1}{N} N - 1 \sum j = 0 N - 1 \sum j^{'} = 0 (N - 1 \sum k = 0 e^{2 π i (j - j^{'}) k / N}) | j^{'} ⟩ ⟨ j | = N - 1 \sum j = 0 N - 1 \sum j^{'} = 0 δ_{j^{'}, j} | j^{'} ⟩ ⟨ j | = I, \\ (7) \end{matrix}

其中 $δ_{j^{'}, j}$ 是克罗内克 $δ$ 函数，其值为 $1$ 当且仅当 $j = j^{'}$ ，否则为 $0$ 。式 $(7)$ 中第二行到第三行利用了一个数学中常用的公式：

\begin{matrix} N - 1 \sum k = 0 e^{2 π i (j - j^{'}) k / N} = N δ_{j^{'}, j} . \\ (8) \end{matrix}

该公式可以由等比数列求和公式推导得到，感兴趣的同学可以自己动手试下。 $□$

对比离散傅里叶变换矩阵的定义，即式 $(1)$ ，我们可以注意到

\begin{matrix} U_{F} (N - 1 \sum j = 0 x_{j} | j ⟩) = N - 1 \sum k = 0 y_{k} | k ⟩, \\ (9) \end{matrix}

即如果我们将离散傅里叶变换中的 $x_{j}$ 编码到计算基 $| j ⟩$ 对应的概率幅上，那么作用量子傅里叶变换之后，输出态中的计算基 $| k ⟩$ 对应的概率幅即为 $y_{k}$ ，从而清楚地看到 DFT 和 QFT 在矩阵表达上的一致性。

习题 2. 证明式 $(9)$ 成立。

证明. 由 $U_{F}$ 的定义我们有

\begin{matrix} U_{F} (N - 1 \sum j = 0 x_{j} | j ⟩) = N - 1 \sum j = 0 x_{j} U_{F} | j ⟩ = N - 1 \sum j = 0 \frac{x_{j}}{\sqrt{N}} N - 1 \sum k = 0 e^{2 π i j k / N} | k ⟩ = & N - 1 \sum k = 0 (\frac{1}{\sqrt{N}} N - 1 \sum j = 0 x_{j} e^{2 π i j k / N}) | k ⟩ = N - 1 \sum k = 0 y_{k} | k ⟩ . \\ (10) \end{matrix}

证毕。 $□$

量子电路实现方法

由上一小节可知量子傅里叶变换的本质就是酉矩阵 $U_{F}$ ，因此，接下来我们将详细地介绍 $U_{F}$ 的量子电路的构造过程。通过将量子傅里叶变换的输出态做张量积分解，再逐个量子比特构建便可得到 $U_{F}$ 的量子电路。

注：为了与符号对应、便于阅读，本小节中量子比特的编号从 $1$ 开始。

量子傅里叶变换输出态的张量积分解。先约定整数和小数的二进制表示。给定整数 $j \in [0, 2^{n} - 1]$ ，记 $j = (j_{1} j_{2} \dots j_{n})_{2}$ 为 $j$ 的二进制展开，即 $j = j_{1} 2^{n - 1} + j_{2} 2^{n - 2} + \dots + j_{n} 2^{0}$ ，其中 $j_{1}, j_{2}, \dots, j_{n} \in {0, 1}$ 。类似地，记 $j / 2^{n} = (0. j_{1} j_{2} \dots j_{n})_{2}$ 为小数 $j / 2^{n}$ 的二进制展开，即 $j / 2^{n} = j_{1} / 2 + j_{2} / 4 + \dots + j_{n} / 2^{n}$ ；同样地，我们也可以定义 $(j_{1} \dots j_{l} . j_{l + 1} \dots j_{n})_{2}$ 。

例 1. 令 $n = 3$ ，由 $6 = 1 \times 2^{2} + 1 \times 2^{1} + 0 \times 2^{0}$ ，有 $6 = (110)_{2}$ ， $6 / 2^{3} = (0.110)_{2}$ 。

基于二进制表示，我们就可以给出量子傅里叶变换输出态的张量积表示，其对量子傅里叶变换的量子电路构造有直接的指导意义。

首先，注意到由 $n$ 个量子比特表示的量子态 $| k ⟩ = | k_{1} \dots k_{n} ⟩$ 即对应于 $k$ 的二进制表示，故我们可以将量子傅里叶变换，即式 $(4)$ 中的输出态 $| k ⟩$ 二进制展开为 $| k_{1} \dots k_{n} ⟩$ ：

\begin{matrix} U_{F} | j ⟩ & = \frac{1}{2^{n / 2}} 2^{n} - 1 \sum k = 0 e^{2 π i j k / 2^{n}} | k ⟩ = \frac{1}{2^{n / 2}} 1 \sum k_{1} = 0 \dots 1 \sum k_{n} = 0 e^{2 π i j (\sum_{l = 1}^{n} k_{l} 2^{- l})} | k_{1} \dots k_{n} ⟩, \\ (11) \end{matrix}

将 $e^{2 π i j (\sum_{l = 1}^{n} k_{l} 2^{- l})} | k_{1} \dots k_{n} ⟩$ 中指数上的求和式展开为乘法，再连同量子态关于 $l$ 做变量分离（即将与不同 $l$ 相关的变量放在一起作为整体），便得到了量子态的张量积形式：

\begin{matrix} U_{F} | j ⟩ & = \frac{1}{2^{n / 2}} 1 \sum k_{1} = 0 \dots 1 \sum k_{n} = 0 n ⨂ l = 1 e^{2 π i j k_{l} 2^{- l}} | k_{l} ⟩ . \\ (12) \end{matrix}

交换张量积和求和的顺序（这点值得读者去亲自验证），再将只有两项的求和形式展开便可得到

\begin{matrix} U_{F} | j ⟩ = \frac{1}{2^{n / 2}} n ⨂ l = 1 (1 \sum k_{l} = 0 e^{2 π i j k_{l} 2^{- l}} | k_{l} ⟩) = n ⨂ l = 1 (\frac{| 0 ⟩ + e^{2 π i j 2^{- l}} | 1 ⟩}{\sqrt{2}}) . \\ (13) \end{matrix}

然后，我们把 $j$ 二进制展开为 $(j_{1} \dots j_{n})_{2}$ ，那么输出态的第 $l$ 个量子比特就可以表示为

\begin{matrix} \frac{| 0 ⟩ + e^{2 π i j 2^{- l}} | 1 ⟩}{\sqrt{2}} = \frac{| 0 ⟩ + e^{2 π i {(j_{1} \dots j_{n - l} . j_{n - l + 1} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} = \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - l + 1} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}}, \\ (14) \end{matrix}

其中上式 $(14)$ 成立是因为 ${(j_{1} \dots j_{n - l} . j_{n - l + 1} \dots j_{n})}_{2}$ 的整数部分满足 $e^{2 π i {(j_{1} \dots j_{n - l})}_{2}} = 1$ 不影响相对相位。综合式 $(13)$ 和式 $(14)$ ，我们得到量子傅里叶变换输出态的张量积表示为

\begin{matrix} U_{F} | j ⟩ = (\frac{| 0 ⟩ + e^{2 π i (0. j_{n})_{2}} | 1 ⟩}{\sqrt{2}}) \otimes (\frac{| 0 ⟩ + e^{2 π i (0. j_{n - 1} j_{n})_{2}} | 1 ⟩}{\sqrt{2}}) \otimes \dots \otimes (\frac{| 0 ⟩ + e^{2 π i (0. j_{1} j_{2} \dots j_{n})_{2}} | 1 ⟩}{\sqrt{2}}) . \\ (15) \end{matrix}

这个表示的重要意义在于，它给出了输出态中每个量子比特的状态和输入状态的二进制展开之间的对应关系。我们只需要从输入状态 $| j ⟩$ 出发，分别构造出每个量子比特的输出态，它们的张量积即是量子傅里叶变换的输出态。

量子电路实现。由量子傅里叶变换的张量积表示式 $(15)$ 可知，我们只需要实现变换

\begin{matrix} n ⨂ l = 1 | j_{l} ⟩ ⟶ n ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - l + 1} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} . \\ (16) \end{matrix}

仔细观察可以发现，输出态的第 $l$ 个量子比特的状态与且只与输入态的第 $n - l + 1$ 到第 $n$ 个量子比特的状态相关。一个简单直接的办法是将输出态倒序，即先实现

\begin{matrix} n ⨂ l = 1 | j_{l} ⟩ ⟶ n ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{l} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}}, \\ (17) \end{matrix}

再利用 $SWAP$ 门，调整输出态各量子比特的顺序便可完整地实现 QFT：

\begin{matrix} n ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{l} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} ⟶ n ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - l + 1} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} . \\ (18) \end{matrix}

对于式 $(17)$ 中的变换的实现，考虑到中间输出态的第 $l$ 个量子比特的状态与且只与输入态的第 $l$ 到第 $n$ 个量子比特的状态相关，如果我们先将第 $l$ 个量子比特的状态变换为中间输出态对应量子比特的状态的话，位次在 $l$ 之前的量子比特便没有直接信息 $| j_{l} ⟩$ 可用，所以我们应当先实现位次在前的量子比特的变换，即：

\begin{matrix} n ⨂ l = 1 | j_{l} ⟩ ⟶ & \frac{| 0 ⟩ + e^{2 π i {(0. j_{1} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes n ⨂ l = 2 | j_{l} ⟩ ⟶ & 2 ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{l} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes n ⨂ l = 3 | j_{l} ⟩ \dots ⟶ & n ⨂ l = 1 \frac{| 0 ⟩ + e^{2 π i {(0. j_{l} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}}, \\ (19) \end{matrix}

考虑到局部过程的相似性，我们只需要对任意的 $l$ 实现变换

\begin{matrix} | j_{l} ⟩ \otimes n ⨂ k = l + 1 | j_{k} ⟩ ⟶ & \frac{| 0 ⟩ + e^{2 π i {(0. j_{l} \dots j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes n ⨂ k = l + 1 | j_{k} ⟩, \\ (20) \end{matrix}

当 $l = n$ 时上式 $(20)$ 退化为单比特情形：

\begin{matrix} | j_{n} ⟩ ⟶ \frac{| 0 ⟩ + e^{2 π i {(0. j_{n})}_{2}} | 1 ⟩}{\sqrt{2}}, \\ (21) \end{matrix}

变换 $(21)$ 所对应的矩阵便是

\begin{matrix} 1 \sum j_{n} = 0 \frac{| 0 ⟩ + e^{2 π i {(0. j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} ⟨ j_{n} | = \frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}} ⟨ 0 | + \frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}} ⟨ 1 | = \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 1 & - 1 \end{matrix}] = H, \\ (22) \end{matrix}

即 Hadamard 门的矩阵。也就是说单比特的变换 $(20)$ 和 QFT 都是 Hadamard 门。

我们再来考虑稍复杂一点的情形，当 $l = n - 1$ 时，变换 $(20)$ 退化为两比特情形：

\begin{matrix} | j_{n - 1} ⟩ | j_{n} ⟩ ⟶ \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - 1} j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes | j_{n} ⟩ . \\ (23) \end{matrix}

因为变换 $(23)$ 中量子比特 $| j_{n} ⟩$ 的状态没有变化，整个变换可以是一些在 $| j_{n - 1} ⟩$ 上的单比特量子门和 $| j_{n} ⟩$ 做为控制比特的一些量子门的组合。受变换 $(21)$ 的启发，我们可以先对 $| j_{n - 1} ⟩$ 做一个 $H$ 门：

\begin{matrix} | j_{n - 1} ⟩ | j_{n} ⟩ ⟶ (H | j_{n - 1} ⟩) \otimes | j_{n} ⟩ = \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - 1})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes | j_{n} ⟩, \\ (24) \end{matrix}

再来考虑变换

\begin{matrix} \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - 1})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes | j_{n} ⟩ ⟶ \frac{| 0 ⟩ + e^{2 π i {(0. j_{n - 1} j_{n})}_{2}} | 1 ⟩}{\sqrt{2}} \otimes | j_{n} ⟩ . \\ (25) \end{matrix}

类似于式 $(22)$ 的方法，我们可以以遍历的方式计算出变换 $(25)$ 的矩阵表示：

\begin{matrix} C (R_{2}) := ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ \begin{matrix} 1 & 0 & 0 & 0 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & e^{2 π i (0.01)_{2}} \end{matrix} ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . \\ (26) \end{matrix}

下图 2 为变换 $(23)$ 对应的量子电路：

类似 $C (R_{2})$ ，我们可以定义量子门

\begin{matrix} R_{k} := [\begin{matrix} 1 & 0 0 & e^{2 π i / 2^{k}} \end{matrix}], \\ (27) \end{matrix}

及其控制形式

\begin{matrix} C (R_{k}) := ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ \begin{matrix} 1 & 0 & 0 & 0 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & e^{2 π i / 2^{k}} \end{matrix} ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . \\ (28) \end{matrix}

值得一提的是， $C (R_{k})$ 是不区分控制比特与受控比特的量子门，即有等价量子电路:

对于变换 $(20)$ 更一般的情形可以类似地用下图 4 实现，这里就不再赘述了：

算法总结

综变换 $(17$ - $20)$ 所述， $n$ 量子比特系统的 QFT 的电路实现如下图 5：

复杂度分析

量子傅里叶变换的复杂度，即计数图 5 所示的量子电路中所使用的量子门的个数。具体来说，总计使用了 $n$ 个 $H$ 门， $\sum_{j = 1}^{n - 1} j = n (n - 1) / 2$ 个 $C (R_{k})$ 门以及 $⌊ n / 2 ⌋$ 个 $SWAP$ 门。因此，总共使用的量子门个数为

\begin{matrix} n + \frac{n (n - 1)}{2} + ⌊ \frac{n}{2} ⌋ = \frac{n (n + 1)}{2} + ⌊ \frac{n}{2} ⌋ = O (n^{2}) . \\ (29) \end{matrix}

我们可以看到这个数值与量子比特数目 $n$ 是二次关系（也即多项式关系），而与矩阵的维数 $N = 2^{n}$ 呈对数关系，即图 5 给出的量子电路是复杂度为 $Θ (n^{2})$ 的高效量子傅里叶变换算法。相对于经典的 FFT，是一种更高效地实现方式。

量子傅里叶逆变换

量子傅里叶逆变换 $U_{F}^{†}$ 定义为：

\begin{matrix} U_{F}^{†} | k ⟩ := \frac{1}{\sqrt{N}} N - 1 \sum j = 0 e^{- 2 π i j k / N} | j ⟩, k = 0, \dots, N - 1. \\ (30) \end{matrix}

在习题 1 中我们已经证明了 $U_{F}^{†} U_{F} = U_{F} U_{F}^{†} = I$ ，即式 $(30)$ 定义的矩阵 $U_{F}^{†}$ 是 $U_{F}$ 的逆矩阵。利用这个性质，我们可以根据实现 $U_{F}$ 的量子电路（如图 5 所示），通过作用每个基础量子门的逆门来得到实现 $U_{F}^{†}$ 的量子电路。注意到量子门 $H$ 和 $SWAP$ 的逆都是它们自身，而量子门 $R_{k}$ 的逆为

\begin{matrix} R_{k}^{†} := [\begin{matrix} 1 & 0 0 & e^{- 2 π i / 2^{k}} \end{matrix}], \\ (31) \end{matrix}

即 $R_{k}^{†} R_{k} = R_{k} R_{k}^{†} = I$ 。 $U_{F}^{†}$ 的量子电路如图 6 所示，其最开始部分一共有 $⌊ n / 2 ⌋$ 个 $SWAP$ 量子门，然后是 $H$ 门和控制 $R_{k}^{†}$ 门组成的一些子电路（用于实现变换 $(20)$ 的逆变换）。

由量子傅里叶逆变换的电路构造过程，我们可以看出其与量子傅里叶变换具有相同的复杂度。

例子

作为量子傅里叶变换的一个具体的例子，我们考虑三量子比特的 QFT（ $n = 3$ ）在量子计算机上的实现过程。假设某量子计算机支持以下量子门集合 ${H, S, T, X}$ ，并支持单量子比特控制操作。由 $R_{k}$ 门的定义式 $(27)$ 我们发现，

\begin{matrix} R_{2} := [\begin{matrix} 1 & 0 0 & e^{2 π i / 2^{2}} \end{matrix}] = S, R_{3} := [\begin{matrix} 1 & 0 0 & e^{2 π i / 2^{3}} \end{matrix}] = T . \\ (32) \end{matrix}

另外，我们可以使用三个 $CNOT$ 门实现一个 $SWAP$ 门。因此三量子比特 QFT 的量子电路为

另一方面，利用图 6 中构造量子傅里叶逆变换的技巧，我们也可以从上图 7 得到三量子比特的量子傅里叶逆变换的量子电路：

简例与量易伏平台演示

接下来我们展示如何在量易伏平台上实现量子傅里叶变换的电路。从其量子电路图（图 5）可知，其中最关键的步骤是我们如何实现受控 $R_{k}$ 门操作。量易伏支持双量子比特受控 $U$ 门，其中

\begin{matrix} U := [\begin{matrix} cos \frac{θ}{2} & - e^{i λ} sin \frac{θ}{2} e^{i ϕ} sin \frac{θ}{2} & e^{i (λ + ϕ)} cos \frac{θ}{2} \end{matrix}] . \\ (33) \end{matrix}

易见当 $θ = ϕ = 0, λ = 2 π / 2^{k}$ 时， $U = R_{k}$ ，从而我们可以使用受控 $U$ 门来实现受控 $R_{k}$ 门。量易伏平台上实现 QFT 的代码如下：

from QCompute import *
import numpy as np

# 不直接给出输出，后续通过print给出需要信息
from QCompute import Define
Define.Settings.drawCircuitControl = []
Define.Settings.outputInfo = False

def qft(qreg):
    """
    实现量子傅里叶变换的量子电路
    当调用 qft(qreg) 时，对存储在 qreg 中的量子态做量子傅里叶变换 |r> -> QFT|r>
    :param qreg: |r>，量子寄存器，假设调用 qft 前处于状态 |r>
    :return: None
    """
    n = len(qreg)  # 计数 qreg 中包含量子比特的数量
    # QFT 的第一步：
    for l in range(0, n):  # 外循环，每个循环对应一次变换 (20)，实现第 l 个量子比特的变换
        H(qreg[l])  # 对第 l 个量子比特做 H 门
        for k in range(2, n - l + 1):  # 内循环，每个循环对应一个 C(R_k) 门；
            # 当 l >= n - 1 时恰不需要这个内循环
            m = l + k - 1  # 计算 C(R_k) 门的控制比特的编号
            # C(R_k) 作为 CU 门 的特例直接调用，受控比特即第 l 个量子比特
            CU(0, 0, 2 * np.pi / pow(2, k))(qreg[m], qreg[l])
    # QFT 第二步：将量子比特倒序
    for l in range(0, n // 2):  # 对第 i 个和第 (n-i-1) 个量子比特做 SWAP 门
        SWAP(qreg[l], qreg[n - l - 1])

复制

我们可以用如下方式调用 QFT，这里以一个三量子比特系统为例：

def main():
    # 创建环境
    env = QEnv()
    # 选择随机数
    seed = int(2147483647*np.random.random())
    # 选择 Backend 为本地模拟器
    # 注：量易伏也支持云端模拟器和真机后端，访问 https://quantum-hub.baidu.com/ 获取更多信息。
    env.backend(BackendName.LocalBaiduSim2, '-s ' + str(seed))

    qreg = [env.Q[i] for i in range(3)]  # 生成初始化的 3 比特量子寄存器
    qft(qreg)  # 调用 qft 函数，对寄存器所储存的量子态作用 QFT
    
    shots = 1000  # 反复实验 1000 次统计结果
    MeasureZ(qreg, range(3))  # 对寄存器进行测量
    taskResult = env.commit(shots=1000, fetchMeasure=True)
    print("Shots", taskResult['shots'])
    print("Counts", taskResult['counts'])
    print("Seed", seed)


if __name__ == '__main__':
    main()

复制

测量结果如下：

Shots 1000
Counts {'100': 129, '011': 116, '101': 125, '111': 107, '000': 122, '001': 121, '110': 157, '010': 123}
Seed 1241392683

复制

在上面的演示性程序中，三量子比特的寄存器被初始化为 $| 000 ⟩$ 态，QFT 将寄存器状态演化为：

\begin{matrix} \frac{| 000 ⟩ + | 001 ⟩ + | 010 ⟩ + | 011 ⟩ + | 100 ⟩ + | 101 ⟩ + | 110 ⟩ + | 111 ⟩}{2 \sqrt{2}} . \\ (34) \end{matrix}

运行后可查看量易伏构造的 QFT 电路如下：

并获得相应的 QASM 代码为：

OPENQASM 2.0;
include "qelib1.inc";
qreg q[3];
creg c[3];
h q[0];
cu(0.0, 0.0, 1.5707963) q[1], q[0];
cu(0.0, 0.0, 0.7853982) q[2], q[0];
h q[1];
cu(0.0, 0.0, 1.5707963) q[2], q[1];
h q[2];
swap q[0], q[2];
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];

复制

最后更新时间：2021年12月20日

背景介绍
量子傅里叶变换原理
算法总结
简例与量易伏平台演示