论文标题
重新审视量子傅里叶变换
Quantum Fourier Transform Revisited
论文作者
论文摘要
快速傅立叶变换（FFT）是20世纪最成功的数值算法之一，在计算科学和工程的许多分支中都发现了许多应用。 FFT算法可以从离散傅立叶变换（DFT）矩阵的特定矩阵分解中得出。在本文中，我们表明，可以通过将FFT基质分解的对角因子分解为具有Kronecker产品结构的矩阵产物来得出量子傅立叶变换（QFT）。我们分析了这种Kronecker产品结构对古典计算机上rank-1张量的离散傅立叶变换的含义。我们还解释了为什么这样的结构可以利用重要的量子计算机功能，从而使QFT算法能够在经典计算机上的FFT算法上实现量子计算机上的指数加速。此外，建立了DFT矩阵的基质分解与量子电路之间的连接。我们还讨论了radix-2 QFT分解为radix-d QFT分解的自然扩展。不需要量子计算的先验知识才能了解本文中提出的内容。但是，我们认为本文可以帮助读者从矩阵计算的角度获得对量子计算本质的一些基本理解。
The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank-1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix-2 QFT decomposition to a radix-d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.
