上一篇:[科普] 量子计算通识 - 7-Deutsch 算法解析
这一篇我们来看一下多伊奇问题 n 位算法是怎么推导出来的. 关于多伊奇问题请看[上一篇文章] 的开始部分.
多位电路
我们先看一下上篇文章使用过的这张电路图:
上篇文章我们只考虑输入一个 .
计算
在这个电路里面, 输入的是 个
很多时候, 量子位之间的 被省略.
每个量子位都经过 Hadamard 门, 即 :
我们注意到:
这表示什么呢? 还记得抛两枚硬币的情况吗?
这个表示 4 种状态的每一种状态可能性都是, 它处于不确定的叠加态. 对每一种状态来说, 都可以对应一个十进制数字, 那么就是 0,1,2,3, 我们用下标表示 10 进制, 也就有:
推而广之, 忽略 10 进制下标, 变成求和, 从 到, 就得到:
替换到 中得到:
计算
操作的作用是:
我们在上一篇文章推导过, 操作后, 无论 都有:
同样 时候都有:
实际上对于任意 都有:
即:
我们把这个式子带入 得到经过 操作的:
计算
在这里我们可以直接忽略最后一个比特了, 就是忽略掉结尾的
我们对每个
怎么计算
我们注意到 和的区别, 那么我们就有:
但这只是针对单个比特的, 如果是多个比特呢? 先看 2 个比特的情况:
如果是 位的话, 那么就有:
我们 表示 , 我们 表示 , 设定格式 表示
, 用那么就有:
注意这里 总计需要 次求和. 比如前面的两位的例子 就要进行四次:
好了, 我们回到 的上部分:
最终测量
注意上面式子里的 和都是 0 或 1.
这里的求和 来自最早的 Hadamard 操作, 表示从 0 到 ; 而 中的 则是来自 操作, 它代表任意数字. 个量子位的
关于测量, 其实就是计算每个方向上的可能性. 而每个方向就是每种状态, 对于单比特就是每个轴向, 横正向和竖正向.
数学上:
测量得到 .
对于四项的竖列也是同样, 比如抛两枚硬币得到的结果就有 4 个方向或者说四个状态:
这也对应了四个比特表示
, 并且概率之和是 1, 就是
好了, 回到我们的.
它也可以视为 次求和, 类似
我们只关注假设
的每一次 都是 0, 就有
也都是 0, 测量
当 是 Constant 常数操作的时候, 如果 ,, 求和结果是, 最终平方后是 1; 如果,, 求和结果是, 最终平方后还是 1. 就是说如果 是常数操作, 那么最终测得
当 是 Constant 常数操作的时候, 一半情况 , 另一半情况, 而进行 次求和, 这是全部可能, 也是个偶数,和 各占一半, 正好抵消, 结果将是 0. 也就是说如果 是 Constant 常数, 那么就不会测得
虽然在数学上似乎是推导完成了, 但是很多地方仍然缺乏较好的解释, 后续将继续学习和改进.
来源: http://www.jianshu.com/p/2b9cf7bedf81