量子计算 [3].ext + 量子黑盒

2021-04-06 19:25 作者:nyasyamorina 0人读过 | 我要投稿

Deutsche Jozsa 算法原理

首先系统初始化为 |ψ❭ = |0❭, 全部量子位通过H门制备均匀叠加态 $H%5E%7B%5Cotimes%20n%7D%7C0%5Crangle%5E%7B%5Cotimes%20n%7D%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bx%3D0%7D%5E%7B2%5En-1%7D%7Cx%5Crangle$

任何通过 Uf, 使全部让 f 为1的状态的相位翻转, 让 f 为0的状态则不进行任何操作 $U_fH%5E%7B%5Cotimes%20n%7D%7C0%5Crangle%5E%7B%5Cotimes%20n%7D%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5En%7D%7D%5Csum_%7Bx%3D0%7D%5E%7B2%5En-1%7D(-1)%5E%7Bf(x)%7D%7Cx%5Crangle$

再次让全部量子位通过H门, 产生干涉 $H%5E%7B%5Cotimes%20n%7DU_fH%5E%7B%5Cotimes%20n%7D%7C0%5Crangle%5E%7B%5Cotimes%20n%7D%3D%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7By%3D0%7D%5E%7B2%5En-1%7D%7Cy%5Crangle%5Csum_%7Bx%3D0%7D%5E%7B2%5En-1%7D(-1)%5E%7Bf(x)%7D(-1)%5E%7Bx%5Ccdot%20y%7D$ . 这里, x · y是指在{0,1}^n空间里进行内积, 也就是 $x%5Ccdot%20y%3Dx_1y_1%5Coplus%20x_2y_2%5Cotimes%5Ccdots%5Cotimes%20x_ny_n$

这时候, 测量系统得到 |0❭ 的概率为 $%5Clangle%200%7C%5E%7B%5Cotimes%20n%7DH%5E%7B%5Cotimes%20n%7DU_fH%5E%7B%5Cotimes%20n%7D%7C0%5Crangle%5E%7B%5Cotimes%20n%7D%3D%5Cleft%7C%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7Bx%3D0%7D%5E%7B2%5En-1%7D(-1)%5E%7Bf(x)%7D%5Cright%7C%5E2$

可以看到, 当 f 为常数函数时, 测量系统得到 |0❭ 的概率为1; f 为均衡函数时, 累加项互相抵消变为0

量子黑盒

黑盒(Black Box)是指已知输入和输出范围的未知操作, 这里函数 f 就是一个典型的黑盒

因为量子操作"不存在"输出, 所以黑盒只能在给出的量子位上进行操作. 常见的黑盒为相位(Phase)黑盒和标记(Marking)黑盒两种, 下面分别介绍两种黑盒的特性: [设量子黑盒 Uf 有相应的传统黑盒 f, 并且 f 的输出为0或1]

相位黑盒: 翻转特定状态的相位. 设|x❭为某个特定的状态, 如果f(x)=1, 则翻转|x❭的状态, 否则什么也不做, 即 $U_fc_x%7Cx%5Crangle%3D(-1)%5E%7Bf(x)%7Dc_x%7Cx%5Crangle$
标记黑盒: 输入数据位和结果位, 结果位为1个量子位, 调转特定状态时的结果位. 设|x❭为数据位, |y❭为结果位, 如果f(x)=1, 则把|0_y❭和|1_y❭互换, 否则什么也不做, 即 $U_f(%7Cx%5Crangle%5Cotimes(c_0%7C0_y%5Crangle%2Bc_1%7C1_y%5Crangle))%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%7Cx%5Crangle%5Cotimes(c_0%7C0_y%5Crangle%2Bc_1%7C1_y%5Crangle)%3Bf(x)%3D0%5C%5C%20%0A%7Cx%5Crangle%5Cotimes(c_1%7C0_y%5Crangle%2Bc_0%7C1_y%5Crangle)%3Bf(x)%3D1%5Cend%7Bmatrix%7D%5Cright.$ . 标记黑盒也常写作 $U_f%7Cx%2Cy%5Crangle%3D%7Cx%2Cy%5Coplus%20f(x)%5Crangle$

比较相位黑盒和标记黑盒, 相位黑盒比标记黑盒节约了一个量子位, 在繁琐的黑盒调用时可以减少空间使用开销. 而标记黑盒不需要修改数据位, 算法设计比较容易方便

DeutscheJozsa算法常用的黑盒

下面介绍几种在DeutscheJozsa算法演示中常用的几种黑盒, 以演示相位黑盒的内部逻辑

可以看到相位黑盒内部逻辑比较特异化. 如果函数 f 的内部逻辑不易"翻译"为量子计算的话, 使用相位黑盒将会非常困难.

相位反冲

相位反冲是一个把标记黑盒转为相位黑盒的技巧, 使得同时具有标记黑盒的算法易设计和相位黑盒的少量子位的特点. 这个技巧需要一个临时的额外量子位用于转化, 转化完后这个量子位可以立即抛弃.

小例子: 比较两个量子位是否相同

设计标记黑盒, 给出两个数据量子位和一个结果位, 如果两个量子位相同则互换结果位的|0❭和|1❭:

试着运行一下:

可以看到 |000❭ 变为 |001❭, |110❭ 变为 |111❭, 也就是左边两位相同的状态会把第3位的|0❭变为|1❭, 其他情况也可以自己测试

如果结果位原本的状态是 |0❭-|1❭[忽略归一化因子] , 并作用标记黑盒会怎么样呢? 因为如果 f(x) = 0时, 标记黑盒和相位黑盒都不对量子位有影响, 所以只考虑 f(x)=1时: $U_f(%7Cx%5Crangle%5Cotimes(%7C0%5Crangle-%7C1%5Crangle))%3D%7Cx%5Crangle%5Cotimes(%7C1%5Crangle-%7C0%5Crangle)%3D-1%7Cx%5Crangle%5Cotimes(%7C0%5Crangle-%7C1%5Crangle)$ , 可以看到这时候相当于结果位没有改变却在数据位上翻转了相位. 这就是相位反冲

继续使用上面例子: 加入一个包装器把相位反冲应用到标记黑盒上:

测试一下 IsEqualPhase:

使用颜色表示相位, 红色为0, 青色为π, 可以看到|00❭和|11❭的相位都被翻转了, 则表明IsEqualPhase是一个相位黑盒

标签：

量子计算 [3].ext + 量子黑盒

量子计算 [3].ext + 量子黑盒的评论 (共条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [3].ext + 量子黑盒

本文作者的其他文章

量子计算 [3].ext + 量子黑盒的评论 (共 条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [3].ext + 量子黑盒的评论 (共条)