量子計算QuantumComputingCalvinTang

179209347@

—算法篇以簡御繁–本輪&均輪2世紀(jì)Start托勒密全面繼承了亞里士多德的地心說，并利用前人積累和他自己長期觀測得到的數(shù)據(jù)，寫成了8卷本的《偉大論》。地心說托勒密使用古希臘本輪–均輪系統(tǒng)具有類似級數(shù)展開的功能，即為了增加推算的精確度，可以在本輪上再加一個小輪，讓此小輪之心在本輪上繞行，而讓天體在小輪上繞行。只要適當(dāng)調(diào)諸輪的半徑、繞行方向和速度，即可達(dá)到要求。從理論上說，小輪可以不斷增加，以求得更高的精度。托勒密（約90年—168年）之后哥白尼在《天體運(yùn)行論》中放棄了這種表示，改用了更為簡潔的日心說，之后開普勒改用橢圓代替圓。（地心說可以理解為以地球為參照點觀察其它星體軌跡）以簡御繁–泰勒展開式1712Start在局部用一個多項式函數(shù)近似地替代一個復(fù)雜函數(shù)。泰勒展開式

泰勒(Taylor)（1685—1731年）

以簡御繁–傅里葉級數(shù)&傅里葉變換1811Start傅里葉級數(shù)能夠?qū)⑷我庵芷诤瘮?shù)表示成一組三角函數(shù)基函數(shù)依照各自的系數(shù)的累加。傅里葉級數(shù)（即三角級數(shù)）傅里葉(Fourier)（1768—1830年）傅里葉級數(shù)

不同頻率的三角函數(shù)即正交基(Basis)，也被稱為特征函數(shù)(Eigenfunction)，傅立葉級數(shù)的本質(zhì)就是利用無窮多組正交的傅立葉基進(jìn)行線性組合得到任意周期函數(shù)。傅里葉級數(shù)-圓周運(yùn)動的投影正弦波或者余弦波都是一個圓周運(yùn)動在一條直線上的投影。所以傅里葉級數(shù)基本單元也可以理解為一系列始終在旋轉(zhuǎn)的圓。傅里葉級數(shù)-頻域圖泰勒級數(shù)將任何函數(shù)表示為無限的單項之和；傅里葉級數(shù)可將任何周期函數(shù)表示為正弦/余弦函數(shù)之和。傅里葉級數(shù)，在時域是一個周期且連續(xù)的函數(shù)，而在頻域是一個非周期離散的函數(shù)。頻域分析-

分解周期函數(shù)這些正弦波（正弦函數(shù)）和正弦波（余弦函數(shù)）按照頻率從低到高從前向后排列。頻域分析-頻譜頻譜這些按照頻率從低到高從前向后排列的周期函數(shù)，投影形成的頻域圖像就是頻譜。其中每一個波的振幅都是不同的。傅里葉變換時域分析：以時間作為參照來觀察動態(tài)世界的方法。傅立葉變換使我們可以將信號分解為單個頻率和頻率幅度。換句話說，它將信號從時域轉(zhuǎn)換到頻域，結(jié)果稱為頻譜。頻域分析：應(yīng)用頻率特性研究線性系統(tǒng)的經(jīng)典方法。頻域圖時域圖傅里葉變換傅里葉變換，將一個時域非周期的連續(xù)信號，轉(zhuǎn)換為一個在頻域非周期的連續(xù)信號。也可以理解為對一個周期無限大的函數(shù)進(jìn)行傅里葉變換。傅立葉級數(shù)的復(fù)數(shù)形式

傅立葉級數(shù)的復(fù)數(shù)形式傅里葉變換-快速傅里葉變換（FFT）快速傅里葉變換（FFT）是一種可以有效計算傅立葉變換的算法，它廣泛用于信號處理。

傅立葉變換離散傅里葉變換（DFT）離散傅里葉變換（DFT-

DiscreteFourierTransform）是離散傅里葉級數(shù)（DFS）引申出來的，這二者的時域、頻域都是離散的，因而它們的時域、頻域又必然是周期的。但是DFT是有限長序列。

離散傅里葉變換（DFT）

離散傅里葉變換（DFT）

…

因為：

由于：所以有：

即：

同樣可得：

由于：

所以有：

逆離散傅里葉變換（IDFT）于是，我們得到了逆離散傅里葉變換（IDFT）公式：

由于：所以有：

逆離散傅里葉變換（IDFT）

量子傅里葉變換（QFT）傅立葉變換的本質(zhì)是將一個函數(shù)（通常是時間域或空間域中的函數(shù)）轉(zhuǎn)換為其頻率域表示。在量子計算中，這種轉(zhuǎn)換是通過量子傅立葉變換（QuantumFourierTransform，QFT）來實現(xiàn)的。在這個轉(zhuǎn)換過程中，QFT會將函數(shù)的振幅信息轉(zhuǎn)換為相位信息。這種轉(zhuǎn)換對于許多量子算法（如量子相位估計等）是至關(guān)重要的。量子傅里葉變換/逆變換，實質(zhì)上可以視為一種振幅和基向量的相互轉(zhuǎn)化。量子傅里葉變換不加速計算經(jīng)典數(shù)據(jù)的傅里葉變換,但它可以用做相位估計。量子傅里葉（Fourier）變換要點量子傅里葉變換（QFT）

經(jīng)典的逆離散傅里葉變換（IDFT）：

即：

量子傅里葉變換（QFT）

由于：所以有：量子傅里葉變換（QFT）

量子態(tài)的二進(jìn)制表示計算基矢態(tài)的二進(jìn)制表示：

同樣，二進(jìn)制分?jǐn)?shù)的表示：

量子態(tài)的二進(jìn)制表示

于是有：由于：

最后可得：QFT的求和形式與張量積形式

對∣???

進(jìn)行量子傅里葉變換的結(jié)果可表示為：QFT的求和形式與張量積形式

兩邊求和可得：

QFT的求和形式與張量積形式

QFT的求和形式與張量積形式

于是有：QFT的求和形式與張量積形式

于是得到：更近一步有：

QFT的求和形式與張量積形式

于是得到：QFT的求和形式與張量積形式

更近一步有：

QFT的求和形式與張量積形式

于是有：

由于：則有：QFT的求和形式與張量積形式

直積形式

二進(jìn)制展開與量子態(tài)制備

二進(jìn)制展開與量子態(tài)制備

……QFT的量子線路圖H

XX

……

H

…………H

HXX…………

……………

一個量子比特QFT線路H

所以，1個量子比特QFT線路就是H門。

兩個量子比特QFT線路H

R2HXX

三個量子比特QFT線路HSTXXHSH

逆向量子傅里葉變換（IQFT）逆向量子傅里葉變換（Inver