量子计算 [5] -- QFT & 相位估计

2021-04-23 14:46 作者:nyasyamorina 0人读过 | 我要投稿

QFT, 即量子傅里叶变换(Quantum Fourier Transform), 既然是傅里叶变换, 那么肯定跟频率分析脱不了关系. 关于傅里叶变换的细节这里就不再叙述, 感兴趣的可以翻一下我最初的几篇专栏看.

在开始正文前, 需要声明一下量子计算里大端小端的问题. 根据排列方式的不同, 算法实现上也存在不同. 下面为大端(big endian)和小端(little endian)的区别

在形形色色的量子电路里, 有的是大端, 有的是小端, 需要时常注意他们的区别. 实际使用的时候按照个人习惯就好.

以下使用大端的方式表示电路, 习惯小端的读者需要自行逆序一下.

QFT

QFT类似于DFT(离散傅里叶变换, Discrete Fourier Transform), DFT定义为序列 {x_j} 到序列 {y_k} 的映射: $DFT%3A%5C%3By_k%3D%5Csum_%7Bj%3D0%7D%5E%7BN-1%7De%5E%7B-2%5Cpi%20ijkN%5E%7B-1%7D%7Dx_j$ , N为序列长度. 相似地, QFT定义为态到态的映射: $QFT%3A%5C%3B%7Cj%5Crangle%5Crightarrow%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5Cpi%20ijk2%5E%7B-n%7D%7D%7Ck%5Crangle$ , n为组成态的量子位数量.

可以观察到, QFT的定义与DFT定义里, 指数部分相差了一个负号, 也就是说, 忽略归一化因子时, QFT应该为IDFT(逆DFT, inverse DFT), 而IQFT为DFT. [不要问我为什么是这样子定义的, 大家都是这样子定义的]

构造QFT电路

把QFT定义改写为张量积形式为 $QFT%3A%5C%3B%7Cj%5Crangle%5Crightarrow%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Cbigotimes_%7Bl%3D1%7D%5E%7Bn%7D%5Cleft(%7C0%5Crangle%2Be%5E%7B2%5Cpi%20ij2%5E%7B-l%7D%7D%7C1%5Crangle%5Cright)$ , 大⊗为张量积版本的累积符号, 张量积顺序为从左到右, 即: $%5Cbigotimes_%7Bx%3D1%7D%5En%7Cx%5Crangle%3D%7C1%5Crangle%5Cotimes%7C2%5Crangle%5Cotimes%5Ccdots%5Cotimes%7Cn%5Crangle$ , 推导过程可以参考本节结尾.

为了看得更清晰, 记 $e(x)%3De%5E%7B2%5Cpi%20ix%7D$ , 则忽略归一化因子的第 l 个量子位末态为 $%7C0%5Crangle%2Be(j2%5E%7B-l%7D)%7C1%5Crangle$ , 使用二进制表示为 $%7C0%5Crangle%2Be(j_n%5Ccdots%20j_%7Bl%2B1%7D.j_l%5Ccdots%20j_1)%7C1%5Crangle$ , 因为e(x)的周期性 $e(x%2B1)%3De(x)$ , 则末态为 $%7C0%5Crangle%2Be(0.j_l%5Ccdots%20j_1)%7C1%5Crangle$ , 可以看出可以由一系列控制相位旋转门制备这个状态: $%7C0%5Crangle%2B%5Cleft(%5Cprod_%7Bm%3D1%7D%5E%7Bl%7Dj_%7Bl-m%2B1%7De(2%5E%7B-m%7D)%5Cright)%7C1%5Crangle$ , 并且由H门的定义可以得到: $H%7Cj_l%5Crangle%3D%7C0%5Crangle%2Be(0.j_l)%7C1%5Crangle$ .

如此得到QFT的电路:

其中相位旋转门定义为 $R_t%3D%5Cbegin%7Bbmatrix%7D1%260%5C%5C0%26e(2%5E%7B-t%7D)%5Cend%7Bbmatrix%7D$ , 受量子位 $%7Cs%5Crangle$ 控制的Rt门作用在 $%7C1%5Crangle$ 态上的净效应为 $%7C1%5Crangle%5Crightarrow%20se(2%5E%7B-t%7D)%7C1%5Crangle$ .

注意到电路里任意一个量子位, 比如说 $%7Cj_n%5Crangle$ , 经过H门和受控相位旋转门后变为 $%7Cj_n%5Crangle%5Crightarrow%7C0%5Crangle%2B(e(0.j_n)%5Ccdot%20e(0.0j_%7Bn-1%7D)%5Ccdots%20e(0.%5Ccdots%20j_1))%7C1%5Crangle$ , 可以看出这个值应该为张量积版QFT定义最右边的状态, 然而这里使用大端定义, 也就是张量积最右边的量子位应该为电路的最下方, 也就是说需要对量子位的顺序进行翻转才符合QFT的定义, 所以电路末端存在一堆SWAP门.

SWAP门用于交换两个量子位的状态, 定义如下:

由于SWAP门的成本有丶小高, 而且不换顺序依然是成功做了傅里叶变换, 所以很多情况下实际电路是不考虑QFT电路末端的SWAP门的.

关于QFT的逆变换IQFT也不过多叙述, 逆向计算QFT的电路就好, 需要注意的是, 相位旋转门的逆是反向旋转相应的角度.

QFT张量积形式推导

用二进制表示目标态 $%7Ck%5Crangle$ , 则QFT定义为 $QFT%3A%7Cj%5Crangle%5Crightarrow%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5Cpi%20ij(%5Csum_%7Bl%3D1%7D%5E%7Bn%7Dk_l2%5E%7Bl-1%7D)2%5E%7B-n%7D%7D%7Ck_n%5Ccdots%20k_1%5Crangle$ , 把相位分配到各个量子位上有 $%5Csum_%7Bk_n%3D0%7D%5E%7B1%7D%5Ccdots%5Csum_%7Bk_1%3D0%7D%5E%7B1%7D%5Cbigotimes_%7Bl%3Dn%7D%5E1e%5E%7B2%5Cpi%20ijk_l2%5E%7Bl-n-1%7D%7D%7Ck_l%5Crangle$ , 交换累积和累加的顺序有 $%5Cbigotimes_%7Bl%3Dn%7D%5E1%5Csum_%7Bk_l%3D0%7D%5E1e%5E%7B2%5Cpi%20ijk_l2%5E%7Bl-n-1%7D%7D%7Ck_l%5Crangle$ , 即 $%5Cbigotimes_%7Bl%3Dn%7D%5E%7B1%7D%5Cleft(%7C0%5Crangle%2Be%5E%7B2%5Cpi%20ij2%5E%7Bl-n-1%7D%7D%7C1%5Crangle%5Cright)$ , 最后调整累积索引 $n%2B1-l%5Crightarrow%20l$ 得到 $%5Cbigotimes_%7Bl%3D1%7D%5E%7Bn%7D%5Cleft(%7C0%5Crangle%2Be%5E%7B2%5Cpi%20ij2%5E%7B-l%7D%7D%7C1%5Crangle%5Cright)$

相位估计

对于一个位门[也就是矩阵] $U$ , 必定存在至少一个态[也就是向量] $%7Cu%5Crangle$ 使得 $U%7Cu%5Crangle%3D%5Clambda%7Cu%5Crangle$ , 其中λ是数字, 称 $%5Clambda$ 和 $%7Cu%5Crangle$ 为 $U$ 的特征值和特征态. 每个特征态都对应一个特征值, 但一个特征值不一定对应一个特征态.

对于位门[也就是酉矩阵]来说, 特征值的模长必定为1, 也就是说 $%5Clambda%3De%5E%7Bi%5Ctheta%7D%3De%5E%7B2%5Cpi%20i%5Cvarphi%7D$ , 其中 $%5Cvarphi$ 的范围为 [0,1). 因为相位可以到处乱扔, $%7Cx%5Crangle(%5Clambda%7Cy%5Crangle)%3D(%5Clambda%7Cx%5Crangle)%7Cy%5Crangle$ , 不能看出下面电路可以从位门U里提取特征值λ

其中特征态 $%7Cu%5Crangle$ 表示为 $%7Cu_m%5Ccdots%20u_1%5Crangle$ , 不难看出第一个量子位的末态与QFT的末态十分相似. 设 $2%5En%5Cvarphi%3Dj$ , 则上述电路第一个量子位的末态与QFT电路最后一个量子位的末态相同.

根据等式 $%5Cunderbrace%7BU%5Ccdots%20U%7D_%7Bn%7D%7Cu%5Crangle%3D%5Clambda%5En%7Cu%5Crangle$ , 构造以下电路

其中 $U%5E%7B2%5En%7D$ 表示 $U$ 被执行 $2%5En$ 次. 不难看出, 电路上半部分的末态与QFT的末态一致, 也就是说对上半部分的末态执行IQFT可以得到 $2%5En%5Cvarphi$ .

实例1

以X门为例, X门有两个特征态和特征值 $%7Cu_1%5Crangle%3D%7C%2B%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt2%7D(%7C0%5Crangle%2B%7C1%5Crangle)%3B%5Clambda_1%3D1$ 和 $%7Cu_2%5Crangle%3D%7C-%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt2%7D(%7C0%5Crangle-%7C1%5Crangle)%3B%5Clambda_2%3D-1$ , 下面代码使用第二个特征态求特征值

输出值为 -1, 附带少许浮点数精度误差

误差分析

注意到 $2%5En%5Cvarphi%3Dj%3Bj%5Cin%5Cmathbb%7BZ%7D$ . 如果 $%5Cvarphi$ 是无限小数或n不够大时必定存在误差, 下面来分析一下这个误差.

在执行IQFT前, 不考虑特征值寄存器 $%7Cu%5Crangle$ 的系统状态为 $%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Cbigotimes_%7Bl%3D1%7D%5En(%7C0%5Crangle%2Be%5E%7B2%5Cpi%20i%5Cvarphi2%5E%7Bn-l%7D%7D%7C1%5Crangle)$ , 不难写为累加式 $%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5Cpi%20i%5Cvarphi%20k%7D%7Ck%5Crangle$ , IQFT定义为 $QFT%5E%7B-1%7D%3A%7Ck%5Crangle%5Crightarrow%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bj%3D0%7D%5E%7B2%5En-1%7De%5E%7B-2%5Cpi%20ijk2%5E%7B-n%7D%7D%7Cj%5Crangle$ , 则执行IQFT后系统状态变为 $%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5Cpi%20i%5Cvarphi%20k%7D%5Csum_%7Bj%3D0%7D%5E%7B2%5En-1%7De%5E%7B-2%5Cpi%20ijk2%5E%7B-n%7D%7D%7Cj%5Crangle$ , 化简得 $%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7Bj%3D0%7D%5E%7B2%5En-1%7D%7Cj%5Crangle%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5E%7B1-n%7D%5Cpi%20ik(2%5En%5Cvarphi-j)%7D$ .

设测量量子位得到结果 $j_0$ , 则测量概率可以写为 $P(j_0)%3D%5Cleft%7C%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7Bj%3D0%7D%5E%7B2%5En-1%7D%5Clangle%20j_0%7Cj%5Crangle%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5E%7B1-n%7D%5Cpi%20ik(2%5En%5Cvarphi-j)%7D%5Cright%7C%5E2$ , 只有j等于j_0时内积 $%5Clangle%5Ccdot%7C%5Ccdot%5Crangle$ 才会等于1, 其他情况为0. 也就是 $P(j_0)%3D%5Cfrac%7B1%7D%7B2%5E%7B2n%7D%7D%5Cleft%7C%5Csum_%7Bk%3D0%7D%5E%7B2%5En-1%7De%5E%7B2%5Cpi%20ik%5Cdelta%7D%5Cright%7C%5E2$ , 其中记 $2%5En%5Cvarphi%3Dj_0%2B2%5En%5Cdelta$ . 如果δ=0, P(j_0)=1, 这说明在没有误差的时候以概率1测出 $2%5En%5Cvarphi$ .

设 $2%5En%5Cvarphi$ 的四舍五入近似值为 $j_1$ , 则有 $%7C%5Cdelta%7C%5Cleq2%5E%7B-(n%2B1)%7D$ , 则 $P(j_1)%3D%5Cfrac%7B1%7D%7B2%5E%7B2n%7D%7D%5Cleft%7C%5Cfrac%7B1-e%5E%7B2%5E%7Bn%2B1%7D%5Cpi%20i%5Cdelta%7D%7D%7B1-e%5E%7B2%5Cpi%20i%5Cdelta%7D%7D%5Cright%7C%5E2$ , 因为 $%5Cleft%7C1-e%5E%7B2ix%7D%5Cright%7C%3D2%7Csin(x)%7C$ , 并且 $%7Csin(x)%7C%5Cleq%7Cx%7C$ , 有 $P(j_1)%5Cgeq%5Cfrac%7B1%7D%7B2%5E2n%7D%5Cleft%7C%5Cfrac%7Bsin(2%5En%5Cpi%5Cdelta)%7D%7B%5Cpi%5Cdelta%7D%5Cright%7C%5E2$ , 又因为 $%7Csin(%5Cpi%20x)%7C%5Cgeq%7C2x%7C%3B%7Cx%7C%5Cleq0.5$ , 得 $P(j_1)%5Cgeq%5Cfrac%7B1%7D%7B2%5E%7B2n%7D%7D%5Cleft%7C%5Cfrac%7B2%5E%7Bn%2B1%7D%5Cdelta%7D%7B%5Cpi%5Cdelta%7D%5Cright%7C%5E2%3D%5Cfrac%7B4%7D%7B%5Cpi%5E2%7D%5Capprox0.40528$ , 当 $%7C%5Cvarphi%7C$ 为 $2%5E%7B-(n%2B1)%7D$ 时取得等号. 上面说明如果精度不够时, 仍会以比较高的概率测得 $2%5En%5Cvarphi$ 的近似值.

如果需要把测得 $2%5En%5Cvarphi$ 最佳近似值的正确率提高至 1-ε, 需要在n个量子位上至多增加 $log(%5Cfrac%7B1%7D%7B%5Cvarepsilon%7D)$ 个量子位.

实例2

下面用一个旋转门为例: $R_x(2%5Csqrt2%5Cpi)$ , 则有两个特征态 $%7Cu%5Crangle%3D%7C%5Cmp%5Crangle$ , 对应两个特征值 $%5Cvarphi%3D%5Cpm%5Cfrac%7B%5Csqrt2%7D%7B2%7D$ , 写为二进制: $%5Cvarphi_%2B%3D0.10110101000001%5Ccdots_%7Bbin%7D$

从Dump的画幅里可以看到, 测量出 $2%5En%5Cvarphi$ 的最佳近似值23的概率为0.619

在n=8时, 将以高达0.99877的概率得出 $%5Cvarphi$ 为0.70703125

叠加特征态

相位估计有一个致命的缺点就是, 需要知道特征态才可以求得特征值. 但是如果只是需要求出多个特征值里的其中一个, 就可以使用多个特征态的叠加态. 在一部分情况下部分特征态的叠加态反而会比单一特征态更容易制备.

以上面实例2的Rx门来说, 两个特征态分别为 $%7C%2B%5Crangle$ 和 $%7C-%5Crangle$ , 则他们的叠加态为 $%7Cu'%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt2%7D(%7C%2B%5Crangle%2B%7C-%5Crangle)%3D%7C0%5Crangle$ , 明显看出他们的叠加态比单独的某一个态更容易制备. 在对叠加特征态执行相位估计电路后, 将会以一半的概率测得 $%5Cvarphi%5Capprox0.5%5Csqrt2$ 或 $%5Cvarphi%5Capprox1-0.5%5Csqrt2$ [忽略误差影响].