量子傅里叶算法

2019-05-11  本文已影响0人  thuxuxs

量子傅里叶算法

经典离散傅里叶算法

对于数据点集合A=\{A_i,i=0,N-1 \}，其离散傅里叶变化为
B_j=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}{e^{2\pi i jk/N}A_k}

量子离散傅里叶算法

n比特的态可以表示成\left|j_1j_2...j_n\right>，可将态看着二进制数，从而也可将态写成十进制数表示为\left|j\right>，其中
j=[j_1\cdots j_n]=j_1 * 2^{n-1}+j_i*2^{n-i}+j_n

n=3
s='111'
k=int(s,2) # 参数2用来表示从二进制转化为十进制
s==bin(k)[2:].zfill(n) #bin函数用来转化为二进制，zfill函数用来补零

对于二进制的分数表示0.j_1j_2\cdots j_n，其表示为十进制为[0.j_1j_2\cdots j_n]=j_1*2^{-1}+\cdots+j_n*2^{-n}=\sum_{k=1}^{n}j_k*2^{-k}
我们有[0.j_1\cdots j_n]=[j_1\cdots j_n]/2^n.

n=3
s='0.011'
k=int(s[2:],2)/2**n
s=='0.'+bin(int(k*2**n))[2:].zfill(n)

对于态\left|j\right>，其傅里叶变换定义为

\left|j\right>=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi i jk/N}\left|k\right>,
其中N=2^n，设\omega_n=e^{\frac{2\pi i}{2^n}}其矩阵表示为，
\begin{pmatrix} \left|0\right>\\ \vdots\\ \left|j\right>\\ \vdots\\ \left|N-1\right> \end{pmatrix}=\frac{1}{\sqrt{N}} \begin{pmatrix}1&\cdots&1&\cdots&1\\ \vdots&\cdots&\vdots&\cdots&\vdots\\ 1&\cdots&\omega_n^{j k}&\cdots&\omega_n^{j (N-1)}\\ \vdots&\cdots&\vdots&\cdots&\vdots\\ 1&\cdots&\omega_n^{(N-1)k}&\cdots&\omega_n^{(N-1)^2}\\ \end{pmatrix} \begin{pmatrix} \left|0\right>\\ \vdots\\ \left|k\right>\\ \vdots\\ \left|N-1\right> \end{pmatrix}

根据定义
\begin{aligned} \sqrt{N}\left|j\right>&=\sum_{k=0}^{N-1}e^{2\pi ijk/N}\left|k\right>\\ &=\sum_{k=0}^{N-1}e^{2\pi i k[0.j_1\cdots j_{n}]}\left|k\right>\\ &=\sum_{(k_0,\cdots,k_{n-1})\in \{0,1\}^n}e^{2\pi i [0.j_1\cdots j_{n}]\sum_{l=1}^{n}2^{l-1}k_{n-l}}\left|k_0\cdots k_{n-1}\right>\\ &=\sum_{(k_0,\cdots,k_{n-1})\in \{0,1\}^n}\prod_{l=1}^{n} e^{2\pi i k_{n-l}[j_1\cdots j_{l-1}.j_{l}\cdots j_n]}\left|k_0\cdots k_{n-1}\right>\\ &=\sum_{(k_0,\cdots,k_{n-1})\in \{0,1\}^n}\prod_{l=1}^{n} e^{2\pi i k_{n-l}[0.j_{l}\cdots j_n]}\left|k_0\cdots k_{n-1}\right>\\ &=(\left|0\right>+e^{2\pi i [0.j_n]}\left|1\right>)\otimes \sum_{(k_1,\cdots,k_{n-1})\in \{0,1\}^{(n-1)}}\prod_{l=1}^{n-1} e^{2\pi i k_{n-l}[0.j_{l}\cdots j_n]}\left|k_1\cdots k_{n-1}\right>\\ &=\otimes_{l=1}^{n}\left(\left|0\right>+e^{2\pi i[0.j_l\cdots j_n]}\left|1\right>\right) \end{aligned}
第四个等式到第五个等式用到事实
e^{2\pi i k_{n-1}[j_1\cdots j_{l-1}.j_l\cdots j_n]}=e^{2\pi i k_{n-1}[j_1\cdots j_{l-1}]}e^{2\pi i k_{n-1}[0.j_{l}\cdots j_{n}]}=1\cdot e^{2\pi i k_{n-1}[0.j_l\cdots j_n]}

门实现

对于目标态
\begin{aligned} &\frac{1}{\sqrt{2}}(\left|0\right>+e^{2\pi i [0.j_n]}\left|1\right>)\\ &=H\left|j_n\right>\\ \end{aligned}
对于目标态
\begin{aligned} &\frac{1}{\sqrt{2}}(\left|0\right>+e^{2\pi i [0.j_{n-1}j_n]}\left|1\right>)\\ &=\frac{1}{\sqrt{2}}(\left|0\right>+e^{2\pi i [0.j_{n-1}]}e^{2\pi i [0.0j_n]}\left|1\right>) \end{aligned}
可先对\left|j_{n-1}\right>做哈德马德变换，在做用\left|j_{n}\right>控制\left|j_{n-1}\right>的相位门R_2，其中

R_m=\begin{pmatrix}1&0\\0&e^{2\pi i /(2^m)}\end{pmatrix}
具体实现如下图，最后再做sweep门交换一下态即可。

n比特量子傅里叶变换
上一篇 下一篇

猜你喜欢

热点阅读