我常认为是丑女造就了美人,是愚氓举出了智者,是懦夫衬照了英雄,是众生渡化了佛祖。
# 量子 Fourier 变换及其应用
# 量子 Fourier 变换
量子 Fourier 变换定义为,在一组标准正交基∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ |0\rang,...,|N-1\rang ∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ 上的一个线性算子,在基态上的作用为:
∣ j ⟩ → 1 N ∑ k = 0 N − 1 e 2 π i j k / N ∣ k ⟩ |j\rang\rightarrow\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rang
∣ j ⟩ → N 1 k = 0 ∑ N − 1 e 2 π i j k / N ∣ k ⟩
等价地,对任意状态∑ j = 0 N − 1 x j ∣ j ⟩ \sum_{j=0}^{N-1}x_j|j\rang ∑ j = 0 N − 1 x j ∣ j ⟩ ,Fourier 变换可以等价地写为:
∑ j = 0 N − 1 x j ∣ j ⟩ → ∑ k = 0 N − 1 y k ∣ k ⟩ \sum_{j=0}^{N-1}x_j|j\rang\rightarrow\sum_{k=0}^{N-1}y_k|k\rang
j = 0 ∑ N − 1 x j ∣ j ⟩ → k = 0 ∑ N − 1 y k ∣ k ⟩
其中幅度y k y_k y k 是幅度x j x_j x j 的离散 Fourier 变换值。实际上这个变换是一个酉变换。
下面取N = 2 n N=2^n N = 2 n ,基∣ 0 ⟩ , . . . , ∣ 2 n − 1 ⟩ |0\rang,...,|2^n-1\rang ∣ 0 ⟩ , . . . , ∣ 2 n − 1 ⟩ 是一组计算基。二进制分解状态∣ j ⟩ = ∣ j 1 . . . j n ⟩ |j\rang=|j_1...j_n\rang ∣ j ⟩ = ∣ j 1 . . . j n ⟩ ,用记号 “0. j l j l + 1 . . . j m 0.j_lj_{l+1}...j_m 0 . j l j l + 1 . . . j m ” 表示二进制小数j l + 1 2 − 1 + . . . + j m 2 m − l + 1 j_{l+1}2^{-1}+...+j_m2^{m-l+1} j l + 1 2 − 1 + . . . + j m 2 m − l + 1 。
通过简单的代数运算,可给出量子 Fourier 变换有用的积形式:
∣ j 1 . . . j n ⟩ → ( ∣ 0 ⟩ + e 2 π i 0. j n ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i 0. j n − 1 j n ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i 0. j 1 . . . j n ∣ 1 ⟩ ) 2 n / 2 |j_1...j_n\rang\rightarrow\\
\frac{(|0\rang+e^{2\pi i0.j_n}|1\rang)(|0\rang+e^{2\pi i0.j_{n-1}j_{n}}|1\rang)...(|0\rang+e^{2\pi i0.j_1...j_n}|1\rang)}{2^{n/2}}
∣ j 1 . . . j n ⟩ → 2 n / 2 ( ∣ 0 ⟩ + e 2 π i 0 . j n ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i 0 . j n − 1 j n ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i 0 . j 1 . . . j n ∣ 1 ⟩ )
这个积形式非常有用,甚至 j 可以把它作为 Fourier 变换的定义。这个表示允许我们构造有效计算量子 Fourier 变换的一个量子线路。
积形式与之前定义的等价性可以通过简单的代数运算得到:
∣ j ⟩ → 1 2 n / 2 ∑ k = 0 2 n − 1 e 2 π i j k / 2 n ∣ k ⟩ = 1 2 n / 2 ∑ k 1 = 0 1 . . . ∑ k n = 0 1 e 2 π i j ∑ l = 1 n k l 2 − l ∣ k 1 . . . k n ⟩ = 1 2 n / 2 ∑ k 1 = 0 1 . . . ∑ k n = 0 1 ⊗ l = 1 n e 2 π i j k l 2 − l ∣ k l ⟩ = 1 2 n / 2 ⊗ l = 1 n [ ∑ k l = 0 1 e 2 π i j k l 2 − l ∣ k l ⟩ ] = 1 2 n / 2 ⊗ l = 1 n [ ∣ 0 ⟩ + e 2 π i j 2 − l ∣ 1 ⟩ ] |j\rang\rightarrow\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1}e^{2\pi ijk/2^n}|k\rang\\
=\frac{1}{2^{n/2}}\sum_{k_1=0}^1...\sum_{k_n=0}^1e^{2\pi ij\sum_{l=1}^nk_l2^{-l}}|k_1...k_n\rang\\
=\frac{1}{2^{n/2}}\sum_{k_1=0}^1...\sum_{k_n=0}^1\otimes_{l=1}^ne^{2\pi ijk_l2^{-l}}|k_l\rang\\
=\frac{1}{2^{n/2}}\otimes_{l=1}^n[\sum_{k_l=0}^1e^{2\pi ijk_l2^{-l}}|k_l\rang]\\
=\frac{1}{2^{n/2}}\otimes_{l=1}^n[|0\rang+e^{2\pi ij2^{-l}}|1\rang]
∣ j ⟩ → 2 n / 2 1 k = 0 ∑ 2 n − 1 e 2 π i j k / 2 n ∣ k ⟩ = 2 n / 2 1 k 1 = 0 ∑ 1 . . . k n = 0 ∑ 1 e 2 π i j ∑ l = 1 n k l 2 − l ∣ k 1 . . . k n ⟩ = 2 n / 2 1 k 1 = 0 ∑ 1 . . . k n = 0 ∑ 1 ⊗ l = 1 n e 2 π i j k l 2 − l ∣ k l ⟩ = 2 n / 2 1 ⊗ l = 1 n [ k l = 0 ∑ 1 e 2 π i j k l 2 − l ∣ k l ⟩ ] = 2 n / 2 1 ⊗ l = 1 n [ ∣ 0 ⟩ + e 2 π i j 2 − l ∣ 1 ⟩ ]
其中倒数第二步实际上就是个拆括号,把张量积换成乘法就很好理解。
积形式给出了一个很好的线路。若R k = ( 1 0 0 e 2 π i / 2 k ) R_k=\begin{pmatrix}1&0\\0&e^{2\pi i/2^k}\end{pmatrix} R k = ( 1 0 0 e 2 π i / 2 k ) ,输入状态为∣ j 1 . . . j n ⟩ |j_1...j_n\rang ∣ j 1 . . . j n ⟩ ,则下图线路即实现了 Fourier 变换:
简单解释下,Hadamard 门应用到第一量子比特产生状态:
1 2 1 / 2 ( ∣ 0 ⟩ + e 2 π i 0. j 1 ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩ \frac{1}{2^{1/2}}(|0\rang+e^{2\pi i0.j_1}|1\rang)|j_2...j_n\rang
2 1 / 2 1 ( ∣ 0 ⟩ + e 2 π i 0 . j 1 ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩
应用受控门R 2 R_2 R 2 产生状态:
1 2 1 / 2 ( ∣ 0 ⟩ + e 2 π i 0. j 1 j 2 ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩ \frac{1}{2^{1/2}}(|0\rang+e^{2\pi i0.j_1j_2}|1\rang)|j_2...j_n\rang
2 1 / 2 1 ( ∣ 0 ⟩ + e 2 π i 0 . j 1 j 2 ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩
之所以是受控,因为R 2 R_2 R 2 是一定会对∣ 1 ⟩ |1\rang ∣ 1 ⟩ 产生相移的。当且仅当j 2 = 1 j_2=1 j 2 = 1 再运用R 2 R_2 R 2 实际上就是相移了e 2 π i j 2 / 2 2 e^{2\pi ij_2/2^2} e 2 π i j 2 / 2 2 。以此类推,再应用R 3 , . . . R n R_3,...R_n R 3 , . . . R n 就会产生状态:
1 2 1 / 2 ( ∣ 0 ⟩ + e 2 π i 0. j 1 . . . j n ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩ \frac{1}{2^{1/2}}(|0\rang+e^{2\pi i0.j_1...j_n}|1\rang)|j_2...j_n\rang
2 1 / 2 1 ( ∣ 0 ⟩ + e 2 π i 0 . j 1 . . . j n ∣ 1 ⟩ ) ∣ j 2 . . . j n ⟩
然后运用交换量子比特线路(图中为了简洁没给出):
即可得出最终需要的状态。
这也可以证明 Fourier 变换是酉的,因为线路中每个门都是酉的。
完成一个 n 个量子比特的 Fourier 变换需要的门数为
n + ( n − 1 ) + . . . + 1 = n ( n + 1 ) 2 n+(n-1)+...+1=\frac{n(n+1)}{2}
n + ( n − 1 ) + . . . + 1 = 2 n ( n + 1 )
再加上交换须要的门(n 线性个),故这个线路提供了一个 Fourier 变换的Θ ( n 2 ) \varTheta(n^2) Θ ( n 2 ) 的算法。与之对照,计算2 n 2^n 2 n 个元的离散 Fourier 变换最好的经典算法,例如 FFT,复杂度为Θ ( 2 n l o g ( 2 n ) ) \varTheta(2^nlog(2^n)) Θ ( 2 n l o g ( 2 n ) ) 。这证明了量子计算的优越性。然而,实践中量子计算机的幅度不能通过测量直接访问,因此没办法确定 Fourier 变换后的幅度。更糟糕的是,一般没有制备待变换的原状态的有效办法。因此寻找量子 Fourier 变换的用途比我们希望的更微妙。
首先对于一个函数f:\Z_N\longmapsto \C,满足∑ x = 0 N − 1 ∣ f ( x ) ∣ 2 = N \sum_{x=0}^{N-1}|f(x)|^2=N ∑ x = 0 N − 1 ∣ f ( x ) ∣ 2 = N ,我们都可以用一个状态向量来表示这个函数信息 ,即:∣ f ⟩ = 1 N ( f ( 0 ) f ( 1 ) . . . f ( N − 1 ) ) = 1 N ∑ x = 0 N − 1 f ( x ) ∣ x ⟩ |f\rang=\frac{1}{\sqrt{N}}\begin{pmatrix}f(0)\\f(1)\\...\\f(N-1)\end{pmatrix}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}f(x)|x\rang
∣ f ⟩ = N 1 ⎝ ⎜ ⎜ ⎜ ⎛ f ( 0 ) f ( 1 ) . . . f ( N − 1 ) ⎠ ⎟ ⎟ ⎟ ⎞ = N 1 x = 0 ∑ N − 1 f ( x ) ∣ x ⟩
所以Q F T ∣ f ⟩ = 1 N ∑ x = 0 N − 1 ∑ y = 0 N − 1 e 2 π i x y / N f ( x ) ∣ y ⟩ QFT|f\rang=\frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}e^{2\pi ixy/N}f(x)|y\rang
Q F T ∣ f ⟩ = N 1 x = 0 ∑ N − 1 y = 0 ∑ N − 1 e 2 π i x y / N f ( x ) ∣ y ⟩
而记f ^ ( x ) = ∑ l = 0 N − 1 e 2 π i l x / N f ( l ) \hat{f}(x)=\sum_{l=0}^{N-1}e^{2\pi ilx/N}f(l) f ^ ( x ) = ∑ l = 0 N − 1 e 2 π i l x / N f ( l ) ,则有Q F T ∣ f ⟩ = 1 N ∑ y = 0 N − 1 f ^ ( y ) ∣ y ⟩ = ∣ f ^ ⟩ QFT|f\rang=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}\hat{f}(y)|y\rang=|\hat{f}\rang
Q F T ∣ f ⟩ = N 1 y = 0 ∑ N − 1 f ^ ( y ) ∣ y ⟩ = ∣ f ^ ⟩
这就是默认记号的函数状态下的 Fourier 变换
# 相位估计
Fourier 变换是称为相位估计(phase estimation)的一般过程的关键,而相位估计又是许多量子算法的关键。设酉算子U U U 具有一个特征值为e 2 π i φ e^{2\pi i\varphi} e 2 π i φ 的特征向量∣ u ⟩ |u\rang ∣ u ⟩ ,而φ \varphi φ 的值是未知的。相位估计算法就是要估计φ \varphi φ 。
量子相位估计使用两个寄存器。第一个寄存器包含初态都为∣ 0 ⟩ |0\rang ∣ 0 ⟩ 的 t 个量子比特。如何选择 t 和两件事有关:希望精确估计φ \varphi φ 的精度和相位估计过程希望成功的概率。第二个寄存器初态为∣ u ⟩ |u\rang ∣ u ⟩ ,且包含储存∣ u ⟩ |u\rang ∣ u ⟩ 所需要数目的量子比特。
相位估计分三个阶段。首先,应用下图线路:
简单解释下。首先,图右侧省去了归一化常数1 2 \frac{1}{\sqrt{2}} 2 1 ,并且因为排版问题∣ 0 ⟩ |0\rang ∣ 0 ⟩ 和e 2 π i φ ∣ 1 ⟩ e^{2\pi i\varphi}|1\rang e 2 π i φ ∣ 1 ⟩ 之间应该有加号,U 2 t U^{2^t} U 2 t 表示U U U 的2 t 2^t 2 t 次幂。这个线路输出为什么是图中所示,注意到∣ u ⟩ |u\rang ∣ u ⟩ 是U U U 的属于特征值e 2 π i φ e^{2\pi i\varphi} e 2 π i φ 的一个特征向量。因此U U U 作用于∣ u ⟩ |u\rang ∣ u ⟩ 实际上就是个相移。因此受控相移有等效线路作用到控制量子比特上,故得到该输出结果。
相位估计的第二阶段是应用逆 Fourier 变换到第一寄存器(可在Θ ( t 2 ) \varTheta(t^2) Θ ( t 2 ) 个门内完成)。
相位估计的最后阶段是通过在计算基种测量读出第一寄存器的状态。
相位估计的全过程由下图线路给出:
下面来验证这个线路为什么可以实现相位估计的效果。我们并不关心φ \varphi φ 的整数部分(因为e 2 π i e^{2\pi i} e 2 π i 的整数次幂为 1),不妨假设φ \varphi φ 可以表示为 t 经典比特,即φ = 0. φ 1 . . . φ t \varphi=0.\varphi_1...\varphi_t φ = 0 . φ 1 . . . φ t (φ \varphi φ 当然可以是无穷多位的之后可以证明若φ \varphi φ 是无穷位的这个方法也能给出一个不错的近似),则相位估计第一阶段第一寄存器的结果为(2 t − 1 φ 2^{t-1}\varphi 2 t − 1 φ 的整数部分可以直接扔掉,因为幂次为 1):
1 2 t / 2 ( ∣ 0 ⟩ + e 2 π i 0. φ t ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i 0. φ t − 1 φ ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i 0. φ 1 . . . φ t ∣ 1 ⟩ ) \frac{1}{2^{t/2}}(|0\rang+e^{2\pi i0.\varphi_t}|1\rang)(|0\rang+e^{2\pi i0.\varphi_{t-1}\varphi}|1\rang)...(|0\rang+e^{2\pi i0.\varphi_1...\varphi_t}|1\rang)
2 t / 2 1 ( ∣ 0 ⟩ + e 2 π i 0 . φ t ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i 0 . φ t − 1 φ ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i 0 . φ 1 . . . φ t ∣ 1 ⟩ )
相位估计第二阶段是应用逆 Fourier 变换,通过比较之前的 Fourier 变换积形式,我们发现上式和∣ φ 1 . . . φ t ⟩ |\varphi_1...\varphi_t\rang ∣ φ 1 . . . φ t ⟩ 的 Fourier 变换结果一样。于是逆 Fourier 变换,第一寄存器状态变为∣ φ 1 . . . φ t ⟩ |\varphi_1...\varphi_t\rang ∣ φ 1 . . . φ t ⟩ 。此时再对第一寄存器进行测量,则可以测出( φ 1 . . . φ t ) 2 (\varphi_1...\varphi_t)_2 ( φ 1 . . . φ t ) 2 ,此时因为φ \varphi φ 是精确有限位小数,则可以测出来。
但当φ \varphi φ 是无穷位时怎么办?设b b b 是[ 0 , 2 t ) [0,2^t) [ 0 , 2 t ) 中的一个整数,使得b / 2 t = 0. b 1 . . . b t b/2^t=0.b_1...b_t b / 2 t = 0 . b 1 . . . b t ,且b b b 为小于φ \varphi φ 的所有数中φ \varphi φ 的 t 比特最佳近似,即
0 ≤ φ − b / 2 t ≤ 2 − t 0\leq \varphi-b/2^t\leq 2^{-t} 0 ≤ φ − b / 2 t ≤ 2 − t 。我们要证明相位估计最后的测量大概率(后面说明为什么是大概率)产生了一个接近 b 的结果,从而以很高的概率精确估计了φ \varphi φ 。
第一寄存器输出结果为:
1 2 t / 2 ( ∣ 0 ⟩ + e 2 π i φ 2 t − 1 ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i φ 2 t − 2 ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i φ 2 0 ∣ 1 ⟩ ) = 1 2 t / 2 ∑ k = 0 2 t − 1 e 2 π i φ k ∣ k ⟩ \frac{1}{2^{t/2}}(|0\rang+e^{2\pi i\varphi 2^{t-1}}|1\rang)(|0\rang+e^{2\pi i\varphi 2^{t-2}}|1\rang)...(|0\rang+e^{2\pi i\varphi 2^0}|1\rang)=\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}|k\rang
2 t / 2 1 ( ∣ 0 ⟩ + e 2 π i φ 2 t − 1 ∣ 1 ⟩ ) ( ∣ 0 ⟩ + e 2 π i φ 2 t − 2 ∣ 1 ⟩ ) . . . ( ∣ 0 ⟩ + e 2 π i φ 2 0 ∣ 1 ⟩ ) = 2 t / 2 1 k = 0 ∑ 2 t − 1 e 2 π i φ k ∣ k ⟩
这个结果是一个叠加态,因此计算基测量结果一定是以不同概率得到不同的结果,实际上我们就在证明测量结果大概率离 b 很近。
对这个结果进行逆 Fourier 变换(即对每一个∣ k ⟩ |k\rang ∣ k ⟩ 逆 Fourier 变换),产生状态:
1 2 t ∑ k , l = 0 2 t − 1 e − 2 π i k l 2 t e 2 π i φ k ∣ l ⟩ \frac{1}{2^t}\sum_{k,l=0}^{2^t-1}e^{\frac{-2\pi ikl}{2^t}}e^{2\pi i\varphi k}|l\rang
2 t 1 k , l = 0 ∑ 2 t − 1 e 2 t − 2 π i k l e 2 π i φ k ∣ l ⟩
记a l a_l a l 为∣ l ⟩ |l\rang ∣ l ⟩ 的幅度,则
a l = 1 2 t ∑ k = 0 2 t − 1 ( e 2 π i ( φ − l / 2 t ) ) k a ( b + l ) m o d 2 t = 1 2 t ∑ k = 0 2 t − 1 ( e 2 π i ( φ − ( b + l ) / 2 t ) ) k = 1 2 t ( 1 − e 2 π i ( 2 t φ − ( b + l ) ) 1 − e 2 π i ( φ − ( b + l ) / 2 t ) ) a_l=\frac{1}{2^t}\sum_{k=0}^{2^t-1}(e^{2\pi i(\varphi-l/2^t)})^k\\
a_{(b+l)mod2^t}=\frac{1}{2^t}\sum_{k=0}^{2^t-1}(e^{2\pi i(\varphi-(b+l)/2^t)})^k\\
=\frac{1}{2^t}(\frac{1-e^{2\pi i(2^t\varphi-(b+l))}}{1-e^{2\pi i(\varphi-(b+l)/2^t)}})
a l = 2 t 1 k = 0 ∑ 2 t − 1 ( e 2 π i ( φ − l / 2 t ) ) k a ( b + l ) m o d 2 t = 2 t 1 k = 0 ∑ 2 t − 1 ( e 2 π i ( φ − ( b + l ) / 2 t ) ) k = 2 t 1 ( 1 − e 2 π i ( φ − ( b + l ) / 2 t ) 1 − e 2 π i ( 2 t φ − ( b + l ) ) )
记\delta=\varphi-b/2^t\Rightarrow 0\leq\delta\leq2^
a ( b + l ) m o d 2 t = 1 2 t ( 1 − e 2 π i ( 2 t δ − l ) 1 − e 2 π i ( δ − l / 2 t ) ) a_{(b+l)mod2^t}=\frac{1}{2^t}(\frac{1-e^{2\pi i(2^t\delta-l)}}{1-e^{2\pi i(\delta-l/2^t)}})
a ( b + l ) m o d 2 t = 2 t 1 ( 1 − e 2 π i ( δ − l / 2 t ) 1 − e 2 π i ( 2 t δ − l ) )
这里需要理解清除一个东西。相位估计第三阶段对第一寄存器进行测量时,得到的结果显然不一定(以一定概率)得到 b。记得到的结果是 m,我们证明 m 和 b 偏离很远的概率很小。令s = ( b + l ) m o d 2 t s=(b+l)mod2^t s = ( b + l ) m o d 2 t ,则∣ s − b ∣ > ϵ ⇔ ∣ l ∣ > ϵ |s-b|>\epsilon\Leftrightarrow |l|>\epsilon ∣ s − b ∣ > ϵ ⇔ ∣ l ∣ > ϵ (注意 b 和 l 的范围,可以操作下取模)所以:
p ( ∣ m − b ∣ > ϵ ) = ∑ s ∈ [ 0 , 2 t ) , ∣ s − b ∣ > ϵ ∣ a s ∣ 2 = ∑ l ∈ [ 0 , 2 t ) , ∣ l ∣ > ϵ ∣ a ( l + b ) m o d 2 t ∣ 2 p(|m-b|>\epsilon)=\sum_{s\in[0,2^t),|s-b|>\epsilon}|a_s|^2=\sum_{l\in[0,2^t),|l|>\epsilon}|a_{(l+b)mod2^t}|^2
p ( ∣ m − b ∣ > ϵ ) = s ∈ [ 0 , 2 t ) , ∣ s − b ∣ > ϵ ∑ ∣ a s ∣ 2 = l ∈ [ 0 , 2 t ) , ∣ l ∣ > ϵ ∑ ∣ a ( l + b ) m o d 2 t ∣ 2
因为对任意实数,有∣ 1 − e i θ ∣ ≤ 2 |1-e^{i\theta}|\leq 2 ∣ 1 − e i θ ∣ ≤ 2 ,所以有:
∣ a ( l + b ) m o d 2 t ∣ ≤ 2 2 t ∣ 1 − e 2 π i ( δ − l / 2 t ) ∣ |a_{(l+b)mod2^t}|\leq \frac{2}{2^t|1-e^{2\pi i(\delta - l/2^t)}|}
∣ a ( l + b ) m o d 2 t ∣ ≤ 2 t ∣ 1 − e 2 π i ( δ − l / 2 t ) ∣ 2
而因为0 ≤ δ ≤ 2 − t , 0 ≤ l < 2 t 0\leq\delta\leq 2^{-t},0\leq l<2^t 0 ≤ δ ≤ 2 − t , 0 ≤ l < 2 t ,所以2 π ( δ − l / 2 t ) ∈ [ − π , π ] 2\pi (\delta-l/2^t)\in[-\pi,\pi] 2 π ( δ − l / 2 t ) ∈ [ − π , π ] 。由不等式:∣ 1 − e i θ ∣ ≥ 2 ∣ θ ∣ / π , θ ∈ [ − π , π ] |1-e^{i\theta}|\geq 2|\theta|/\pi,\theta\in[-\pi,\pi] ∣ 1 − e i θ ∣ ≥ 2 ∣ θ ∣ / π , θ ∈ [ − π , π ] :
∣ a ( l + b ) m o d 2 t ∣ ≤ π 2 t 2 π ∣ δ − l / 2 t ∣ = 1 2 ∣ 2 t δ − l ∣ |a_{(l+b)mod2^t}|\leq\frac{\pi}{2^t2\pi|\delta-l/2^t|}=\frac{1}{2|2^t\delta-l|}
∣ a ( l + b ) m o d 2 t ∣ ≤ 2 t 2 π ∣ δ − l / 2 t ∣ π = 2 ∣ 2 t δ − l ∣ 1
因此:
p ( ∣ m − b ∣ > ϵ ) ≤ 1 4 ∑ l = ϵ + 1 2 t − 1 1 ( 2 t δ − l ) 2 p(|m-b|>\epsilon)\leq\frac{1}{4}\sum_{l=\epsilon+1}^{2^t-1}\frac{1}{(2^t\delta-l)^2}
p ( ∣ m − b ∣ > ϵ ) ≤ 4 1 l = ϵ + 1 ∑ 2 t − 1 ( 2 t δ − l ) 2 1
又因为0 ≤ 2 t δ ≤ 1 , l > 1 0\leq2^t\delta\leq 1,l>1 0 ≤ 2 t δ ≤ 1 , l > 1 ,
p ( ∣ m − b ∣ > ϵ ) ≤ 1 4 ∑ l = ϵ + 1 2 t − 1 1 ( l − 1 ) 2 < 1 4 ∫ ϵ − 1 2 t − 1 1 l 2 d l < m i n ( 1 4 ϵ , 1 ) p(|m-b|>\epsilon)\leq\frac{1}{4}\sum_{l=\epsilon+1}^{2^t-1}\frac{1}{(l-1)^2}<\frac{1}{4}\int_{\epsilon-1}^{2^t-1}\frac{1}{l^2}dl<min(\frac{1}{4\epsilon},1)
p ( ∣ m − b ∣ > ϵ ) ≤ 4 1 l = ϵ + 1 ∑ 2 t − 1 ( l − 1 ) 2 1 < 4 1 ∫ ϵ − 1 2 t − 1 l 2 1 d l < m i n ( 4 ϵ 1 , 1 )
事实上这和书上就差了些,不过不影响,而且我觉得书上写的很奇怪。因此
p ( ∣ m − b ∣ < ϵ ) ≥ m a x ( 0 , 1 − 1 4 ( ϵ − 1 ) ) p(|m-b|<\epsilon)\geq max(0,1-\frac{1}{4(\epsilon-1)})
p ( ∣ m − b ∣ < ϵ ) ≥ m a x ( 0 , 1 − 4 ( ϵ − 1 ) 1 )
再重新回去考虑 b 的意义:b 是一个 t 位二进制数,表示φ \varphi φ 小数点后 t 位。如果我们想近似φ \varphi φ 小数点后 n 位 (n<t),则可以令ϵ = 2 t − n \epsilon=2^{t-n} ϵ = 2 t − n (此时 m 和 b 的误差只在后 t-n 位,即 m 的前 n 位和φ \varphi φ 的小数点后前 n 位一样)此时我们得到精确结果的概率高达1 − 1 2 t − n + 2 1-\frac{1}{2^{t-n+2}} 1 − 2 t − n + 2 1 。如果追求概率更高,显然可以把 t 取大一点,即第一寄存器中的量子比特多一点。
跟书上不太一样,书上看不懂。但是结果之间量级一样差一点常数吧。
为了使用相位估算算法,需要制备 U 的本征态∣ u ⟩ |u\rang ∣ u ⟩ 。其实对于任意一个状态∣ ψ ⟩ = ∑ u C u ∣ u ⟩ |\psi\rang=\sum_u C_u|u\rang ∣ ψ ⟩ = ∑ u C u ∣ u ⟩ ,其中∣ u ⟩ |u\rang ∣ u ⟩ 是 U 特征值e 2 π i φ u e^{2\pi i\varphi_u} e 2 π i φ u 对应的特征向量,则算法结果会大概率给出一个近似∑ u C u ∣ φ u ~ ⟩ ∣ u ⟩ \sum_uC_u|\tilde{\varphi_u}\rang|u\rang ∑ u C u ∣ φ u ~ ⟩ ∣ u ⟩ 的状态。其中二进制数φ u ~ \tilde{\varphi_u} φ u ~ 是φ u \varphi_u φ u 的一个很好的近似。
相位估计很好地解决了给出酉算子 U 和其一个特征向量,估计其对于特征值的问题。因为酉算子特征值模为 1 一定是e i θ e^{i\theta} e i θ 形式。
# 相位估计应用
# 求阶
对于满足 x<N,且无公因子的正整数 x 和 N,x 模 N 的阶定义为最小正整数 r,使得x r ≡ 1 ( m o d e N ) x^r\equiv1(modeN) x r ≡ 1 ( m o d e N ) 。记L = l o g ( N ) L=log(N) L = l o g ( N ) (即 N 的二进制位数,表示 N 需要的经典比特数),在经典计算机上找不到一个关于 L 多项式复杂度的算法。然而却有一个有效的量子算法。
求阶的量子算法恰好是把相位估计算法应用到酉算子
U ∣ y ⟩ ≡ ∣ x y m o d N ⟩ U|y\rang\equiv|xy\;mod\;N\rang
U ∣ y ⟩ ≡ ∣ x y m o d N ⟩
其中,y = { 0 , 1 } × { 0 , 1 } × . . . = { 0 , 1 } L y=\{0,1\}\times\{0,1\}\times...=\{0,1\}^L y = { 0 , 1 } × { 0 , 1 } × . . . = { 0 , 1 } L 。考虑状态:
∣ u s ⟩ = 1 r ∑ k = 0 r − 1 e x p ( − 2 π i s k r ) ∣ x k m o d N ⟩ 0 ≤ s ≤ r − 1 |u_s\rang=\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}exp(\frac{-2\pi isk}{r})|x^kmod\;N\rang\\
0\leq s\leq r-1
∣ u s ⟩ = r 1 k = 0 ∑ r − 1 e x p ( r − 2 π i s k ) ∣ x k m o d N ⟩ 0 ≤ s ≤ r − 1
其实这个状态是 U 的本征态,因为 (x r = 1 m o d N x^r=1modN x r = 1 m o d N ):
U ∣ u s ⟩ = 1 r ∑ k = 0 r − 1 e x p ( − 2 π i s k r ) ∣ x k + 1 m o d N ⟩ = e x p ( 2 π i s r ) 1 r ∑ k = 1 r e x p ( − 2 π i s k r ) ∣ x k m o d N ⟩ = e x p ( 2 π i s r ) 1 r ∑ k = 1 r − 1 e x p ( − 2 π i s k r ) ∣ x k m o d N ⟩ + e x p ( 2 π i s r ) 1 r e x p ( − 2 π i s ) ∣ 1 ⟩ = e x p ( 2 π i s r ) 1 r ∑ k = 1 r − 1 e x p ( − 2 π i s k r ) ∣ x k m o d N ⟩ + e x p ( 2 π i s r ) 1 r ∣ 1 ⟩ = e x p ( 2 π i s r ) 1 r ∑ k = 0 r − 1 e x p ( − 2 π i s k r ) ∣ x k m o d N ⟩ = e x p ( 2 π i s r ) ∣ u s ⟩ U|u_s\rang=\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}exp(\frac{-2\pi isk}{r})|x^{k+1}mod\; N\rang\\
=exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}\sum_{k=1}^{r} exp(\frac{-2\pi isk}{r})|x^kmod\; N\rang\\
=exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}\sum_{k=1}^{r-1}exp(\frac{-2\pi isk}{r})|x^kmod\; N\rang+exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}exp(-2\pi is)|1\rang\\
=exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}\sum_{k=1}^{r-1}exp(\frac{-2\pi isk}{r})|x^kmod\; N\rang+exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}|1\rang\\
=exp(\frac{2\pi is}{r})\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}exp(\frac{-2\pi isk}{r})|x^kmod\; N\rang\\
=exp(\frac{2\pi is}{r})|u_s\rang
U ∣ u s ⟩ = r 1 k = 0 ∑ r − 1 e x p ( r − 2 π i s k ) ∣ x k + 1 m o d N ⟩ = e x p ( r 2 π i s ) r 1 k = 1 ∑ r e x p ( r − 2 π i s k ) ∣ x k m o d N ⟩ = e x p ( r 2 π i s ) r 1 k = 1 ∑ r − 1 e x p ( r − 2 π i s k ) ∣ x k m o d N ⟩ + e x p ( r 2 π i s ) r 1 e x p ( − 2 π i s ) ∣ 1 ⟩ = e x p ( r 2 π i s ) r 1 k = 1 ∑ r − 1 e x p ( r − 2 π i s k ) ∣ x k m o d N ⟩ + e x p ( r 2 π i s ) r 1 ∣ 1 ⟩ = e x p ( r 2 π i s ) r 1 k = 0 ∑ r − 1 e x p ( r − 2 π i s k ) ∣ x k m o d N ⟩ = e x p ( r 2 π i s ) ∣ u s ⟩
注意到上面的讨论∣ u s ⟩ ∈ S p a n { ∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ } |u_s\rang\in Span\{|0\rang,...,|N-1\rang\} ∣ u s ⟩ ∈ S p a n { ∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ } 。为了方便,把 U 补全为2 L × 2 L 2^L\times 2^L 2 L × 2 L ,即当N ≤ y ≤ 2 L − 1 N\leq y\leq 2^L-1 N ≤ y ≤ 2 L − 1 时,U ∣ y ⟩ = ∣ y ⟩ U|y\rang=|y\rang U ∣ y ⟩ = ∣ y ⟩ 。即 U 只有作用在子空间S p a n { ∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ } Span\{|0\rang,...,|N-1\rang\} S p a n { ∣ 0 ⟩ , . . . , ∣ N − 1 ⟩ } 上时是不平凡的。
利用相位估计,使我们以高精度得到对应的特征值e ( 2 π i s / r ) e^{(2\pi is/r)} e ( 2 π i s / r ) ,再花一点功夫就可以得到阶 r。
引用相位估计过程由两个重要要求:
必须有对任意整数 k 实现受控U 2 j U^{2^j} U 2 j 操作的有效过程
必须能够有效制备具有不平凡特征值的特征向量∣ u s ⟩ |u_s\rang ∣ u s ⟩ 或至少是这些特征向量的叠加。
第一个要求 可以用称为 ** 求模幂(modular expoentiation)** 的过程来满足,用这个过程我们能够实现整个受控U 2 j U^{2^j} U 2 j 运算的序列,以应用到用O ( L 3 ) O(L^3) O ( L 3 ) 个门的相位估计过程。
求模幂:
我们希望计算变换:
∣ z ⟩ ∣ y ⟩ → ∣ z ⟩ U z t 2 t − 1 . . . U z 1 2 0 ∣ y ⟩ = ∣ z ⟩ ∣ x z y ( m o d N ) ⟩ |z\rang|y\rang\rightarrow|z\rang U^{z_t2^{t-1}}...U^{z_12^0}|y\rang=|z\rang|x^zy(modN)\rang
∣ z ⟩ ∣ y ⟩ → ∣ z ⟩ U z t 2 t − 1 . . . U z 1 2 0 ∣ y ⟩ = ∣ z ⟩ ∣ x z y ( m o d N ) ⟩
所以一系列受控U 2 j U^{2^j} U 2 j 实际上就等价于用一个求模幂乘以第二寄存器的内容,其中 z 是第一寄存器的内容。
此时我们的想法是先引入第三计算器计算∣ x z m o d N ⟩ |x^zmodN\rang ∣ x z m o d N ⟩ (因为去除 y 之后方便使用快速幂),再把他乘进第二寄存器,再用退计算(uncomputation)把第三寄存器抹除。
首先引入第三寄存器初始状态∣ x ⟩ ∣ 1 ⟩ |x\rang|1\rang ∣ x ⟩ ∣ 1 ⟩ ,考虑下怎么处理状态相乘,即实现∣ a ⟩ ∣ b ⟩ → ∣ a ⟩ ∣ a ⋅ b ⟩ |a\rang|b\rang\rightarrow|a\rang|a\cdot b\rang ∣ a ⟩ ∣ b ⟩ → ∣ a ⟩ ∣ a ⋅ b ⟩ 。实际上可以使用小学时期就学过的按位乘法(只不过是按二进制位乘法)就可以很好的解决这个问题,复杂度就是O ( l o g ( a ) l o g ( b ) ) O(log(a)log(b)) O ( l o g ( a ) l o g ( b ) ) 在这题中就是O ( l o g 2 ( x ) ) O(log^2(x)) O ( l o g 2 ( x ) ) 。
具体实现也需要考虑下第三寄存器里乘法的实现,应该需要引入一些辅助量子比特,但应该是O ( l o g ( x ) ) O(log(x)) O ( l o g ( x ) ) 级别的,同样最后需要的门数是O ( l o g 3 ( x ) ) O(log^3(x)) O ( l o g 3 ( x ) ) 的(每次乘法是平方,做 t 次)。
然后把第三寄存器得出的x z m o d N x^zmodN x z m o d N 乘到第二寄存器,再用退计算 (uncomputation) 的技巧抹除第三寄存器内容。
但实际实现过程还需要很多细节的考虑。总之显然这通过引入不多的量子比特和计算门就是可以实现的(O ( l o g 3 ( x ) ) O(log^3(x)) O ( l o g 3 ( x ) ) )。
实践中,练习给出了我认为更好的一个做法。把第二寄存器初始化为∣ 0 ⟩ |0\rang ∣ 0 ⟩ ,然后把U j : U j ∣ x ⟩ = ∣ x j m o d N ⟩ U^j:U^j|x\rang=|x^jmodN\rang U j : U j ∣ x ⟩ = ∣ x j m o d N ⟩ 替换为算子 V:
V : V ∣ j ⟩ ∣ k ⟩ = ∣ j ⟩ ∣ k + x j m o d N ⟩ V:V|j\rang|k\rang=|j\rang|k+x^jmodN\rang
V : V ∣ j ⟩ ∣ k ⟩ = ∣ j ⟩ ∣ k + x j m o d N ⟩
这样操作得出的输出结果是一样的,复杂度也没变,V 也很好构造出来。但是感觉实现起来少了些细节吧不知道(x。
第二个要求 需要一定技巧,因为在制备∣ u s ⟩ |u_s\rang ∣ u s ⟩ 时我们根本不知道 r,所以不能直接制备。其实:
1 r ∑ s = 0 r − 1 ∣ u s ⟩ = ∣ 0...01 ⟩ \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rang=|0...01\rang
r 1 s = 0 ∑ r − 1 ∣ u s ⟩ = ∣ 0 . . . 0 1 ⟩
所以如果第二寄存器的输入为∣ 0...01 ⟩ |0...01\rang ∣ 0 . . . 0 1 ⟩ 的话,第一寄存器的操作为:
1 2 t / 2 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] ∣ 1 ⟩ = 1 2 t / 2 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] ∑ s = 0 r − 1 1 r ∣ u s ⟩ = ∑ s = 0 r − 1 1 r 1 2 t / 2 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] ∣ u s ⟩ → ∑ s = 0 r − 1 1 r 1 2 t / 2 [ ∣ 0 ⟩ + e 2 π i 2 t − 1 s / r ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + e 2 π i 2 0 s / r ∣ 1 ⟩ ] ∣ u s ⟩ → ∑ s = 0 r − 1 1 r F T ⊺ { 1 2 t / 2 [ ∣ 0 ⟩ + e 2 π i 2 t − 1 s / r ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + e 2 π i 2 0 s / r ∣ 1 ⟩ ] } ∣ u s ⟩ ( 记 s / r = φ s = 0. φ s 1 . . . φ s t ) = ∑ s = 0 r − 1 1 r ∣ φ s 1 . . . φ s t ⟩ ∣ u s ⟩ \frac{1}{2^{t/2}}[|0\rang+|1\rang]...[|0\rang+|1\rang]|1\rang=\frac{1}{2^{t/2}}[|0\rang+|1\rang]...[|0\rang+|1\rang]\sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}|u_s\rang\\
=\sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}\frac{1}{2^{t/2}}[|0\rang+|1\rang]...[|0\rang+|1\rang]|u_s\rang\\
\rightarrow \sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}\frac{1}{2^{t/2}}[|0\rang+e^{2\pi i2^{t-1}s/r}|1\rang]...[|0\rang+e^{2\pi i2^0 s/r}|1\rang]|u_s\rang\\
\rightarrow \sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}FT^\intercal\{\frac{1}{2^{t/2}}[|0\rang+e^{2\pi i2^{t-1}s/r}|1\rang]...[|0\rang+e^{2\pi i2^0 s/r}|1\rang]\}|u_s\rang\\
(记s/r=\varphi_s=0.\varphi_{s1}...\varphi_{st})\\
=\sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}|\varphi_{s1}...\varphi_{st}\rang|u_s\rang
2 t / 2 1 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] ∣ 1 ⟩ = 2 t / 2 1 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] s = 0 ∑ r − 1 r 1 ∣ u s ⟩ = s = 0 ∑ r − 1 r 1 2 t / 2 1 [ ∣ 0 ⟩ + ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + ∣ 1 ⟩ ] ∣ u s ⟩ → s = 0 ∑ r − 1 r 1 2 t / 2 1 [ ∣ 0 ⟩ + e 2 π i 2 t − 1 s / r ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + e 2 π i 2 0 s / r ∣ 1 ⟩ ] ∣ u s ⟩ → s = 0 ∑ r − 1 r 1 F T ⊺ { 2 t / 2 1 [ ∣ 0 ⟩ + e 2 π i 2 t − 1 s / r ∣ 1 ⟩ ] . . . [ ∣ 0 ⟩ + e 2 π i 2 0 s / r ∣ 1 ⟩ ] } ∣ u s ⟩ ( 记 s / r = φ s = 0 . φ s 1 . . . φ s t ) = s = 0 ∑ r − 1 r 1 ∣ φ s 1 . . . φ s t ⟩ ∣ u s ⟩
此时对第二寄存器基于基∣ u 0 ⟩ , . . . ∣ u r − 1 ⟩ |u_0\rang,...|u_{r-1}\rang ∣ u 0 ⟩ , . . . ∣ u r − 1 ⟩ 的投影测量,每个结果s 0 ∈ [ 0 , r − 1 ] s_0\in[0,r-1] s 0 ∈ [ 0 , r − 1 ] 均以概率1 / r 1/r 1 / r 得到,得到后第一寄存器状态即会坍塌进入∣ φ s 0 1 . . . φ s 0 t ⟩ |\varphi_{s_01}...\varphi_{s_0t}\rang ∣ φ s 0 1 . . . φ s 0 t ⟩ ,因此无论测出结果是几,都可以估计出s 0 / r s_0/r s 0 / r 的值。
到这里仍未结束,因为我们需要解决知道有理数φ ≈ s / r \varphi\approx s/r φ ≈ s / r (近似到O ( L ) O(L) O ( L ) 位),和 s,怎么得到 r?此时需要连分式算法 :
连分式算法的思想是只用整数把实数描述为如下形式:
[ a 0 , . . . , a M ] = a 0 + 1 a 1 + 1 a 2 + 1 . . . + 1 a M [a_0,...,a_M]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{...+\frac{1}{a_M}}}}
[ a 0 , . . . , a M ] = a 0 + a 1 + a 2 + . . . + a M 1 1 1 1
其中[ a 0 , . . . , a m ] [a_0,...,a_m] [ a 0 , . . . , a m ] 称为第 m 个渐进值。若φ \varphi φ 是无理数则M = ∞ M=\infin M = ∞ 。
这个算法很简单,以31 13 \frac{31}{13} 1 3 3 1 为例,实际上就是拆开整数和真分数,把真分数倒过来,再重复。
31 13 = 2 + 5 13 = 2 + 1 13 5 = 2 + 1 2 + 3 5 = . . . = 2 + 1 2 + 1 1 + 1 1 + 1 / 2 \frac{31}{13}=2+\frac{5}{13}=2+\frac{1}{\frac{13}{5}}=2+\frac{1}{2+\frac{3}{5}}=...=2+\frac{1}{2+\frac{1}{1+\frac{1}{1+1/2}}}
1 3 3 1 = 2 + 1 3 5 = 2 + 5 1 3 1 = 2 + 2 + 5 3 1 = . . . = 2 + 2 + 1 + 1 + 1 / 2 1 1 1
复杂度的话实际上这个算法需要O ( L ) O(L) O ( L ) 的翻转和拆开,每个翻转和拆开又需要O ( L 2 ) O(L^2) O ( L 2 ) 个基本算术门,所以纵谷需要O ( L 3 ) O(L^3) O ( L 3 ) 个门即可实现。
定理:设有理数s / r s/r s / r 是任一个使得∣ s r − φ ∣ ≤ 1 2 r 2 |\frac{s}{r}-\varphi|\leq\frac{1}{2r^2} ∣ r s − φ ∣ ≤ 2 r 2 1 的有理数,则s / r s/r s / r 是φ \varphi φ 连分式的一个渐进值。
通过此定理可以通过用连分式算法拆解φ \varphi φ 的渐进值,且每拆分一次都可以考虑下拆分出来的渐进分数的分母带入到x r = 1 ( m o d N ) x^r=1(modN) x r = 1 ( m o d N ) 验证,若等式成立了则求阶任务就完成了。
实际上给出分母r r r 的上界L L L ,然后把φ \varphi φ 近似到2 L + 1 2L+1 2 L + 1 位,则真实值s / r s/r s / r 与φ \varphi φ 的误差∣ s / r − φ ∣ ≤ 2 − 2 L − 1 ≤ 1 / 2 r 2 |s/r-\varphi|\leq2^{-2L-1}\leq1/2r^2 ∣ s / r − φ ∣ ≤ 2 − 2 L − 1 ≤ 1 / 2 r 2 ,所以真实值肯定为渐进值的一个近似值,即一定可以得出结果。分子分母都能的出来。
然而求阶算法还可能面临失败。首先,相位估计的结果可能给出s / r s/r s / r 的一个很糟糕的估计,不过这也的概率不大,也可以通过增加线路规模来减小。其次,s 和 r 可能有公因子(但连分式分解出来的 r‘一定和 s 互质)。这时连分式算法返回的r ′ r' r ′ 会是r r r 的一个因子,而非 r 本身。这个问题有三种解决办法:
注意到测量得到s 0 ∈ [ 0 , r − 1 ] s_0\in[0,r-1] s 0 ∈ [ 0 , r − 1 ] 时概率是均等的。而小于 r 的素数至少为r / 2 l o g r r/2logr r / 2 l o g r 个,因此s 0 s_0 s 0 为质数的概率是1 / 2 l o g r 1/2logr 1 / 2 l o g r 。故重复相位估计算法2 l o g ( N ) 2log(N) 2 l o g ( N ) 次,将会以很高的概率得到相位φ ≈ s / r \varphi\approx s/r φ ≈ s / r 使得s / r s/r s / r 互质。
直接说比较好的方法。重复相位估计两次,分别得到s 1 , s 2 s_1,s_2 s 1 , s 2 ,然后连分式得到的对应 r 为r 1 , r 2 r_1,r_2 r 1 , r 2 。我们取 r 为r 1 , r 2 r_1,r_2 r 1 , r 2 的最小公倍数。此时正确的概率很高,因为s 1 , s 2 s_1,s_2 s 1 , s 2 没有公因子的概率为1 − ∑ q p ( q ∣ s 1 ) p ( q ∣ s 2 ) 1-\sum_qp(q|s_1)p(q|s_2) 1 − ∑ q p ( q ∣ s 1 ) p ( q ∣ s 2 ) ,其中竖线为可以整除的意思。然后由于 s 是从 0,…,r-1 中均匀随机选一个,所以p ( q ∣ s 1 ) ≤ 1 / q p(q|s_1)\leq1/q p ( q ∣ s 1 ) ≤ 1 / q 。所以s 1 , s 2 s_1,s_2 s 1 , s 2 没有公因子的概率≥ 1 − ∑ q 1 / q 2 \geq 1-\sum_q1/q^2 ≥ 1 − ∑ q 1 / q 2 。通过数论知识可以得到这个概率≥ 1 4 \geq\frac{1}{4} ≥ 4 1 ,即 r 正确的概率至少为1 4 \frac{1}{4} 4 1 。(这很高吗?。。。
事实上求阶问题量子算法规模在O ( l o g 3 ( N ) ) O(log^3(N)) O ( l o g 3 ( N ) ) 。
# 量子 Fourier 变换的一般应用
# 离散对数问题
给定 a 和b = a s b=a^s b = a s ,s 是多少?
# 问题的转化
实际上我们可以考虑一个函数f ( x 1 , x 2 ) = a b m o d N = a s x 1 + x 2 m o d N f(x_1,x_2)=abmodN=a^{sx_1+x_2}modN f ( x 1 , x 2 ) = a b m o d N = a s x 1 + x 2 m o d N ,这个函数很好构造而且是周期的,因为f ( x 1 + l , x 2 − l s ) = f ( x 1 , x 2 ) f(x_1+l,x_2-ls)=f(x_1,x_2) f ( x 1 + l , x 2 − l s ) = f ( x 1 , x 2 ) ,而周期是二元的( l , − l s ) (l,-ls) ( l , − l s ) 。实际上我们就想求这个 s。而 r 为满足a r = 1 ( m o d N ) a^r=1(modN) a r = 1 ( m o d N ) 的最小正整数,显然 f 也有一维周期:f ( x 1 + r , x 2 ) = f ( x 1 , x 2 ) = f ( x 1 , x 2 + r ) f(x_1+r,x_2)=f(x_1,x_2)=f(x_1,x_2+r) f ( x 1 + r , x 2 ) = f ( x 1 , x 2 ) = f ( x 1 , x 2 + r ) ,这个一维周期保证了下面的约等号成立 。
然后可以类似之前求周期的经验:
∣ 0 ⟩ ∣ 0 ⟩ ∣ 0 ⟩ → 1 2 t ∑ x 1 = 0 2 t − 1 ∑ x 2 = 0 2 t − 1 ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ 0 ⟩ → 1 2 t ∑ x 1 = 0 2 t − 1 ∑ x 2 = 0 2 t − 1 ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ( x 1 , x 2 ) ⟩ |0\rang|0\rang|0\rang\rightarrow\frac{1}{2^t}\sum_{x_1=0}^{2^t-1}\sum_{x_2=0}^{2^t-1}|x_1\rang|x_2\rang|0\rang\rightarrow\frac{1}{2^t}\sum_{x_1=0}^{2^t-1}\sum_{x_2=0}^{2^t-1}|x_1\rang|x_2\rang|f(x_1,x_2)\rang\\
∣ 0 ⟩ ∣ 0 ⟩ ∣ 0 ⟩ → 2 t 1 x 1 = 0 ∑ 2 t − 1 x 2 = 0 ∑ 2 t − 1 ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ 0 ⟩ → 2 t 1 x 1 = 0 ∑ 2 t − 1 x 2 = 0 ∑ 2 t − 1 ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ( x 1 , x 2 ) ⟩
然后引入状态:
∣ f ^ ( l 1 , l 2 ) ⟩ = 1 2 t ∑ x 1 = 0 2 t − 1 ∑ x 2 = 0 2 t − 1 e − 2 π i ( l 1 x 1 + l 2 x 2 ) / 2 t ∣ f ( x 1 , x 2 ) ⟩ |\hat{f}(l_1,l_2)\rang=\frac{1}{2^t}\sum_{x_1=0}^{2^t-1}\sum_{x_2=0}^{2^t-1}e^{-2\pi i(l_1x_1+l_2x_2)/2^t}|f(x_1,x_2)\rang
∣ f ^ ( l 1 , l 2 ) ⟩ = 2 t 1 x 1 = 0 ∑ 2 t − 1 x 2 = 0 ∑ 2 t − 1 e − 2 π i ( l 1 x 1 + l 2 x 2 ) / 2 t ∣ f ( x 1 , x 2 ) ⟩
则
∣ f ( x 1 , x 2 ) ⟩ = 1 2 t ∑ l 1 = 0 2 t − 1 ∑ l 2 = 0 2 t − 1 e 2 π i ( l 1 x 1 + l 2 x 2 ) / 2 t ∣ f ^ ( l 1 , l 2 ) ⟩ ≈ 1 r ∑ l 1 = 0 r − 1 ∑ l 2 = 0 r − 1 e 2 π i ( l 1 x 1 + l 2 x 2 ) / r ∣ f ^ ( l 1 , l 2 ) ⟩ = 1 r ∑ l 2 = 0 r − 1 e 2 π i ( s l 2 x 1 + l 2 x 2 ) / r ∣ f ^ ( s l 2 , l 2 ) ⟩ |f(x_1,x_2)\rang=\frac{1}{2^t}\sum_{l_1=0}^{2^t-1}\sum_{l_2=0}^{2^t-1}e^{2\pi i(l_1x_1+l_2x_2)/2^t}|\hat{f}(l_1,l_2)\rang\approx\\
\frac{1}{r}\sum_{l_1=0}^{r-1}\sum_{l_2=0}^{r-1}e^{2\pi i(l_1x_1+l_2x_2)/r}|\hat{f}(l_1,l_2)\rang=\frac{1}{\sqrt{r}}\sum_{l_2=0}^{r-1}e^{2\pi i(sl_2x_1+l_2x_2)/r}|\hat{f}(sl_2,l_2)\rang
∣ f ( x 1 , x 2 ) ⟩ = 2 t 1 l 1 = 0 ∑ 2 t − 1 l 2 = 0 ∑ 2 t − 1 e 2 π i ( l 1 x 1 + l 2 x 2 ) / 2 t ∣ f ^ ( l 1 , l 2 ) ⟩ ≈ r 1 l 1 = 0 ∑ r − 1 l 2 = 0 ∑ r − 1 e 2 π i ( l 1 x 1 + l 2 x 2 ) / r ∣ f ^ ( l 1 , l 2 ) ⟩ = r 1 l 2 = 0 ∑ r − 1 e 2 π i ( s l 2 x 1 + l 2 x 2 ) / r ∣ f ^ ( s l 2 , l 2 ) ⟩
实际上,最后一个等式需要借用f ^ \hat{f} f ^ 的周期性,以及l 1 , l 2 < r l_1,l_2<r l 1 , l 2 < r ,用一点数学证明(Ex5.22),不过这有一点点复杂。
然后系统状态为:
= 1 2 t r ∑ x 1 = 0 2 t − 1 ∑ x 2 = 0 2 t − 1 ∑ l 2 = 0 r − 1 e 2 π i l 2 ( s x 1 + x 2 ) / r ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ =\frac{1}{2^t\sqrt{r}}\sum_{x_1=0}^{2^t-1}\sum_{x_2=0}^{2^t-1}\sum_{l_2=0}^{r-1}e^{2\pi il_2(sx_1+x_2)/r}|x_1\rang|x_2\rang |\hat{f}(sl_2,l_2)\rang
= 2 t r 1 x 1 = 0 ∑ 2 t − 1 x 2 = 0 ∑ 2 t − 1 l 2 = 0 ∑ r − 1 e 2 π i l 2 ( s x 1 + x 2 ) / r ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩
然后直接对前两个寄存器应用逆 Fourier 变换:
Q F T ⊺ : 1 2 t r ∑ x 1 = 0 2 t − 1 ∑ x 2 = 0 2 t − 1 ∑ l 2 = 0 r − 1 e 2 π i l 2 ( s x 1 + x 2 ) / r ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ → 1 r 2 2 t ∑ l 2 = 0 r − 1 ∑ x 1 , y 1 = 0 2 t − 1 e x p ( 2 π i x 1 2 t [ 2 t s l 2 r − y 1 ] ) ∑ x 2 , y 2 = 0 2 t − 1 e x p ( 2 π i x 2 2 t [ 2 t l 2 r − y 2 ] ) ∣ y 1 ⟩ ∣ y 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ = 1 r ∑ l 2 = 0 r − 1 ∑ y 1 , y 2 = 0 2 t − 1 δ 2 t s l 2 r − y 1 , 0 δ 2 t l 2 r − y 2 , 0 ∣ y 1 ⟩ ∣ y 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ = 1 r ∑ l 2 = 0 r − 1 ∣ 2 t s l 2 r ⟩ ∣ 2 t l 2 r ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ QFT^\intercal:\frac{1}{2^t\sqrt{r}}\sum_{x_1=0}^{2^t-1}\sum_{x_2=0}^{2^t-1}\sum_{l_2=0}^{r-1}e^{2\pi il_2(sx_1+x_2)/r}|x_1\rang|x_2\rang |\hat{f}(sl_2,l_2)\rang\\
\rightarrow\frac{1}{\sqrt{r}2^{2t}}\sum_{l_2=0}^{r-1}\sum_{x_1,y_1=0}^{2^t-1}exp(\frac{2\pi ix_1}{2^t}[\frac{2^tsl_2}{r}-y_1])\sum_{x_2,y_2=0}^{2^t-1}exp(\frac{2\pi ix_2}{2^t}[\frac{2^tl_2}{r}-y_2])|y_1\rang|y_2\rang|\hat{f}(sl_2,l_2)\rang\\
=\frac{1}{\sqrt{r}}\sum_{l_2=0}^{r-1}\sum_{y_1,y_2=0}^{2^t-1}\delta_{\frac{2^t sl_2}{r}-y_1,0}\delta_{\frac{2^tl_2}{r}-y_2,0}|y_1\rang|y_2\rang|\hat{f}(sl_2,l_2)\rang\\
=\frac{1}{\sqrt{r}}\sum_{l_2=0}^{r-1}|\frac{2^tsl_2}{r}\rang|\frac{2^tl_2}{r}\rang|\hat{f}(sl_2,l_2)\rang
Q F T ⊺ : 2 t r 1 x 1 = 0 ∑ 2 t − 1 x 2 = 0 ∑ 2 t − 1 l 2 = 0 ∑ r − 1 e 2 π i l 2 ( s x 1 + x 2 ) / r ∣ x 1 ⟩ ∣ x 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ → r 2 2 t 1 l 2 = 0 ∑ r − 1 x 1 , y 1 = 0 ∑ 2 t − 1 e x p ( 2 t 2 π i x 1 [ r 2 t s l 2 − y 1 ] ) x 2 , y 2 = 0 ∑ 2 t − 1 e x p ( 2 t 2 π i x 2 [ r 2 t l 2 − y 2 ] ) ∣ y 1 ⟩ ∣ y 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ = r 1 l 2 = 0 ∑ r − 1 y 1 , y 2 = 0 ∑ 2 t − 1 δ r 2 t s l 2 − y 1 , 0 δ r 2 t l 2 − y 2 , 0 ∣ y 1 ⟩ ∣ y 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩ = r 1 l 2 = 0 ∑ r − 1 ∣ r 2 t s l 2 ⟩ ∣ r 2 t l 2 ⟩ ∣ f ^ ( s l 2 , l 2 ) ⟩
然后对前两个寄存器测量,得出s l 20 r , l 20 r \frac{sl_{20}}{r},\frac{l_{20}}{r} r s l 2 0 , r l 2 0 。
然后应用一个推广连分式算法,可以分别同时对他们做连分式,当同时得到 r 时,将两个连分式的渐进值相除,即可得出 s。
# Simon’s Algorithm
给定一个函数f : { 0 , 1 } n ⟼ { 0 , 1 } m , m ≥ n f:\{0,1\}^n\longmapsto \{0,1\}^m,m\geq n f : { 0 , 1 } n ⟼ { 0 , 1 } m , m ≥ n ,满足f ( x ) = f ( y ) ⇔ y = x ⊕ s f(x)=f(y)\Leftrightarrow y=x\oplus s f ( x ) = f ( y ) ⇔ y = x ⊕ s ,其中⊕ \oplus ⊕ 为异或符号。现给出一个可以实现 f 的黑箱,求 s 的值。
首先制备一个两寄存器初态∣ 0 ⟩ ∣ 0 ⟩ |0\rang|0\rang ∣ 0 ⟩ ∣ 0 ⟩ ,第一寄存器 n 量子比特,第二寄存器 m 量子比特。
利用H ⊗ n H^{\otimes n} H ⊗ n 制造叠加态→ 1 2 n / 2 ∑ x ∈ { 0 , 1 } n ∣ x ⟩ ∣ 0 ⟩ \rightarrow \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n}|x\rang|0\rang → 2 n / 2 1 ∑ x ∈ { 0 , 1 } n ∣ x ⟩ ∣ 0 ⟩
应用 f 的黑箱→ 1 2 n / 2 ∑ x ∈ { 0 , 1 } n ∣ x ⟩ ∣ f ( x ) ⟩ \rightarrow \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n}|x\rang|f(x)\rang → 2 n / 2 1 ∑ x ∈ { 0 , 1 } n ∣ x ⟩ ∣ f ( x ) ⟩
对第二寄存器进行测量,得到结果f ( x 0 ) f(x_0) f ( x 0 ) 。而对应f ( x 0 ) f(x_0) f ( x 0 ) 的x x x 至多有两个,因此系统状态坍塌进入:
→ ( 1 2 ∣ x 0 ⟩ + 1 2 ∣ x 0 ⊕ s ⟩ ) ∣ f ( x 0 ) ⟩ \rightarrow(\frac{1}{\sqrt{2}}|x_0\rang+\frac{1}{\sqrt{2}}|x_0\oplus s\rang)|f(x_0)\rang
→ ( 2 1 ∣ x 0 ⟩ + 2 1 ∣ x 0 ⊕ s ⟩ ) ∣ f ( x 0 ) ⟩
此时扔掉第二寄存器,对第一寄存器继续应用算子H ⊗ n = 1 2 n ∑ x , y ∈ { 0 , 1 } n ( − 1 ) x ⋅ y ∣ x ⟩ ⟨ y ∣ H^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum_{x,y\in\{0,1\}^n}(-1)^{x\cdot y}|x\rang\lang y| H ⊗ n = 2 n 1 ∑ x , y ∈ { 0 , 1 } n ( − 1 ) x ⋅ y ∣ x ⟩ ⟨ y ∣ :
→ 1 2 n + 1 ∑ x ∈ { 0 , 1 } n ( ( − 1 ) x 0 ⋅ x ∣ x ⟩ + ( − 1 ) ( x 0 ⊕ s ) ⋅ x ∣ x ⟩ ) \rightarrow\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}((-1)^{x_0\cdot x}|x\rang+(-1)^{(x_0\oplus s)\cdot x}|x\rang)
→ 2 n + 1 1 x ∈ { 0 , 1 } n ∑ ( ( − 1 ) x 0 ⋅ x ∣ x ⟩ + ( − 1 ) ( x 0 ⊕ s ) ⋅ x ∣ x ⟩ )
而( − 1 ) ( a ⊕ b ) ⋅ c = ( − 1 ) a ⋅ c × ( − 1 ) b ⋅ c (-1)^{(a\oplus b)\cdot c}=(-1)^{a\cdot c}\times (-1)^{b\cdot c} ( − 1 ) ( a ⊕ b ) ⋅ c = ( − 1 ) a ⋅ c × ( − 1 ) b ⋅ c 因为我们按位考虑,两数点乘实际上就是两数对应位都为 1 的位数,
然后所以只用考虑 c 为 1 的位。然后 a 和 b 对应位都为 0 的话,相当于点乘结果没变;a 和 b 对应位都为 1 的话,相当于点乘结果 + 2,然后反应在 (-1) 的指数上相当于也没变。只有 a 和 b 对应位不同,相当于点乘结果 + 1,算式结果要乘上 (-1)。因此不难验证式子成立
= 1 2 n + 1 ∑ x ∈ { 0 , 1 } n ( − 1 ) x 0 ⋅ x ( 1 + ( − 1 ) s ⋅ x ) ∣ x ⟩ =\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}(-1)^{x_0\cdot x}(1+(-1)^{ s\cdot x})|x\rang
= 2 n + 1 1 x ∈ { 0 , 1 } n ∑ ( − 1 ) x 0 ⋅ x ( 1 + ( − 1 ) s ⋅ x ) ∣ x ⟩
然后我们对第一寄存器测量,显然如果有结果(例如x = a x=a x = a )的时候一定满足s ⋅ a = 0 ( m o d 2 ) s\cdot a=0(mod2) s ⋅ a = 0 ( m o d 2 ) ,这实际上就揭示了 s 的一些信息。
我们一直重复整个过程 n-1 次。然后就会得到 n-1 个线性方程:
s ⋅ a 1 = 0 ( m o d 2 ) s ⋅ a 2 = 0 ( m o d 2 ) . . . . s ⋅ a n − 1 = 0 ( m o d 2 ) s\cdot a_1=0(mod2)\\
s\cdot a_2=0(mod2)\\
....\\
s\cdot a_{n-1}=0(mod2)
s ⋅ a 1 = 0 ( m o d 2 ) s ⋅ a 2 = 0 ( m o d 2 ) . . . . s ⋅ a n − 1 = 0 ( m o d 2 )
当a 1 , a 2 , . . . , a n − 1 a_1,a_2,...,a_{n-1} a 1 , a 2 , . . . , a n − 1 线性无关(相对于异或)时,因为上面数字的特殊性(只有 0 和 1 两种情况),可以解出两组解,而且一组解一定为 0 解(可以构造这样一组方程组解试试就明白了),而另一组非平凡解就是我们要的结果。
但是我们究竟有多大概率重复 n-1 次就获得 n-1 个线性无关的方程?
得到如下结果就失败了
失败的概率
成功的概率
a 1 a_1 a 1
0
1 2 n − 1 \frac{1}{2^{n-1}} 2 n − 1 1
1 − 1 2 n − 1 1-\frac{1}{2^{n-1}} 1 − 2 n − 1 1
a 2 a_2 a 2
0 , a 1 0,a_1 0 , a 1
2 2 n − 1 \frac{2}{2^{n-1}} 2 n − 1 2
1 − 2 2 n − 1 1-\frac{2}{2^{n-1}} 1 − 2 n − 1 2
…
…
…
…
a_
0 , a 1 , . . . , a n − 2 , a 1 ⊕ a 2 , . . . 0,a_1,...,a_{n-2},a_1\oplus a_2,... 0 , a 1 , . . . , a n − 2 , a 1 ⊕ a 2 , . . .
2 n − 2 2 n − 1 \frac{2^{n-2}}{2^{n-1}} 2 n − 1 2 n − 2
1 − 2 n − 2 2 n − 1 1-\frac{2^{n-2}}{2^{n-1}} 1 − 2 n − 1 2 n − 2
因此,最后成功的概率是最右面一列乘起来,当 n 趋近于无穷时,成功概率下界为\approx 0.288>\frac{1}
所以重复 n-1 次至少有 1/4 的概率就能得出 s。
事实上,Z 2 \Z_2 Z 2 上的 Quantum Fourier Transform 就是H ⊗ n H^{\otimes n} H ⊗ n
# Period-finding(Simon’s algorithm over Z N \Z_N Z N )
给定一个量子酉门Q F Q_F Q F ,它可以实现函数F : Z N ⟼ { 0 , 1 } m , N = 2 n , m ≥ n F:\Z_N\longmapsto \{0,1\}^m,N=2^n,m\geq n F : Z N ⟼ { 0 , 1 } m , N = 2 n , m ≥ n (实际上Z N = { 0 , 1 } n \Z_N=\{0,1\}^n Z N = { 0 , 1 } n ),然后已知这个函数满足F ( x ) = F ( y ) ⇔ F ( x + L ) = F ( y ) F(x)=F(y)\Leftrightarrow F(x+L)=F(y) F ( x ) = F ( y ) ⇔ F ( x + L ) = F ( y ) ,实际上因为这里的+ + + 是+ ( m o d N ) +(modN) + ( m o d N ) ,所以只有L ∣ N L|N L ∣ N 时这个条件才有可能被满足。求L L L 。
# 需知的定理
Fourier 变换更一般的定义为:
∑ h ∈ H a h ∣ h ⟩ → ∑ g ∈ G a g ~ ∣ g ⟩ , w h e r e a g ~ = ∑ h ∈ H a h e x p ( 2 π i g h / ∣ G ∣ ) \sum_{h\in H}a_h|h\rang\rightarrow\sum_{g\in G}\tilde{a_g}|g\rang,where\quad \tilde{a_g}=\sum_{h\in H}a_h exp(2\pi igh/|G|)
h ∈ H ∑ a h ∣ h ⟩ → g ∈ G ∑ a g ~ ∣ g ⟩ , w h e r e a g ~ = h ∈ H ∑ a h e x p ( 2 π i g h / ∣ G ∣ )
H 是 G 的某个子集,G 是 Hilbert 空间标准正交基状态的指标集,例如对 n 量子比特系统,G 就可以是 0 到2 n − 1 2^n-1 2 n − 1 的数的集合。
设我们有个酉算子U k U_k U k ,它进行的运算为:U k ∣ x ⟩ = ∣ x + k ⟩ U_k|x\rang=|x+k\rang U k ∣ x ⟩ = ∣ x + k ⟩ ,把它作用于∑ h ∈ H a h ∣ h ⟩ \sum_{h\in H}a_h|h\rang ∑ h ∈ H a h ∣ h ⟩ ,然后再进行 Fourier 变换:
U k ∑ h ∈ H a h ∣ h ⟩ = ∑ h ∈ H a h ∣ h + k ⟩ → ∑ g ∈ G a g ~ ′ ∣ g ⟩ a g ~ ′ = ∑ h ∈ H e 2 π i g h / ∣ G ∣ e 2 π i g k / ∣ G ∣ a h = e 2 π i g k / ∣ G ∣ a g ~ U_k\sum_{h\in H}a_h|h\rang=\sum_{h\in H}a_h|h+k\rang\rightarrow\sum_{g\in G}\tilde{a_g}'|g\rang\\
\tilde{a_g}'=\sum_{h\in H}e^{2\pi igh/|G|}e^{2\pi igk/|G|}a_h=e^{2\pi igk/|G|}\tilde{a_g}
U k h ∈ H ∑ a h ∣ h ⟩ = h ∈ H ∑ a h ∣ h + k ⟩ → g ∈ G ∑ a g ~ ′ ∣ g ⟩ a g ~ ′ = h ∈ H ∑ e 2 π i g h / ∣ G ∣ e 2 π i g k / ∣ G ∣ a h = e 2 π i g k / ∣ G ∣ a g ~
不管 k 是几,∣ g ⟩ |g\rang ∣ g ⟩ 对应的概率幅度都不会变,即∣ a g ~ ′ ∣ = ∣ e 2 π i g k / ∣ G ∣ a g ~ ∣ = ∣ a g ~ ∣ |\tilde{a_g}'|=|e^{2\pi igk/|G|}\tilde{a_g}|=|\tilde{a_g}| ∣ a g ~ ′ ∣ = ∣ e 2 π i g k / ∣ G ∣ a g ~ ∣ = ∣ a g ~ ∣ 。
以群论的语言说,G 是一个群,H 是 G 的一个子群。如果一个 G 上的函数 f 在 H 的陪集上是定常的,那么我们说 f 的 Fourier 变换在 H 的陪集上是不变的。(注这里陪集运算是加法,[ a ] = a + H [a]=a+H [ a ] = a + H )
# 算法过程
首先制备初态∣ 0 ⊗ n ⟩ ∣ 0 ⊗ m ⟩ |0^{\otimes n}\rang|0^{\otimes m}\rang ∣ 0 ⊗ n ⟩ ∣ 0 ⊗ m ⟩
应用H ⊗ n H^{\otimes n} H ⊗ n 到第一寄存器生成叠加态→ 1 2 n / 2 ∑ x = 0 2 t − 1 ∣ x ⟩ ∣ 0 ⊗ m ⟩ \rightarrow\frac{1}{2^{n/2}}\sum_{x=0}^{2^t-1}|x\rang|0^{\otimes m}\rang → 2 n / 2 1 ∑ x = 0 2 t − 1 ∣ x ⟩ ∣ 0 ⊗ m ⟩
应用Q F : → 1 2 n / 2 ∑ x = 0 2 t − 1 ∣ x ⟩ ∣ f ( x ) ⟩ Q_F:\rightarrow\frac{1}{2^{n/2}}\sum_{x=0}^{2^t-1}|x\rang|f(x)\rang Q F : → 2 n / 2 1 ∑ x = 0 2 t − 1 ∣ x ⟩ ∣ f ( x ) ⟩
对第二寄存器观测,假设得到结果为C ∗ C^* C ∗ ,则系统坍塌进入→ L 2 n ∑ x , f ( x ) = C ∗ ∣ x ⟩ ∣ C ∗ ⟩ \rightarrow\sqrt{\frac{L}{2^{n}}}\sum_{x,f(x)=C^*}|x\rang|C^*\rang → 2 n L ∑ x , f ( x ) = C ∗ ∣ x ⟩ ∣ C ∗ ⟩ ,记
g C ∗ ( x ) = { L f ( x ) = C ∗ , x ∈ { x 0 , x 0 + L , . . . N − L } 0 e l s e g_{C^*}(x)=\begin{cases}
\sqrt{L}&f(x)=C^*,x\in\{x_0,x_0+L,...N-L\}\\
0&else
\end{cases}
g C ∗ ( x ) = { L 0 f ( x ) = C ∗ , x ∈ { x 0 , x 0 + L , . . . N − L } e l s e
则第一寄存器状态为状态为∣ g C ∗ ⟩ |g_{C^*}\rang ∣ g C ∗ ⟩
对第一寄存器应用 Fourier 变换:
Q F T ∣ g C ∗ ⟩ = ∣ g C ∗ ^ ⟩ = ∑ s = 0 N − 1 g ^ C ∗ ( s ) ∣ s ⟩ QFT|g_{C^*}\rang=|\hat{g_{C^*}}\rang=\sum_{s=0}^{N-1}\hat{g}_{C^*}(s)|s\rang
Q F T ∣ g C ∗ ⟩ = ∣ g C ∗ ^ ⟩ = s = 0 ∑ N − 1 g ^ C ∗ ( s ) ∣ s ⟩
其中,由于 Fourier 变换的移不变性质,概率∣ g ^ C ∗ ( s ) ∣ 2 |\hat{g}_{C^*}(s)|^2 ∣ g ^ C ∗ ( s ) ∣ 2 是不依赖于C ∗ C^* C ∗ 的。 ,或言之:
g ^ C ∗ ( x ) = 1 N ∑ y = 0 N − 1 e 2 π i x y / N g C ∗ ( y ) = L N ∑ y ∈ { x 0 , x 0 + L , . . . , N − L + x 0 } e 2 π i x y / N = L N e 2 π i x x 0 / N ∑ y ∈ { 0 , L , 2 L , . . . , N − L } e 2 π i x y / N = { N L e 2 π i x x 0 / N x ∈ { 0 , N L , 2 N L , . . . , ( L − 1 ) N L } 0 e l s e \hat{g}_{C^*}(x)=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi ixy/N}g_{C^*}(y)=\sqrt{\frac{L}{N}}\sum_{y\in\{x_0,x_0+L,...,N-L+x_0\}}e^{2\pi ixy/N}=\sqrt{\frac{L}{N}}e^{2\pi ixx_0/N}\sum_{y\in\{0,L,2L,...,N-L\}}e^{2\pi ixy/N}\\
=\begin{cases}\sqrt{\frac{N}{L}}e^{2\pi ixx_0/N}&x\in\{0,\frac{N}{L},2\frac{N}{L},...,(L-1)\frac{N}{L}\}\\
0&else
\end{cases}
g ^ C ∗ ( x ) = N 1 y = 0 ∑ N − 1 e 2 π i x y / N g C ∗ ( y ) = N L y ∈ { x 0 , x 0 + L , . . . , N − L + x 0 } ∑ e 2 π i x y / N = N L e 2 π i x x 0 / N y ∈ { 0 , L , 2 L , . . . , N − L } ∑ e 2 π i x y / N = { L N e 2 π i x x 0 / N 0 x ∈ { 0 , L N , 2 L N , . . . , ( L − 1 ) L N } e l s e
显然e 2 π x x 0 / N e^{2\pi xx_0/N} e 2 π x x 0 / N 只是个全局相位不影响测量。
所以
∣ g ^ C ∗ ⟩ = 1 L ∑ s , s L = 0 ( m o d N ) e 2 π i x 0 s / N ∣ s ⟩ |\hat{g}_{C^*}\rang=\frac{1}{\sqrt{L}}\sum_{s,sL=0(modN)}e^{2\pi ix_0s/N}|s\rang
∣ g ^ C ∗ ⟩ = L 1 s , s L = 0 ( m o d N ) ∑ e 2 π i x 0 s / N ∣ s ⟩
其中ϕ = e 2 π i x 0 x / N \phi=e^{2\pi ix_0x/N} ϕ = e 2 π i x 0 x / N 是个不影响测量的全局相位。
然后我们可以对第一寄存器进行测量。测出来的结果是一个随机的k\frac{N}{L},k\in\
我们重复这个过程两次,然后测出k 1 N L , k 2 N L k_1\frac{N}{L},k_2\frac{N}{L} k 1 L N , k 2 L N ,再去最大公因数。实际上,g c d ( k 1 , k 2 ) = 1 gcd(k_1,k_2)=1 g c d ( k 1 , k 2 ) = 1 的概率≥ 25 % \geq 25\% ≥ 2 5 %
因此我们重复两遍就可以很大概率得出N L \frac{N}{L} L N ,然后再用 N 去除就可以得到 L 了
# 补充说明
显然,我们遇到的问题往往不能保证N = 2 n N=2^n N = 2 n 和L ∣ N L|N L ∣ N ,即加法并不需要循环。
当N ≠ 2 n N\neq 2^n N = 2 n 时,我们可以补充定义f ( x ) = − 1 , N ≤ x < 2 n f(x)=-1,N\leq x<2^n f ( x ) = − 1 , N ≤ x < 2 n ,其中− 1 -1 − 1 为一个在f ( 0 ) f(0) f ( 0 ) ~f ( N − 1 ) f(N-1) f ( N − 1 ) 中没出现过的数。那么对第二寄存器测量时,如果出现− 1 -1 − 1 ,就重复过程。这样的话其他操作不变显然也可以实现要求。
当L L L 不整除N N N 时,我们进行上述算法过程仍然以≥ 0.4 / L \geq 0.4/L ≥ 0 . 4 / L 的概率得到一个离k N L k\frac{N}{L} k L N 最近的整数。下面我们证明这个命题
在之前,
g C ∗ ( x ) = { L f ( x ) = C ∗ , x ∈ { x 0 , x 0 + L , . . . N − L } 0 e l s e , g ^ C ∗ ( x ) = { N L e 2 π i x x 0 / N x ∈ { 0 , N L , 2 N L , . . . , ( L − 1 ) N L } 0 e l s e g_{C^*}(x)=\begin{cases}
\sqrt{L}&f(x)=C^*,x\in\{x_0,x_0+L,...N-L\}\\
0&else
\end{cases},\hat{g}_{C^*}(x)=\begin{cases}\sqrt{\frac{N}{L}}e^{2\pi ixx_0/N}&x\in\{0,\frac{N}{L},2\frac{N}{L},...,(L-1)\frac{N}{L}\}\\
0&else
\end{cases}
g C ∗ ( x ) = { L 0 f ( x ) = C ∗ , x ∈ { x 0 , x 0 + L , . . . N − L } e l s e , g ^ C ∗ ( x ) = { L N e 2 π i x x 0 / N 0 x ∈ { 0 , L N , 2 L N , . . . , ( L −