用于快速傅立叶变换的量子电路

我们提出了一种实现快速傅立叶变换(FFT)的算法，它是由若干量子门组合而成的量子电路。在我们的实现中，数据序列由向量空间的张量积来表示。也就是说，我们的快速傅立叶变换被定义为量子态的张量积的变换。它与所谓的量子傅里叶变换(QFT)有本质的不同，QFT被定义为量子态叠加幅度的线性变换。FFT的量子电路由几个用于基本算术运算的电路组成，例如量子加法器、减法器和移位运算，这些电路被尽可能有效地实现。也就是说，我们的电路不会生成任何垃圾位。与QFT相比，我们的方法的优点是它的通用性强，并且在例如量子图像处理方面的数据存储效率。

量子计算利用量子力学固有的量子纠缠和量子叠加，正在迅速取得进展，以克服经典计算的局限性。Shor的算法[1]在多项式时间内解决整数因式分解问题，Grover的算法[2]使得在非结构化数据库中的搜索速度大大加快脚注1是量子计算惊人特性的最著名的例子之一(例如，对于量子计算的各种应用，参见[6])。

傅里叶变换作为量子电路的实现有时在量子计算中起着至关重要的作用。事实上，量子傅立叶变换(QFT)[7]是许多重要量子算法的关键组成部分，包括Shor因子分解算法和估计酉算子特征值的量子相位估计算法。这里，QFT是量子态振幅的傅里叶变换：

其中N=2^n，振幅(Xk)是振幅(Xj)的经典离散傅立叶变换。

其中\(W_N：=\exp(-2\pi I/N)\)。由于态(1.1)和量子并行性的叠加，QFT可以在由O(n^2)个量子门组成的量子电路中实现，这比计算复杂度为O(n2^n)的快速傅立叶变换(FFT)[8]要高效得多。

我们在本文中考虑的傅里叶变换与QFT有所不同：我们提出了FFT而不是QFT算法的量子实现。在我们的过程中，数据序列用向量空间的张量积表示：\(\BigoTimes_{j=0}^{N-1}|x_j\Rangle\)。即，通过所谓的基编码来准备表示给定经典信息的状态向量[9]。(另一方面，QFT(1.1)基于幅度编码。)。基于基编码，傅里叶变换被定义为。

其中数据序列\(xk\)是如(1.2)所示的\(xj\)的傅立叶变换。我们采用可逆FFT[10]作为上述傅里叶变换的算法，并将其实现为计算复杂度为O(n2^n)的量子电路。从这个角度来看，只要我们只考虑单一的数据序列，处理速度就与经典的处理速度相同。尽管如此，与经典的FFT相比，甚至与QFT相比，它有以下优点。第一个原因是量子平行。也就是说，利用多个数据集的量子叠加，我们可以同时处理它们。注意，这里存在几个问题，如何在量子态中编码经典数据(以及如何读取合成的叠加量子数据)，这是量子计算所特有的。为了利用量子计算的优势，需要一个适合于量子计算的qRAM[3，4，5][有关包括数据编码在内的经典FFT和我们的量子版本的FFT(让我们将其表示为QFFT)之间的计算成本的比较，请参见第295节]。第二个原因是它的通用性很强：该方法总是适用于传统FFT可以处理的数据集。第三个优点是它的数据存储效率，例如，就量子图像而言(参见[11，12，13，14]以了解量子数据集的一些应用)。

左面板中描绘了灰度值从0到(M-1)((M=2^m))的2×2像素图像。右侧面板中的\(X_{j，k}\)表示(j，k)站点上的灰度值。量子图像可以表示为\(|x_{0，0}\Rangle\oTimes|x_{0，1}\Rangle\oTimes|x_{1，0}\Rangle\oTimes|x_{1，1}\Rangle\in(\mathbb{C}^2)^{\oTimes 4M}\)

让我们用一个简单的例子来说明上面的第三个优点：灰度值从0到(M-1)(M=2^m)的L×L\)像素图像(参见图)。1代表\(L=2\))。(这个问题等价于L×L正方形晶格上的晶格量子多体问题，每个格点由一个M个自由度的粒子占据。)。这个量子图像\(|\psi^{(\alpha)}\rangle\)(\(\alpha\)表示图像的标签)可以用向量空间[15，16，17，18]的张量积表示：

$$\BEGIN{对齐}|\psi^{(\alpha)}\rangle=\bigoTimes_{(j，k)=(0，0)}^{(L-1，L-1)}|x^{(\alpha)}_{j，k}\rangle，\qquad 0\le x^{(\alpha)}_{j，k}\le M-1。\结束{对齐}$$。

由于(|\psi^{(\alpha)}\rangle\in(\mathbb{C}^2)^{\oTimes m L^2}\)，它使用\(mL^2)个量子比特。利用量子叠加，QFFT最多可以同时处理2^{mL^2}个量子图像：

$$\BEGIN{ALIGNED}|\psi\rangle=\sum_{\alpha=1}^{2^{mL^2}}c_{\alpha}|\psi^{(\alpha)}\rangle\in(\mathbb{C}^2)^{\oTimes m L^2}\qquad(c_{\alpha}\in\mathbb{C})。\结束{对齐}$$。

另一方面，要将量子傅立叶变换应用到上述图像处理中，需要将量子图像制备成。

其中\(|\widetilde{\psi}^{(\alpha)}\Rangle\in(\mathbb{C}^2)^{\oTimes 2\log_2L}\)仅使用\(2\log_2L\)量子位[参见。(1.4)QFFT][19、20、21]。然而，由于傅立叶系数[见(1.1)和(1.2)]被表示为叠加的振幅，要完全提取它们需要指数级的长时间。此外，为了正确地对多个\(2^{m L^2})个量子图像执行傅里叶变换，必须将它们表示为。

$$\BEGIN{ALIGNED}|\widetilde{\psi}\rangle=\bigoTimes_{\alpha=1}^{2^{mL^2}}|\widetilde{\psi}^{(\alpha)}\rangle\in(\mathbb{C}^2)^{\oTimes(2^{mL^2+1})\log_2L}。\结束{对齐}$$。

也就是说，对于QFT，需要((2^{mL^2+1})\log2L\)个量子比特来处理(2^{m L^2})个量子图像，这些量子比特远远大于QFFT的(m L^2)个量子比特。此外，QFT必须单独应用于每个图像，因为数据集(1.7)不是图像的叠加，而是每个图像的张量积。脚注2因此，当量子图像的数量足够大时，QFFT的总处理时间比QFT短。

本文通过实现一些基本的算术运算，如量子加法器[22，23，24，25，26，27]，减法器[28，29，30，31]和新开发的移位型运算，尽可能高效地构造了上述QFFT的量子电路：我们的量子电路不产生任何无用信息位。

这篇论文的提纲如下。在接下来的部分，介绍FFT的量子版本的算法，我们将展示将QFFT实现为量子电路所需的基本算术运算。在第三节中，我们实际上将这些基本算术运算实现到量子电路中。在第四节中，我们将这些基本电路有效地结合起来，构造了QFFT的量子电路。第五节估计了实现QFFT所需的量子门数量。本节还讨论了经典FFT和QFFT之间的计算成本，包括数据编码。在第六节中，我们举例说明了QFFT的一个具体应用实例。第七节专门进行总结和讨论。一些技术细节将推迟到附录中。

在本节中，我们将介绍FFT的量子版本的算法，并图形化地表示将QFFT实现为量子电路所需的几种算术运算。(例如，有关FFT的详细算法，请参见[32]。)。我们只使用基编码的方法来获得量子态。这里介绍的矩阵式符号对量子算法的实现很有帮助。

让我们从傅立叶变换的公式(1.2)和(1.3)开始。设置\(W_{N}=\exp(-2\pi I/N)\)\((N=2^n)\)并将(1.2)中的求和分解为奇数和偶数部分，我们得到。

$$\BEGIN{Alignment}\Left|X_k\Right\Rangle=\Left|G^{(n-1，0)}_k+W_{N}^{k}G^{(n-1，1)}_k\Right\Rangle，\Left|X_{k+N/2}\Rangle=\Left|G^G^{(n-1，0)}_k-W_{N}^k G^{(n-1，1)}_k\Rangle，\end{aligned}$。

其中\(0\le k\le N/2-1\)和\({G_k^{(n-1，p)})(\(p=0，1\))是\(x2r+p}\}\)\((0\le r\le N/2-1)\)的傅立叶系数：

注意\(G^{(n-1，p)}_{k+N/2}=G^{(n-1，p)}_k\)和\(W^{N/2}_N=-1\)成立。通常，\(X_k\)是一个复数，记号\(\Left|X_k\Right\Rangle\)表示\(\Left|(X_K)_r\Right\rangle\Left|(X_K)_i\Right\Rangle\)，其中\((X_K)_r\)和\((X_K)_i\)分别是\(X_K)的实部和虚部。如图所示，(2.1)可以表示为所谓的蝴蝶图：

其中\(0\le k\le N/2-1\)。这里，虚线表示乘以\(-1\)。为方便起见，我们还将其表示为类似矩阵的表示法：

$$\BEGIN{ALIGNED}\BEGIN{bMatrix}|X_k\Rangle\\|X_{k+N/2}\Rangle\end{bMatrix}=\Begin{bMatrix}1&；{}1\\1&；{}-1\\end{bMatrix}\Begin{bMatrix}1&；0\\0&；{}W_N^k\end{bMatrix}\Begin{bMatrix}\Left|G^{(n-1，0)}_k\Rangle\Left|G^{(n-1，1)}_k\Rangle\Rangle\end{bMatrix}=\Begin{bMatrix}\Left|G^{(n-1，0)}_k+W_{N}^{k}G^{{(n-1，1)}_k\Rangle\Left|G^{{(n-1，0)}_k-W_{N}^。{k}G^{(n-1，1)}_k\right\rangle\end{bMatrix}。\结束{对齐}$$。

$$\BEGIN{ALIGNED}\BEGIN{bMatrix}A&；{}B\\C&；{}D\End{bMatrix}\Begin{bMatrix}|a\Rangle\\|b\Rangle\End{bMatrix}=\Begin{bMatrix}|A a+B b\Rangle\C a+D d\Range\End{bMatrix}\quad(A，B，C，D\in\mathbb{C})。\结束{对齐}$$。

不要将上述操作与传统的矩阵运算混淆：结果不是\(|a\rangle\)和\(|b\rangle\)的线性组合。类似矩阵的符号对于将量子算法实现为量子电路很有用。

我们再一次分解\(x2r}\}\)的傅里叶变换。\({x{2R+1}\}))分为\({x{4s}\})和\({x4s+2}\})(分别为：\{x4s+1})和({x4s+2})(分别为：\{x4s})和({x4s+2})。\({x_{4s+1}\}\)和\({x_{4s+3}\})(\(0\le s\le N/4-1\))。结果为。

$$\BEGIN{对齐}\BEGIN{bMatrix}\Left|G_k^{(n-1，p)}\Right\Rangle\\Left|G_{k+N/4}^{(n-1，p)}\Right\Rangle\end{bMatrix}=\Begin{bMatrix}\Left|G_k^{(n-2，p)}+W_{N/2}^k G_k^{(n-2，p+2)}\Right\Rangle\Left|G_k^{(n-2，p)}\Right\Rangle\Left|G_k^{(n-2，p)}\Right\Rangle\Left|G_k^{(n-2，p)}。P)}-W_{N/2}^k G_k^{(n-2，p+2)}\right\RangeEnd{bMatrix}\quad(p=0，1；0\le k\le N/4-1)，\end{aligned}$$。

$$\BEGIN{ALIGNED}G_k^{(n-2，q)}=\sum_{s=0}^{N/4-1}W_N^{4SK}x_{4s+q}\quad(0\le q\le3；\，\，0\le s\le N/4-1)。\结束{对齐}$$。

$$\BEGIN{ALIGNED}\BEGIN{bMatrix}\Left|G_k^{(n-m，p)}\Right\Rangle\\Left|G_{k+N/2^{m+1}}^{(n-m，p)}\Right\Rangle\end{bMatrix}=\Begin{bMatrix}\Left|G_k^{(n-m-1，p)}+W_{N/2^m}^k G_k^{(n-m-1，P+2^{m})}\right\Rangle\\Left|G_k^{(n-m-1，p)}-W_{N/2^m}^k G_k^{(n-m-1，p+2^{m})}\right\range\end{bMatrix}，\end{aligned}$。

这是QFFT的算法。经典版本仅通过将状态向量解释为标量来重现。

最重要的是，QFFT/FFT被分解成\(\log_2N\)“层”，每层由N/2个蝶形图组成(关于\(N=8)，见图2)：QFFT/FFT中全部使用\((N\log_2N)/2\)图。结果，通过上述过程，傅立叶变换(1.2)的总计算复杂度从O(N^2)降低到O(N\log2N)。

(N=8)的QFFT\(\BigoTimes_{j=0}^{N-1}|x_j\Rangle\Longmapsto\BigoTimes_{k=0}^{N-1}|X_k\Rangle\)的图示。这里，\(W_{k}=\exp(-2\pi i/k)\)和\(G^{(j，p)}_k\)由递归关系(2.8)和(2.9)确定。

如(2.4)所示，为了在量子电路中实现QFFT，矩阵的乘法。

应该从量子计算的角度来进行。第一种是通过LDU分解将其分解为加法器、减法器和移位算子。

$$\Begin{Alignment}\Left[\Begin{Matrix}1&；{}1\\1&；{}-1\End{Matrix}\Right]=\Left[\Begin{Matrix}1&；{}0\\1&；{}-1\End{Matrix}\Right]\Left[\Begin{Matrix}1&；2\End{Matrix}\Right]\Left[\Begin{Matrix}1&；{}1\\0&；{}1\End{Matrix}\Right]。\结束{对齐}$$。

利用(2.4)中的类似于矩阵的表示法，可以将(2.4)中定义的第一矩阵对状态\(|a\rangle\)和\(|b\rangle\)的动作图形化地解释为。

再次注意，上述运算不同于传统的矩阵运算。另一方面，第二个矩阵简单地表示为。

因此，QFFT可以实现为由加法器、减法器和移位算符组成的量子电路。在下一节中，我们将解释这些算术运算符。这些运算符在蝶形运算(2.14)中的实际实现将推迟到第2.14节。

在这一部分中，我们图形化地介绍了一些量子算术运算的概念，如量子加法器、减法器和移位运算符，这些运算是将QFFT实现为量子电路所必需的。

这里，我们采用二的补码记数法来表示负数。让我们使用二进制表示\(|a\rangle=|a_{n-1}\cdots a_0\rangle：=|a_{n-1}\rangle\oTimes\otime|a_0\rangle\)(\(a_j\in\{0，1\}))来写一个状态\(|a\rangle\)\((a\ge 0)\)。设m(\(m>；n\))是系统的量子比特总数。让我们将\(|a\rangle\)表示为。

其中\(a_+=0\)。然后，负数\(|b\rangle\)(\(=|-a-1\rangle\))可以由\(|a\rangle\)的补码表示：

其中\(a_-=\bar{a}_+=1\)、\(\bar{0}=1\)和\(\bar{1}=0\)。也就是说，对于m量子比特系统，数字(-2^{m-1}，-2^{m-1}+1，\dots，2^{m-1}-1)可以用这个记号来表示。例如，\(m=3\)。

$$\BEGIN{ALIGNED}\BEGIN{array}{llll}|0\Rangle=|000\Rangle，&；{}\quad|1\Rangle=|001\Rangle，&；{}\quad|2\Rangle=|010\Rangle，&；{}|3\Rangle=|011\Rangle，\\-4\Rangle=|100\Rangle，&；{}\quad|-3\Rangle=|101\Rangle，&；{}\quad|-2\Rangle=|110\Rangle，&；{}\Quad|-1\Rangle=|111\Rangle。\结束{数组}\结束{对齐}$$。

在实际计算中，为了避免溢出，有时需要增加位数(即所谓的符号扩展)。只需将\(a_{\pm}\)插入表示即可实现此操作：例如，可以将m-量子比特系统的表示扩展为l-量子比特系统的表示(\(l>；m\))：

在图3中，我们展示了一种将位数从4量子比特增加到6量子比特的量子电路。

在附录中，讨论了QFFT所需的额外量子位数\(a_{\pm}\)。

将位数从4量子比特\(|a_{\pm}a_2a_1 a_0\Rangle\)增加到6量子比特\(|a_{\pm}a_2a_1 a_0\Rangle\)的操作，其中\(a_+=0\)(。\(a_-=1\))表示正(分别为。负)编号。扩展状态是通过CNOT门复制\(a_{\pm}\)来实现的。

让我们考虑一个加法器和一个减法器，稍微修改[27，31]中的论点。

用于(|a_{\pm}a_{\pm}a_2a_1a_0+b_{\pm}b_{\pm}b_2b_1b_0\rangle\)的加法器电路。该电路由图5中定义的Toffoli门和Peres门组成。\(c_j\)和\(s_j\)(\(j=1，2，3\))是(3.6)中定义的进位位和和位。

具有二进制表示\(a=a_{n-1}\cdots a_0\)和\(b=b_{n-1}\cdots b_0\)(\(a_j，b_j\in\0，1\))的两个n位数的相加计算如下。

其中进位位\(c_j\)和和位\(s_j\)(\(j=1，\cdots n\))由下式定义。

$$\BEGIN{ALIGNED}c_j&；={\Left\{\Begin{array}{ll}a_0 b_0&；{}(j=1)\\a_{j-1}b_{j-1}\o plus b_{j-1}c_{j-1}\o plus c_{j-1}a_{j-1}&；{}(2\le j\le n)\end{array}\right。}，\non number\\s_j&；={\Left\{\Begin{array}{ll}a_0\Oplus b_0&；{}(j=0)\\a_j\Oplus b_j\Oplus c_j&；{}(1\le j\le n-1)\\a_{\pm}\Oplus b_{\pm}\Oplus c_n&；{}(j=n)\end{array}\右。}。\结束{对齐}$$。

请注意，符号\(\Oplus\)表示异或运算。就量子电路而言，这种加法是在态的变换中实现的。

图4显示了实际电路，它是最初在[27]中开发的量子加法器的略微修改版本。加法器电路由如图5中定义的Toffoli门[33]和Peres门[34]组成，其中V和\(V^{\dagger}\)分别由下式给出

$$\BEGIN{ALIGNED}V=\frac{1+i}{2}\Begin{pMatrix}1&；{}-i\\-i&；{}1\end{pMatrix}，\quad V^{\dagger}=\frac{1-i}{2}\Begin{pMatrix}1&；{}i\\i&；{}1\end{pMatrix}。\结束{对齐}$$。

Toffoli门(左图)和佩雷斯门(右图)。V和\(V^{\Dagger}\)由(3.9)定义。Toffoli和Peres门分别需要5个和4个量子门。

另一方面，使用恒等式\(\overline{\overline{a}+b}=a-b\)，我们将量子减法器定义为。

$$\BEGIN{ALIGNED}|a\Rangle\oTimes|b\Rangle\Longmapsto{\Left\{\Begin{array}{ll}|a\Rangle\oTimes|\overline{a}+b}\Rangle=|a\Rangle\oTimes|a-b\Rangle\\a\Rangle\oTimes|\overline{a+\overline{b}}\Rangle=|a\Rangle\oTimes|-a+b\Rangle\end{array}\right。}，\结束{对齐}$$。

这可以通过将NOT门(用符号\(\Bigoplus\)表示)插入上述加法器(3.8)[31]来实现：

用于\(n_{\mathm{in}}\)-量子比特输入数据的加法器的量子电路由6个“层”组成，如图4所示。(此处请注意，层数与\(n_{\mathm{in}}\)无关。)。第一层、第二层、第五层和第六层分别包含\(n_{\mathm{in}-1\)、\(n_{\mathm{in}-2\)、\(n_{\mathm{in}}-2\)和\(n_{\mathm{in}}-1\)CNOT门。第三层由\(n_{\mathm{in}-1\)Toffoli门组成：\(5(n_{\mathm{in}}-1)-1)需要CNOT门。第四层包含\(n_{\mathm{in}}-1\)个Peres门和一个CNOT门：\(4(n_{\mathm{in}})-1)+1\)个CNOT门。请注意，Toffoli(分别为。Peres)GATE需要5个(分别为。4)CNOT门如图5所示。因此，对于\(n_{\mathm{in})-量子比特数据的加法器电路总共需要\(13 n_{\mathm{in}}-14\)个量子门。另一方面，(3.11)中定义的减法器最多需要3个n\mathm{in}}个CNOT门，因此减法器总共需要16个n\mathm{in}-14个量子门。

我们可以通过带非门的加法器来改变输入数字的符号：

此操作通过将数字向左移位(算术左移)来执行：

$$\BEGIN{ALIGNED}|a\rangle=|\下括号{a_{\pm}\dots a_{\pm}}_{m-n}a_{n-1}\dots a_0\rangle\long mapsto|\下括号{a_{\pm}\dots a_{\pm}}_{m-n-p}a_{n-1}\dots a_0\下括号{0\cdots 0}_p\Rangle=|2^p a\Rangle。\结束{对齐}$$。

以类似的方式，我们可以定义算术右移位，它是乘以\(2^{-p}\)的运算：

$$\BEGIN{ALIGNED}|a\rangle=&；|\下括号{a_{\pm}\dots a_{\pm}}_{m-n}a_{n-j-1}\dots a_{0}a_{-1}\cdots a_{-j}\Rangle\non number\\&；\lo。

.