量子计数 [5+4i] -- 量子计数

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

已知有一个函数 a $f%3A%5C%7B0%2C1%5C%7D%5En%5Crightarrow%5C%7B0%2C1%5C%7D$ , 求使得 f 输出1的输入总数.

求解这个问题的算法叫做量子计数(Quantum Counting). 实际上这个算法是Grover算法和相位估计的结合应用. 所以这里也不详细叙述了.

在Grover算法的附章里, 详细讨论了在n个量子位系统里, 单次迭代过程对态的变换为 $GU_f%3D%5Cbegin%7Bbmatrix%7Dcos(2%5Ctheta)%26-sin(2%5Ctheta)%5C%5Csin(2%5Ctheta)%26cos(2%5Ctheta)%5Cend%7Bbmatrix%7D$ , 其中 $G%3DW(2%7C0%5En%5Crangle%5Clangle0%5En%7C-I)W$ 为Grover扩散算子, $U_f%3DI-2%7CGood%5Crangle%5Clangle%20Good%7C$ 为量子相位黑盒版的未知函数f, $%5Ctheta%3Dsin%5E%7B-1%7D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D$ 为均匀叠加态 $%7C%2B%5En%5Crangle%3Dcos%5Ctheta%7CBad%5Crangle%2Bsin%5Ctheta%7CGood%5Crangle$ 在空间 $%5Cleft%5C%7BO%3B%7CBad%5Crangle%2C%7CGood%5Crangle%5Cright%5C%7D$ 与 $%7CBad%5Crangle$ 的夹角, $%7CGood%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%20M%7D%5Csum_g%7Cg%5Crangle$ 为全部使未知函数f输出为1的态的叠加, $%7CBad%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%7BN-M%7D%7D%5Csum_b%7Cb%5Crangle$ 为全部使未知函数f输出为0的态的叠加, $M$ 为全部 $%7Cg%5Crangle$ 的数量, $N%3D2%5En$ 为全部态的数量.

不难知道, 单次迭代的特征态与特征值为 $%7Cu_%2B%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt2%7D(%7CBad%5Crangle-i%7CGood%5Crangle)$ , $%5Clambda_%2B%3De%5E%7B2i%5Ctheta%7D$ ; $%7Cu_-%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt2%7D(%7CBad%5Crangle%2Bi%7CGood%5Crangle)$ , $%5Clambda_-%3De%5E%7B-2i%5Ctheta%7D$ . 使用相位估计可以求出θ, 进而求出M, 即使未知函数 f 输出为1的输入数量.

因为特征态乘上一个非零系数也是特征态, 所以 $e%5E%7Bi%5Ctheta%7D%7Cu_%2B%5Crangle$ 和 $e%5E%7B-i%5Ctheta%7D%7Cu_-%5Crangle$ 也分别是单次迭代的特征态. 这两个态的叠加态为 $%5Cfrac%7B1%7D%7B%5Csqrt2%7D(e%5E%7Bi%5Ctheta%7D%7Cu_%2B%5Crangle%2Be%5E%7B-i%5Ctheta%7D%7Cu_-%5Crangle)$ = $cos%5Ctheta%7CBad%5Crangle%2Bsin%5Ctheta%7CGood%5Crangle$ , 也就是说特征态的叠加刚好为容易制备的均匀叠加态 $%7C%2B%5En%5Crangle$ .

使用相位估计对Grover算法里的单次迭代分析, 测量结果得到 $%5Cvarphi_%2B%3D%5Cfrac%7B%5Ctheta%7D%7B%5Cpi%7D$ 和 $%5Cvarphi_-%3D1-%5Cfrac%7B%5Ctheta%7D%7B%5Cpi%7D$ , 即 $sin%5Ctheta%3Dsin(%5Cpi%5Cvarphi_%2B)%3Dsin(%5Cpi-%5Cpi%5Cvarphi)$ , 又因为 $sin(x)%3Dsin(%5Cpi-x)$ , 得 $sin(%5Cpi%5Cvarphi)%3D%5Csqrt%7B%5Cfrac%7BM%7D%7BN%7D%7D$ , 最后求得 $M%3DNsin%5E2(%5Cpi%5Cvarphi)$ .

由相位估计的误差分析不难知道, 最佳测量值 $%5Ctilde%7B%5Cvarphi%7D$ 与实际值 $%5Cvarphi$ 之间存在误差 $%7C%5CDelta%5Cvarphi%7C%3D%5Cleft%7C%5Ctilde%5Cvarphi-%5Cvarphi%5Cright%7C%5Cleq%5Cfrac%7B1%7D%7B2%5E%7Bm%2B1%7D%7D$ , 其中m是用于相位估计的量子位数量. 求解误差为 $%5Cleft%7C%5Cfrac%7B%5CDelta%20M%7D%7BN%7D%5Cright%7C%3D%5Cleft%7C%5Cfrac%7B%5Ctilde%20M-M%7D%7BN%7D%5Cright%7C$ = $%7Csin%5E2(%5Cpi%5Ctilde%5Cvarphi)-sin(%5Cpi%5Cvarphi)%7C$ = $%7Csin(%5Cpi%5Ctilde%5Cvarphi)%2Bsin(%5Cpi%5Cvarphi)%7C%7Csin(%5Cpi%5Ctilde%5Cvarphi)-sin(%5Cpi%5Cvarphi)%7C$ , 因为 $%7Csin(x%2B%5CDelta%20x)-sinx%7C%5Cleq%7C%5CDelta%20x%7C$ 和 $sin(x%2B%5CDelta%20x)%5Cleq%20sinx%2B%5CDelta%20x$ * , 所以 $%5Cleft%7C%5Cfrac%7B%5CDelta%20M%7D%7BN%7D%5Cright%7C%5Cleq%20%5Cpi%7C2sin(%5Cpi%5Cvarphi)%2B%5Cpi%5CDelta%5Cvarphi%7C%7C%5CDelta%5Cvarphi%7C$ , 即 $%7C%5CDelta%20M%7C%5Cleq2%5Cpi%5Csqrt%7BMN%7D%7C%5CDelta%5Cvarphi%7C%2BN%5Cpi%5CDelta%5Cvarphi%5E2$ .

因为测量计算后的结果 $%5Ctilde%20M%3DNsin%5E2(%5Cpi%5Ctilde%5Cvarphi)$ 很可能为小数, 所以需要进行四舍五入. 为了得到准确的M, 自然有条件 $%7C%5CDelta%20M%7C%5Cleq%5Cfrac%7B1%7D%7B2%7D$ , 即 $%7C%5CDelta%5Cvarphi%7C%5Cleq%5Cfrac%7B1%7D%7B4%5Cpi%5Csqrt%7BMN%7D%7D$ $%5CRightarrow$ $2%5E%7Bm%2B1%7D%5Cgeq4%5Cpi%5Csqrt%7BMN%7D$ $%5CRightarrow$ $m%5Cgeq1%2B%5Cfrac%7Bn%7D%7B2%7D%2Blog_2%5Cpi%2B%5Cfrac%7Blog_2M%7D%7B2%7D$ . 一般情况下 $M%5Cleq%5Cfrac%7BN%7D%7B2%7D$ , 有 $m%5Cgeq%20n%2B0.5%2Blog_2%5Cpi%5Capprox%20n%2B2$ . 特别地, 使用 $m%3Dn%2B2$ , 在 $%5Cvarphi%3D0.25$ 时误差 $%5Cleft%7C%5Cfrac%7B%5CDelta%20M%7D%7B2%5Em%5CDelta%5Cvarphi%7D%5Cright%7C$ 取极大值 $%5Cpi%2F4$ , 即 $%7C%5CDelta%20M%7C%5Cleq2%5E%7Bm-2%7D%5Cpi%7C%5CDelta%5Cvarphi%7C%5Cleq%5Cpi%2F8$ .

* 对于|ΔM/N|=|sin(π(φ+Δφ))+sin(πφ)||sin(π(φ+Δφ))-sin(πφ)|, 确实有|sin(π(φ+Δφ))-sin(πφ)|<=π|Δφ|, 但|sin(π(φ+Δφ))+sin(πφ)|<=|2sin(πφ)+πΔφ|在Δφ<0时不一定成立. 实际上这步不是很严谨, 但是教材都这样写, 而且对后续推导没有太大影响, 就这样子吧.

下面以之前用作Grover算法的例子 -- 图形着色问题实际操作一下, 因为大部分代码都在之前演示过, 这里只给出关键代码.

需要注意的是, 上面讨论的Grover扩散算子定义为 $G%3DW(2%7C0%5En%5Crangle%5Clangle0%5En%7C-I)W$ , 但实际上比较常用的版本为 $G%5E%7B'%7D%3DW(I-2%7C0%5En%5Crangle%5Clangle0%5En%7C)W$ , 可以看到两个版本相差了一个相位π, 测量后计算M需要注意一下这个差异.

需要注意的是, 尽管运行精度已经足够测量出准确结果, 但是相位估计算法依然有可能给出偏差比较大的结果从而造成很大的误差. 上述代码里的图为4个顶点, 并且4个顶点之间全部连接, 只有4个顶点都为不同颜色才是正确的着色方案, 即总共正确答案数量为 4! = 24 个.

在实际使用中, 量子计数常搭配Grover算法一起使用, 而Grover算法并不需要准确的M, 并且如果M远远小于N时, 相位估计精度m=n+2实在是overkill. 所以m=n+2总共还是拿来玩玩就好, 计算速度实在是硬伤.

你以为我又要推销瑟图群和垃圾库了? 我这次就不推了 (

一晚上赶出来的专栏, 困shi了. 封面随便在瑟图库里找了一张图, 用latex做封面其实也很花时间好吧.

标签：

量子计数 [5+4i] -- 量子计数

量子计数 [5+4i] -- 量子计数的评论 (共条)

你可能也喜欢这些文章

最新发布的文章

量子计数 [5+4i] -- 量子计数

本文作者的其他文章

量子计数 [5+4i] -- 量子计数的评论 (共 条)

你可能也喜欢这些文章

最新发布的文章

量子计数 [5+4i] -- 量子计数的评论 (共条)