注册| 登录

Deutsch 算法

2018-03-04

Deutsch 算法常用来演示说明量子计算如何在计算能力上超越经典计算。

考虑函数 f(x),其定义域为 f0, 1g,且 f(x) ∈ f0, 1g。易知这样的函数共有四种情况。其中一种情况是f(0) = f(1) = 0,另一种情况是 f(0) = f(1) = 1,这两种情况 f(x) 都是常函数;还有两种情况,即 f(0) = 0、 f(1) = 1 和 f(0) = 1、 f(1) = 0,这两种情况函数f(x) 都有两个取值,且 f(x) = 0 和 f(x) = 1 对应自变量取值的个数相等,称为平衡函数。表1.1 列举了这四种不同的函数。现在我们想要判断函数 f(x) 是常函数还是平衡函数。如果采用经典计算的方式,我们需要分别计算 f(0) 和 f(1),然后判断 f(0) 和 f(1) 是否相等。也就是说,采用经典计算的方式确定 f(x) 是否为常函数,需要进行两次计算。如果采用量子计算的方式,通过 Deutsch 算法,则只需一次计算就可以确定。

QQ图片20180118152346.png

表 1. 定义域为 {0,1} 且值域为 {0,1} 的子集的函数 f(x)。这样的函数共有四个,其中两个是常函数,另外两个是平衡函数。

QQ图片20180118152521.png

图 1 Deutsch 算法及 Deutsch-Jozsa 算法的量子线路图。(a) Deutsch 算法。(b) DeutschJozsa 算法。图中量子逻辑门 Uf 对量子比特的态的作用见正文。


图1 a 为 Deutsch 算法的量子线路图。通过 Deutsch 算法判断 f(x) 是否为常函数,共需要两个量子比特。两个量子比特的初态为

image.png

然后对两个量子比特分别施加 Hadamard 门,则得到的态为

image.png

image.png 施加量子逻辑门 Uf,其中 Uf 对量子比特的态的作用为

image.png

y ⊕ f(x) 代表 y + f(x) 除以 2 的余数。故

image.png

可得

image.png

因此, Uf 作用于态image.png得到的态为

image.png

可见,如果 f(x) 是常函数,则第一个量子比特的态为 image.png;反之,如果 f(x) 是平衡函数,则第一个量子比特的态为 image.png。再对第一个量子比特施加 Hadamard 门,则两个量子比特的末态为

image.png

image.pngimage.png 作为基矢对第一个量子比特进行测量。如果 f(x) 是常函数,则测量结果必然是 0;如果 f(x) 是平衡函数,则测量结果是 1。换言之,如果测量结果是 0,则说明 f(x) 是常函数,而测量结果是 1 则说明 f(x) 是平衡函数。这样,通过 Deutsch 算法,我们将问题的可能的两个解(f(x) 是常函数、 f(x) 是平衡函数),对应到第一个量子比特的两个可区分的态,进一步对应到两个确定的测量结果,从而可以根据测量结果确定问题的解。注意在执行 Deutsch 算法时,我们将量子比特制备到 image.pngimage.png 的叠加态,只进行了一次计算,就可以确定 f(x)是否为常函数;而如果采用经典计算的方式,如前所述,需要两次计算。


Deutsch 算法还可以推广到更一般的情况。考虑定义在 {0, 1, ..., 2n - 1g}上的函数 f(x),满足 f(x) ∈ {0, 1},且 f(x) 要么为常函数要么为平衡函数。也就是说,要么对于定义域 {0, 1, ..., 2n - 1} 中所有的元素 x,函数 f(x) 的值为常数 0 或1;要么定义域 {0, 1, ..., 2n - 1} 中有一半的元素使得 f(x) 的值为 0,另一半的元素使得 f(x) 的值为 1。我们的目标是确定 f(x) 是常函数还是平衡函数。如果采用经典计算的方式,要得到确定无误的判断,运气不好的话需要进行 2n-1 + 1次计算。这是因为,当我们选取定义域中 2n-1 个元素分别计算后,有可能得到2n-1 个相同的函数值,这种情况下我们仍不能确定无误的得出 f(x) 是常函数还是平衡函数的结论。如果采用量子计算的方式,类似 f(x) 定义域为 {0, 1} 的情况,只需要一次计算就可以确定。解决这个问题的量子算法称为 Deutsch-Jozsa算法(Deutsch-Jozsa algorithm),是对 Deutsch 算法在更一般情况下的推广 。图1b 为 Deutsch-Jozsa 算法的量子线路图。对量子比特施加完 Deutsch-Jozsa算法中的所有量子逻辑门后,以 image.png 作为基矢对前 n 个量子比特进行测量。分析可知,当且仅当 f(x) 是常函数时,测量结果为 0。换言之,如果测量结果为 0,则说明 f(x) 是常函数;反之,如果测量结果不为 0,则说明 f(x) 是平衡函数。


参考文献:

1. D. Deutsch and R. Jozsa, Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London A 439, 553 (1992).

2. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press (2000).

3. 耿建培,“基于固态自旋量子比特的高保真度量子逻辑门的实验研究”,中国科技大学博士学位论文(2017).

收藏 评论:0
没有ID?去注册 忘记密码? 已有账号,马上登陆

添加表情