量子计算 [3] -- DeutscheJozsa算法
算法简介
DeutscheJozsa算法是用于求解一个问题:
有一个未知的函数 f: {0,1}^n → {0,1} [这个函数是接收n个0或1, 输出1个0或1], 已知这个 f 要么是常数函数(Constant function), 要么是均衡函数(Balance function)[均衡函数的意思是说 f 对于所有可能的输入, 有一半输出0, 另外一半输出1]. 设计算法检测 f 是常数函数还是均衡函数
传统算法
因为函数输入是n个0或1, 把输入看作一个二进制数, 那么 f: x → {0,1}; x ∈ Z∩[0, 2^n)
给定一个范围D, 对 f 进行历遍, 当存在两种不一致的输出时, f 不是常数函数, 那么 f 即是均衡函数. 如果 f 是均衡函数, 那么在
范围Z∩[0, 2^n)里有一半输入到 f 后输出为同样的结果, 那么为了确定 f 是否为常数函数, 范围D的大小至少为 2^(n-1)+1
于是传统算法为: 在大小为 2^(n-1)+1 的范围D内, 对 f 进行历遍, 如果存在不相同的输出, 则 f 为均衡函数, 否则 f 为常数函数
不难看出, 如果 f 为常数函数, 则需要调用函数 2^(n-1)+1 次, 或者在第 2^(n-1)+1 次时才有不相同的结果, 运气好的话第2次就可以得到与第1次不一样的结果
量子算法
因为量子位门属于可逆逻辑门, 所以所有量子计算都在已有的量子位上进行, 而不会输出任何结果. 为此, 需要把函数 f 进行"可逆化"
之前说过, 一个n量子位系统的状态可以表示为 |ψ❭ = c_0|0❭ + ... + c_{2^n-1}|2^n-1❭. 不妨把"可逆化"的 f 记为 Uf. Uf 把所有 f 输出为1的状态的相位进行翻转 [当然也可以设为 f 为0时翻转, 没有大问题]. 有了 Uf, 调用一次 Uf 就获得全部结果成为可能
所有量子位都以 |0❭ 初始化, 为了制备均匀叠加的量子态, 可以对所有量子位通过H门, 用3量子位做示例:
把拥有均匀叠加的量子位系统通过 Uf 后, f 的所有输出已经蕴含在量子位的相位里. 但因为测量量子位会使量子位坍缩到测量结果里而失去其他状态的信息, 并且不存在有效测量相位的途径, 所以还不能得到需要的结果
这时候把量子位状态互相干涉, 即通过H门. 之后, 测量所有量子位. 如果 f 为常数函数, 则干涉会在|0❭增长, 而在其他状态消减为0, 如果 f 为均衡函数, 则在|0❭消减为0. 所以如果测量结果全为0, 表明 f 为常数函数, 否则为均衡函数
可以看到量子算法里只对未知函数调用了1次, 相较于传统算法最少2次, 最多2^(n-1)+1次, 加速效果是非常明显的
数学细节可以期待一下未来的附章
DeutscheJozsa算法尽管没有实机用途, 但是作为量子计算入门是一个非常好的实例了
算法演示: [github.com/nyasyamorina/nyasQuantumCalculate/blob/main/examples/2-DeutschJozsaAlgorithm.py]
日常推自制库和瑟图群: [https://github.com/nyasyamorina/nyasQuantumCalculate] [274767696]
