当前位置: 首页 > article >正文

量子计算(10)量子算法2:Deutsch-Jozsa算法

        又到了一周一篇的量子计算啦!全体起立respect!

        前言:本篇文章研究的算法,相当无聊。在日常生活中基本上用不到,但是这个算法却能显著的体现出量子计算算法比经典算法更加快速这一特点。这个算法就好比C语言里的hello world、人工智能里的数字图像识别,亦或者代表植物大战僵尸里的旗帜僵尸。并不代表着Deutsch-Jozsa算法多么有用,只是代表恭喜你,你入了量子计算的门了!

目录

1、单变量平衡函数与常函数        

2、Deustch算法思想步骤


1、单变量平衡函数与常函数        

        对于单变量函数f{0,1}\rightarrow {0,1},即变量与因变量均只能为0或者1的函数。我们把具有以下类型真值表的函数,称之为常函数:

xf1(x)
00
10

        或者:

xf2(x)
01
11

        即不管输入怎么样,输出只能全为1或者全为0的函数为常函数。它要么善良的很纯粹,要么坏的很纯粹。

        我们把具有以下类型的真值表的函数,称为平衡函数:

xf3(x)
00
11

        或者:

xf4(x)
01
10

        即输出里面有一半是1有一半是0,是一个亦正亦邪的存在。

        对于经典算法来说,我们需要两次测试,才能得出,这是一个怎样的函数。但是,量子计算就特别强,它只需要一次测试,就能得出来。欲知如何操作,请看下文:

2、Deustch算法思想步骤

        还记得上篇文章,我们说过,量子计算里面的变换都是酉变换,是一个可逆电路,对平衡函数,显然满足,但是对于常函数,我们必须进行改造。考考大家,如何对此函数进行改造?

         答案如上图,怎么样,有没有想到呢?由这部分电路一起构成下文的Uf,我们令F=y\oplusf(x),我们还是列一个真值表:

xyx,F1(x)x,F2(x)x,F3(x)x,F4(x)
000010001
0101000100
1010111110
1111101011

        满足可逆性!

        我们想要一次就能检测出来,说明我们的输入必然为一个叠加态(有|0>也有|1>),那么我们很容易想到H门。至于输出结果的辅助位,暂时还不清楚到底要怎么设计,暂且就让它为|0>态吧。

         所以我们暂时能得到上面这张图。我们逐步分析一下\psi _{1}\psi _{2}的状态。容易知道\psi _{1}状态下,量子态为\frac{ |00>+|01>}{\sqrt{2}},而\psi _{2}态为\frac{|F(0)0>+|F(1)1>}{\sqrt{2}}

        这个时候就有读者会说:“好嘛,亏我还这么相信小编,小编的这波操作下来,让我一脸懵逼,这有啥区别啊?还不是判断不出来平衡函数与常函数?”

        欸?此言差矣?至少我们踏出来了正确的一步。我们仔细想想,之所以没有差别,原因在于什么?显然是在于我们没有修改的|0>态啊。但是,如果只改为|1>态,照样一点用都没有,会与|0>态时一样,没有意义。于是,我们仍然选择用一个叠加态,加一个H门,看看对解决问题有没有帮助。

        而且我们也知道,两个H门加在一起,就会变成一根线:啥也不是。于是我们再添加一个H门,把电路的量子态变简单一点。

        

 改造的结果如上图,我们还是分析三个位置的量子态。

位置量子态
\psi _{1}\frac{|0>+|1>}{\sqrt{2}} \otimes \frac{|0>+|1>}{\sqrt{2}}
\psi _{2}\frac{|0\oplus f(x)>+|1\oplus f(x)>}{\sqrt{2}} \otimes \frac{|0>+|1>}{\sqrt{2}}
\psi _{3}\frac{|f(x)>+|\overline{f(x)}>}{\sqrt{2}} \otimes |0>

        其中x为0或者1,如此一来,确实能产生差别,当为常函数的时候,高位为|+>态,而为平衡函数的时候高位为一个纯态,可以通过检测高位|0>与|1>的百分比,就能知道这到底是什么函数。(常函数各为50%,平衡函数二者中一个为100%另一个为0%)。

        虽然我们已经能够判断出来了,但这还不是真正的Deutsch算法,真正的Deutsch算法电路如下图,仅仅只有|0>与|1>之差:

 但是这个改变却能让算法更快,请大家仔细观察下面这个式子,最后一步进行规整。

 我们分别分析一下\psi _{1}\psi _{2}以及\psi _{3}的状态:

位置状态
\psi _{1}\frac{|0>-|1>}{\sqrt{2}}\otimes \frac{|0>+|1>}{\sqrt{2}}
\psi _{2}自己算,见下面的分析
\psi _{3}自己算

最后的差别,就体现在了这一个0与1上边。在\psi _{2}状态下,如果低位为|0>,那么高位为\frac{|f(0)>-|\overline{f(0)}>}{\sqrt{2}};如果低位为|1>,那么高位为\frac{|f(1)>-|\overline{f(1)}>}{\sqrt{2}}。如果为常函数的话,低位|0>时高位为(-1)^{f(0)}|\, ->,低位为|1>时高位为(-1)^{f(1)}|\, ->,综合一下,状态为\frac{|0>-|1>}{\sqrt{2}} \otimes \frac{|0>+|1>}{\sqrt{2}},如果为平衡函数的话状态为\frac{|0>-|1>}{\sqrt{2}} \otimes \frac{|0>-|1>}{\sqrt{2}},到\psi _{3}位置时,低位的\frac{|0>+|1>}{\sqrt{2}}又会转化为|0>态,而\frac{|0>-|1>}{\sqrt{2}}会转化为|1>态差异就会产生在低位。

        是不是觉得很混乱,小编换一种方式来讲。

        在\psi _{1}状态下\frac{|0>-|1>}{\sqrt{2}}\otimes \frac{|0>+|1>}{\sqrt{2}}=\frac{1}{2} (|00>-|10>+|01>-|11>),对吧?

        而低位又会控制高位,即|00>在经过Uf后会变为|(0\oplusf(0)) ,0>,同理|10>会变为|(1\oplusf(0)) ,0>,

        |01>会变为|(0\oplusf(1)) ,1>,|11>会变为|(1\oplusf(1)) ,1>。而被|0>控制的结果就是它本身,被|1>控制的结果就是取反,对吧?

        所以我们又可以化简,即|00>在经过Uf后会变为|f(0) ,0>,同理|10>会变为|(\overline{f(0)} ,0>, |01>会变为|f(1) ,1>,|11>会变为|\overline{f(1)} ,1>。

        当f(0)=f(1)时,若均为0,则\psi _{2}位置与\psi _{1}位置一模一样,\psi _{3}的低位为|0>

        若均未1,则\psi _{2}位置为\frac{1}{2} (|10>-|00>+|11>-|01>),则\psi _{3}的低位为-|0>

        当f(0)=1,f(1)=0时,\psi _{2}位置为\frac{1}{2} (|10>-|00>+|01>-|11>),则\psi _{3}的低位为-|1>

        当f(0)=0,f(1)=1时,\psi _{2}位置为\frac{1}{2} (|00>-|10>+|11>-|01>),则\psi _{3}的低位为|1>

综上所述,只要是常函数,高位检测出来的均为|0>,只要是平衡函数,高位检测出来的均为|1>

        好的,本期的量子算法课就到这里啦,感兴趣的小伙伴们请继续关注我!


http://www.kler.cn/a/1917.html

相关文章:

  • Java爬虫:速卖通(AliExpress)商品评论获取指南
  • 人工智能:人机交互和用户体验:相关学点、两者关系、未来趋势
  • 重温设计模式--命令模式
  • 开发手札:CameraRTS精准性优化
  • 多功能护照阅读器港澳通行证阅读机RS232串口主动输出协议,支持和单片机/Linux对接使用
  • (Z Shell)zsh: no matches found: ? 使用单引号包裹
  • centos yum安装英伟达显卡驱动
  • Intel I210网卡
  • 分享5款让你工作事半功倍的软件
  • C语言数据结构初阶(7)----队列
  • HBase高手之路4-Shell操作
  • 苹果发布无线充新专利,苹果Find My技术成为近几年苹果的重要创新
  • PCIE时钟解说
  • (数据结构)八大排序算法
  • 【绘图】比Matplotlib更强大:ProPlot
  • CLIP:一种基于视觉和语言相互关联的图像分类模型
  • 蓝桥杯刷题冲刺 | 倒计时20天
  • 数字图像处理 Delaunay三角剖分和Voronoi图
  • 从零实现深度学习框架——学习率调整策略介绍
  • 一文带你领略 WPA3-SAE 的 “安全感”
  • Java之链表(不带头结点,带头结点,迭代实现,递归实现)
  • 2023年 ZZU ACM 招新赛暨选拔赛题解
  • yolov8训练筷子点数数据集
  • 浏览器的组成部分
  • 2023美赛C题【分析思路+代码】
  • (只需五步)注册谷歌账号详细步骤,解决“此电话号码无法验证”问题