Man and History: Quantum Fourier Transform

Quantum Fourier Transform

2022/01/28

-----

《題西林壁》

橫看成嶺側成峰，

遠近高低各不同。

不識廬山真面目，

只緣身在此山中。

～蘇軾～

http://rthk9.rthk.hk/chiculture/chipoem/poem6.htm

-----

https://pixabay.com/zh/photos/people-girl-woman-highland-2598465/

-----

◎ 說明：

-----

Q1：簡單說明離散傅立葉變換是什麼？

-----

Fig. 1. 時域與頻域的 3D 分解圖 [8]。

A1：參考圖一。

藍色的波形由 1、3、5 Hz 的正弦波組成，顏色分別是綠色、紅色、以及青色，傅立葉變換輸入藍波，然後將這三個波的振幅計算出來。在工程上取有限點來計算，稱為離散傅立葉變換，本例取樣 100 點，可計算 1 Hz 到 50 Hz 這 50 個波的振幅分別是多少，本例是 3、1、0.5，其餘為 0 [8]。

-----

Q2：秀爾演算法為何從量子傅立葉變換開始講解？

-----

Fig. 2. From Fourier Series to Shor's Algorithm.

A2：因為量子傅立葉變換是量子相位估計的基礎，而量子相位估計又是秀爾演算法的基礎，參考圖一。

「量子傅立葉變換（QFT）是離散傅立葉變換在波函數幅度上的量子實現。它是許多量子算法的一部分，最著名的是 Shor 的因式分解算法和量子相位估計。在計算基礎上，我們使用狀態以二進制形式存儲數字 | 0 ⟩ 和 | 1 ⟩。注意不同量子比特變化的頻率。在傅立葉基礎中，我們使用圍繞 Z 軸的不同旋轉來存儲數字。我們要存儲的數字決定了每個量子位繞 Z 軸旋轉的角度。」[1]。

以上是從 Qiskit 教程摘錄下來的一段話，也可以說是我們進入量子運算演算法旅程的開始。起點為什麼選擇量子傅立葉變換呢？一般完整的教材，會從量子位元，或者基本觀念，量子態的疊加與糾纏開始。這些觀念並不是很容易接受，所以我先設立一個明確的目標，就是最有名的，可以用來破解 RSA 加密的秀爾演算法。

不過你可以看到由於秀爾演算法使用了量子相位估計（核心是量子傅立葉逆變換），所以目標馬上要往前推進到量子傅立葉變換。然後又要立刻推進到離散傅立葉變換 [8]，要不然你要如何理解秀爾演算法呢？如果要深入原理，則可以從傅立葉變換家族開始 [9]！

-----

◎ 參考資料：

-----

1. 沒有加快

-----

「下面就開始說明量子傅立葉變換，它是量子質數分解和很多其他量子算法的基礎，不過，強調一下，它沒有加快經典計算中傅立葉變換的速度。」[4]。

「從表面上看，我們實現了指數級別的加速，然而，事實上，我們並不能加速計算這個的過程，因為我們不能直接得到量子態的幅度，更糟糕的是，我們可能無法高效的製備傅立葉變換要求的初始的狀態，因此，量子傅立葉變換比我們想像的脆弱，不過我們我們可在這基礎上提出一些非常有用的算法。」[4]。

-----

2. 么正矩陣（酉矩陣）

-----

「量子傅立葉變換（quantum Fourier transform）是一種離散傅立葉變換，將原式分解成更為簡單的多個么正矩陣的積。利用這般的分解方式，離散傅立葉變換可以用作量子電路，其包含了多個哈達瑪閘與受控移相閘。」[3]。

-----

3. 么正變換（酉變換）

-----

「酉變換，所以我們能夠用量子線路實現」[4]。

-----

4. 阿達瑪閘

-----

「The quantum gates used in the circuit are the Hadamard gate and the controlled phase gate Rm.」[2]。

-----

5. 受控移相閘

-----

「The quantum gates used in the circuit are the Hadamard gate and the controlled phase gate Rm.」[2]。

-----

References

[1] Quantum Fourier Transform

https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html

[2] Quantum Fourier transform - Wikipedia

https://en.wikipedia.org/wiki/Quantum_Fourier_transform

[3] 量子傅立葉變換 - 維基百科，自由的百科全書

https://zh.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E5%82%85%E7%AB%8B%E8%91%89%E8%AE%8A%E6%8F%9B

[4] 5.1 量子傅立葉- 知乎

https://zhuanlan.zhihu.com/p/81280426

# QFT

[5] Ruiz-Perez, Lidia, and Juan Carlos Garcia-Escartin. "Quantum arithmetic with the quantum Fourier transform." Quantum Information Processing 16.6 (2017): 152.

https://arxiv.org/pdf/1411.5949.pdf

-----

[6] 和小白蔡一起入門量子計算–量子傅立葉變換（一）_量子客

https://www.qtumist.com/post/5484

[7] 第四章量子傅立葉轉換及其應用

http://www.csie.kuas.edu.tw/~changwl/quantum_computer/chapter-four/Chapter-Four.pdf

[8] 经典与量子的快速傅立叶变换 – refraction-ray

https://re-ra.xyz/%E7%BB%8F%E5%85%B8%E4%B8%8E%E9%87%8F%E5%AD%90%E7%9A%84%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E5%8F%B6%E5%8F%98%E6%8D%A2/

[9] 快速傅里葉變換(FFT)和量子傅里葉變換(QFT)_大羚羊的博客-CSDN博客_量子傅里葉變換

https://blog.csdn.net/m0_37622530/article/details/83032517

[10] Man and History: Discrete Fourier Transform in Python

https://mandhistory.blogspot.com/2022/03/discrete-fourier-transform-in-python.html