量子计算 [4].ext + Long算法

2021-04-17 15:11 作者:nyasyamorina 0人读过 | 我要投稿

Grover搜索算法详解

Grover搜索算法分为两步: 制备均匀叠加态和迭代某个过程, 而迭代可以分为两小步: 作用相位黑盒和作用Grover扩散算子.

而Grover算子为 $G%3DW%5E%7B-1%7D(2%7C0%5En%5Crangle%5Clangle0%5En%7C-I)W$ , 其中W为Walsh-Hadamard变换 [或叫H变换也ok].

Walsh-Hadamard变换

H变换是一个广义傅里叶变换, 同时也是计算最简单的广义傅里叶变换, N阶H变换定义为: $W_%7B2%5En%7D%3DH%5E%7B%5Cotimes%20n%7D$ , N = 2^n, 其中 $H%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B2%7D%7D%5Cbegin%7Bbmatrix%7D1%261%5C%5C1%26-1%5Cend%7Bbmatrix%7D$ , n为量子位数量. 不难发现这个H矩阵定义与H门一致. 所以H变换在量子计算表现为把H门作用在全部量子位上. 并且因为H门的逆也为H门, 所以H变换的逆也为H变换.

既然H变换是广义傅里叶变换, 那么不难推测H变换实质上也是在分析频率. 但是看到Grover算子中间的部分 $2%7C0%5En%5Crangle%5Clangle0%5En%7C-I$ , 只与变换后的第1个分量有关, 那么只需要关心变换的第1个分量: $W_N%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN%7D%7D%5Cbegin%7Bbmatrix%7D1%261%26%5Ccdots%261%5C%5C%5Cvdots%26%5Cvdots%26%5Cddots%26%5Cvdots%5Cend%7Bbmatrix%7D$ , 可以看到变换的第1个分量与数据的总和有关, 或者说与均值有关.

Grover算子

稍微把Grover算子扔进人肉计算机里可以得到: $G%3D2P-I$ , 其中 $P_%7Bjk%7D%3D%5Cfrac%7B1%7D%7B2%5En%7D$ , 在不考虑辐角的情况下, 也就是只有实数时, Grover算子实际上就是以系统的均值取对称 [近似对称]. 原论文里的两个例子:

整个迭代

把正确答案写为 $%7Cg%5Crangle$ , 错误答案写为 $%7Cb%5Crangle$ , 则定义 $%7CGood%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BM%7D%7D%5Csum_g%7Cg%5Crangle$ 和 $%7CBad%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN-M%7D%7D%5Csum_b%7Cb%5Crangle$ , 其中M为全部正确答案的总数, N为全部答案的总数 [一般N=2^n, n为量子位数量]. 则均匀叠加态写为 $H%5E%7B%5Cotimes%20n%7D%7C0%5En%5Crangle%3D%7C%2B%5En%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN%7D%7D%5Csum_%7Bx%3D0%7D%5E%7BN-1%7D%7Cx%5Crangle%3Dsin%5Ctheta%7CGood%5Crangle%2Bcos%5Ctheta%7CBad%5Crangle$ , 其中 $%5Ctheta%3Dsin%5E%7B-1%7D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D$ .

相位黑盒把所有正确答案的相位翻转, 即 $U_f%3DI-2%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C%3D%7CBad%5Crangle%5Clangle%20Bad%7C-%7CGood%5Crangle%5Clangle%20Good%7C$

因为Grover搜索算法是从均匀叠加态开始, 所以在算法中任意时刻 $%7Cg%5Crangle$ 之间的系数都是一致的, 同理 $%7Cb%5Crangle$ 之间也存在这样的关系. 设在某次迭代前系统状态为 $%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle%2Bsin%5Cbeta%7CGood%5Crangle$ . 作用相位黑盒把正确答案的相位翻转: $U_f%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle-sin%5Cbeta%7CGood%5Crangle$ . 此时系统的均值为 $avg%3D%5Cfrac%7B1%7D%7BN%7D(%5Csqrt%7BN-M%7Dcos%5Cbeta-%5Csqrt%7BM%7Dsin%5Cbeta)$ , 作用Grover算子后系统状态为

$GU_f%7C%5CPsi%5Crangle%3D(cos(2%5Ctheta)cos%5Cbeta-sin(2%5Ctheta)sin%5Cbeta)%7CBad%5Crangle%2B(sin(2%5Ctheta)cos%5Cbeta%2Bcos(2%5Ctheta)sin%5Cbeta)%7CGood%5Crangle$

可以看到单次迭代的净效应是在 $%5C%7BO%3B%7CBad%5Crangle%2C%7CGood%5Crangle%5C%7D$ 空间里逆时针旋转了2θ. 所以最佳迭代次数 j 应该使得系统状态最接近 $%7CGood%5Crangle$ , 也就是与 $%7CBad%5Crangle$ 的夹角为π/2, 即 $j%20%3D%20%5Cleft%5B%5Cfrac%7B%5Cfrac%7B%5Cpi%7D%7B2%7D-%5Ctheta%7D%7B2%5Ctheta%7D%5Cright%5D%3D%5Clfloor%5Cfrac%7B%5Cpi%7D%7B4%5Ctheta%7D%5Crfloor$ , 其中 $%5Clfloor%20%5Crfloor%20$ 为向下取整 [floor].

详细计算过程可以看本文结尾 -- 附1

Long算法

Long算法由龙桂鲁教授提出, 可以以概率1给出正确答案.

在Grover算法里, 迭代次数 j 由系统状态在 $%5C%7BO%3B%7CBad%5Crangle%2C%7CGood%5Crangle%5C%7D$ 空间里转动的角度2θ确定, 但因为j只能为正整数, 并且转动角度2θ不够精细, 导致系统状态几乎不可能刚好等于 $%7CGood%5Crangle$ , 即不太可能以概率1给出正确结果.

Long算法的篇幅实在过长, 需要深入了解的可以去看看原论文. 这里稍微简述一下.

拓展Grover搜索算法: 相位黑盒从 $U_f%3DI-2%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C$ 拓展为 $I%2B(e%5E%7Bi%5Cphi%7D-1)%5Csum_g%7Cg%5Crangle%5Clangle%20g%7C$ , 即从把正确答案的相位旋转π改为旋转 $%5Cphi$ . Grover算子从 $G%3DW(I-2%7C0%5En%5Crangle%5Clangle0%5En%7C)W$ 拓展为 $W(I%2B(e%5E%7Bi%5Cvarphi%7D-1)%7C0%5En%5Crangle%5Clangle0%5En%7C)W$ , 即从把系统状态沿着均值取对称[近似]变为沿着均值把相位旋转φ. 拓展后为了使算法有意义, 需要满足相位匹配条件 $%5Cphi%3D%5Cvarphi$ .

在Long算法里, 需要指定迭代次数 j, 然后求得旋转相位 $%5Cvarphi%20%3D%202sin%5E%7B-1%7D%5Cleft(%5Cfrac%7Bsin(%5Cfrac%7B%5Cpi%7D%7B4j%2B2%7D)%7D%7Bsin%5Ctheta%7D%5Cright)$ , 为了确保相位有意义, 迭代次数需要满足 $j%3E%5Clfloor%5Cfrac%7B%5Cpi%7D%7B4%5Ctheta%7D-0.5%5Crfloor$ , 可以看到Long算法的迭代次数不可以比Grover算法里的迭代次数少, 当 j 小于等于这个下限时, 旋转相位φ为复数, 则算法失去意义.

修改本篇里的Grover算法为Long算法, 需要注意的是, 旋转门需要在使用前确定, 并且旋转角度是由迭代次数确定, 也就是需要在制作黑盒前就确定迭代次数

接下来修改黑盒s:

为了确保一致性, GroverOperator和RunGroverSearching就没有改名字了. 因为Long算法以概率1给出正确答案, 所以并不需要检查答案, 则主体为

优化输出和结果检查套用本篇里的就好.

G. L. Long $Grover%5C%3AAlgorithm%5C%3Awith%5C%3Azero%5C%3Atheoretical%5C%3Afailure%5C%3Arate$ (2001)

附1

作用相位黑盒后的系统状态为

$U_f%7C%5CPsi%5Crangle%3Dcos%5Cbeta%7CBad%5Crangle-sin%5Cbeta%7CGood%5Crangle%3D%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D%5Csum_b%7Cb%5Crangle-%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D%5Csum_g%7Cg%5Crangle$

则均值为

$avg%3D%5Cfrac%7B1%7D%7BN%7D(%5Csum_b%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D-%5Csum_g%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D)%3D%5Cfrac%7B1%7D%7BN%7D(%5Csqrt%7BN-M%7Dcos%5Cbeta-%5Csqrt%7BM%7Dsin%5Cbeta)$

作用Grover算子 $G%3D2P-I$ 为

$GU_f%7C%5CPsi%5Crangle%3D(2avg-%5Cfrac%7Bcos%5Cbeta%7D%7B%5Csqrt%7BN-M%7D%7D)%5Csum_b%7Cb%5Crangle%2B(2avg%2B%5Cfrac%7Bsin%5Cbeta%7D%7B%5Csqrt%7BM%7D%7D)%5Csum_g%7Cg%5Crangle%3D(2%5Csqrt%7BN-M%7Davg-cos%5Cbeta)%7CBad%5Crangle%2B(2%5Csqrt%7BM%7Davg%2Bsin%5Cbeta)%7CGood%5Crangle$

$GU_f%7C%5CPsi%5Crangle%3D((1-%5Cfrac%7B2M%7D%7BN%7D)cos%5Cbeta-%5Cfrac%7B2%5Csqrt%7BM(N-M)%7D%7D%7BN%7Dsin%5Cbeta)%7CBad%5Crangle%2B(%5Cfrac%7B2%5Csqrt%7BM(N-M)%7D%7D%7BN%7Dsin%5Cbeta%2B(1-%5Cfrac%7B2M%7D%7BN%7D)sin%5Cbeta)%7CGood%5Crangle$

又因为 $sin%5Ctheta%3D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D%3Bcos%5Ctheta%3D%5Csqrt%7B%5Cfrac%7BN-M%7D%7BN%7D%7D$ , 使用倍角公式 $cos(2x)%3D1-2sin%5E2x%3Bsin(2x)%3D2cosxsinx$ 化简得:

$GU_f%7C%5CPsi%5Crangle%3D(cos(2%5Ctheta)cos%5Cbeta-sin(2%5Ctheta)sin%5Cbeta)%7CBad%5Crangle%2B(sin(2%5Ctheta)cos%5Cbeta%2Bcos(2%5Ctheta)sin%5Cbeta)%7CGood%5Crangle$

标签：

量子计算 [4].ext + Long算法

量子计算 [4].ext + Long算法的评论 (共条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [4].ext + Long算法

本文作者的其他文章

量子计算 [4].ext + Long算法的评论 (共 条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [4].ext + Long算法的评论 (共条)