量子那些事儿 关注
手机版

量子计算的理论发展(三)

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

量子计算的理论发展(三)

雪花又一年 2018-05-17 15:23:19 浏览233 评论0

摘要: 今天介绍几种重要的量子算法。 在量子计算的物理实现方面,最重要的莫过于DJ算法,因为它能非常简单地证明量子计算的加速能力。 在应用前景方面,莫过于可以破解RSA公钥体系的Shor算法,和可以解决大部分问题的Grover搜索算法。

今天介绍几种重要的量子算法。

在量子计算的物理实现方面,最重要的莫过于DJ算法,因为它能非常简单地证明量子计算的加速能力。

在应用前景方面,莫过于可以破解RSA公钥体系的Shor算法,和可以解决大部分问题的Grover搜索算法。

所以接下来我们主要关注这三种算法。

一、DJ算法

全称是Deutsch-Jozsa算法,它解决的是这样一个问题:

一个函数f: \left\{ 0, 1 \right\}^n\rightarrow \left\{ 0, 1 \right\},已知它要么是常数函数要么是平衡函数,通过某种算法来确定f是何种类型的函数。

经典算法做多次访问,若做k次访问,输出结果不完全相同,则必为平衡函数;若做k次访问,输出结果都相同,则可能为常数函数。要想做出准确的判断,这个k必须超过2^(n-1),这个算法的复杂度是随着n的增大而指数增多的

但是采用DJ算法,只需要一步就可以判断是常数函数还是平衡函数,其逻辑门操作如图:

jylNRFMWkKGOhKBaIXnnsFYVpoh9FQd7XdlrfGd4

过程如下:

先对输入的n个比特|0>和辅助比特|1>作Hadamard变换,然后经过Uf变换,再对输出比特(不包括辅助比特)进行Hadamard变换即可得到一个可以判断是常数函数还是平衡函数的等式。

第一步Hadamard变换将输入的|0>^{\otimes n}|1>转换为

ABqPLTF0Cd3ZAAAAAElFTkSuQmCC

Hadamard变换实际上是将|0>转换为\frac{1}{\sqrt{2}} \left(  |0>+|1> \right),将|1>转换为\frac{1}{\sqrt{2}} \left(  |0>-|1> \right),多个比特的时候有如下公式:

BIkDCYfiFgiJB+03NjZaa0RwXvtLEyEeHh4eHh4r

然后进行Uf变换,这其中Uf起到了决定性作用,它常被称为是quantum oracle,它进行了如下转换|x>|y>\rightarrow|x>|y\oplus f(x)>,得到

RbU3dteKxnwAAAABJRU5ErkJggg==

因为f(x)要么是0要么是1,所以上式可以改写为

wfPlK0r2QLhWgAAAABJRU5ErkJggg==

再只对输入比特作Hadamard变换,

qiBisn8AAAAASUVORK5CYII=

然后我们以|0>^{\otimes n}为基进行测量,落到这个基上的概率是

wPSzK2X5k5zyAAAAABJRU5ErkJggg==

如果f(x)是常数函数,这个概率就是1;如果是平衡函数,这个概率就是0.

也就是说对于最后的测量,如果落在|0>^{\otimes n}上,就是常数函数;如果不落在|0>^{\otimes n}上,就是平衡函数,实现了一步解决问题,说明了量子计算相对于经典计算的强大之处。

打字蛮累的,今天就先写到这里,大家能对量子计算的威力有个印象~



原文发布时间为:2017.02.01
本文作者:Golden Horqin
本文来源:知乎,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注29
关注
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
阿里云流计算(Aliyun StreamCompute)是运行在阿里云平台上的流式大数据分析... 查看详情
提供一种性能卓越、稳定、安全、便捷的计算服务,帮助您快速构建处理能力出色的应用,解放计算给服... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云9.10会员日

阿里云9.10会员日