量子傅里叶算法

作者: thuxuxs | 来源:发表于2019-05-11 21:48 被阅读0次

量子傅里叶算法
傅里叶分析
Fortran傅里叶级数逼近
关于傅里叶变换的理解
一、连续函数傅里叶级数与傅里叶变换
傅里叶级数数学推导&傅里叶变换分析学习笔记
傅里叶分析
傅里叶级数
傅里叶分析
傅里叶级数

量子傅里叶算法

经典离散傅里叶算法

对于数据点集合 $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$ ，其中