登陆

极彩登录官方网站-量子计算机能够做什么?

admin 2019-05-24 234人围观 ,发现0个评论

作者:Marianne Freiberger

翻译:Nothing

审校:loulou

本文转自中科院物理所微信极彩登录官方网站-量子计算机能够做什么?大众号 。

重视 哆嗒数学网 每天取得更多数学趣文

假如你在新闻中看到有人成功制作出了量子核算机的话,你最好立刻冻住自己的信用卡。由于,当你在网上购物时,现在一切维护你的信用卡信息的办法将会在几秒钟内被量子核算机攻破。不光是你在银行内的信息,一切的加密信息在量子核算机面前都将被轻松破解。

网络安全依赖于一些很难处理的数学问题

关于量子核算机有许多耸人听闻的说法,可是量子核算机破解加密信息的超强才能是真的。现有的加密办法是根据那些用一般核算机无法快速处理的数学问题规划的,可是量子核算机能够简单攻破这种加密办法。那么量子核算机还有哪些显着强于一般核算机的技能?

破译暗码

虽然为了答复这个问题咱们进行了许多理论方面的预备,可是这个问题依旧很扎手。RSA算法,一种广泛被用于维护信息安全的算法,它运用核算机都很难快速完结的因数分化来进行加密。假如给你一个数字10,你立刻就能够告诉我它能够被分化为2和5两个素数的乘积,可是假如我给你的数字是62615533,你应该无法经过心算告诉我它是哪些素数的乘积。

这不能见怪于你的心算才能。一旦数字足够大,核算机也力不从心。“假如给出一个4000位的数字,即使是让现存的核算机运转和世界年纪相同长的时刻也无法将它分化成一系列素数的乘积,”剑桥大学的量子核算前驱Richard Jozsa说。

其实还有其他许多问题和分化数字具有相同的特征:咱们有许多能够处理它们的算法,可是跟着要处理的问题的难度的添加,所需算法的步数也越多。另一个闻名的问题是游览商问题,这个问题是说怎么让游览商拜访每个城市时所走的旅程最短:要拜访的城市越多,问题越杂乱。

杂乱性理论依照处理问题的步数的添加速度来对各种问题进行分类。假如步数的添加是指数型的,比方游览商问题,问题会变得十分扎手,由于指数型添加的添加速度会越来越快。当算法步数的添加跟着输入数字的添加体现成多项式方式时,咱们才以为这样的问题是可处理的:假如输入的巨细是n,解题所需的步数正比于n2,n3或许nk。虽然解题步数添加在咱们看来仍是很快(假定k=10),可是杂乱理论专家以为这种添加还算缓极彩登录官方网站-量子计算机能够做什么?慢。“步数添加体现为多项式的数学模型是可核算的,”Jozsa解释道,“假如步数添加不体现为多项式的方式,咱们以为这类问题在实践操作中极彩登录官方网站-量子计算机能够做什么?是无法处理的。”

因数分化被以为是不行处理的问题:没有人写出能够由咱们现在的核算机运转的多项式时刻(步数呈多项式型添加)算法。这正是量子核算能够大展威风之处。1994年数学家Peter Shor提出一种处理数字分化问题的量子算法,它不光是多项式时刻算法,而且k不大于3。这个算法运用数论的常识,将因数分化问题转化成一种在特定的数学函数中辨认周期形式的问题——形式辨认正是量子核算机所拿手的。

现在运用的其他加密算法也存在相似的问题,例如椭圆曲线加密算法(elliptic curve cryptograp美国老奶奶hy):量子核算机能够简单破解它们。

这看起来量子核算机有很大优势,但在这个领域内任何事情都是不确定的。“在杂乱性理论中,要证明给定的使命不能在多项式时刻内处理是出了名的难题,”Jozsa说,“这是一个为难的现实。”由于没人知道因数分化的多项式时刻算法,并不意味着这样一个等候咱们发现的算法不存在。“或许,下周或许就有一个聪明的数论专家把这样的算法找出来,” Jozsa说,“对量子核算来说,这有点败兴。”

杂乱性问题

杂乱性的等级

关于其他问题状况怎么样?在其他的比因数分化更难的问题中,量子核算的威力会超越经典核算吗?在答复这个问题之前咱们要清晰“更难”的意义,这把咱们引导到了杂乱性类(complexity classes)的分级这儿。首要介绍“简略的”问题,这类问题具有可在经典核算机上运转的多项式时刻算法,这类问题组成了一个被称为P的类。接下来是咱们没有找到多项式时刻算法的问题,但咱们能够在多项式时刻内来查验解的正确性。这类问题被称为NP问题。因数分化正是归于这类问题。

在NP类问题中,有一些问题特别难解——这些问题被称为NP彻底问题(NP-complete),游览商问题归于这类问题。比NP彻底问题愈加杂乱的问题这儿将不再介绍。

因数分化被概括于NP类问题但不归于NP彻底问题。由于量子核算能够在因数分化问题中打败经典核算,接下来的问题是,当触及NP彻底问题时,量子核算机体现怎么?有一种说法以为,量子核算机能够极彩登录官方网站-量子计算机能够做什么?在眨眼之间处理NP彻底问题。但这种说法过于达观了。“咱们不知道咱们是否能够用量子核算机处理NP彻底问题,现实上,咱们以为量子核算机做不到这一点,”Jozsa解释道。

P和NP问题是相同杂乱的问题吗?

在这儿,咱们应该认识到杂乱性理论的核心问题:极彩登录官方网站-量子计算机能够做什么?一切咱们说到的东西都不能被证明。咱们不只不知道量子核算机能否有效地处理NP彻底问题,乃至不知道一般核算机能否有效地处理这些问题。正如或许存在一个能够处理因数分化问题但尚未被发现的多项式时刻算法相同,也或许存在处理其他NP问题或NP彻底问题的多项式时刻算法。假如咱们找到了这些算法,那么咱们的杂乱性类层次的结构将会溃散:P类、NP类和NP彻底类将会归于同一类。假如你能证明或否定P类问题等价于NP类问题,那就厉害了,克莱数学研究所都会奖赏你一百万美元:它被以为是数学中最风趣的七个敞开问题之一。

量子核算时机做什么?

假如理论不是建立在坚实的基础上,那么咱们怎样保证量子核算能够有实践用途呢?P问题在理论上是“简单”处理的,可是你依然需求花费许多时刻去处理它。这时量子核算机能够协助咱们吗?

答案是必定的。一个比如是“难如登天”问题,它指的是从巨大无规则的数据库中找到特定的信息。试想,从包括n个条目的电话号码簿中查找一个特定的号码而不是一个特定的姓名。这是一个需求耗费许多时刻的使命,由于号码是无规则的,它不像姓名相同是按规则摆放的。经典核算机除了一个一个的检索号码之外没有其他办法,最坏的状况是,咱们发现电话号码簿中底子不存在咱们要找的号码,或许这个号码处于最终一个方位,这样就需求进行n次操作。而量子核算机只需求n0.5次操作。这看起来并没有提速多少,可是当n足够大时,提速是相当可观的:以n=1000000为例,经典核算机需求进行一百万次操作而量子核算机仅需求进行1000次操作。

分子由许多遵从量子规则的粒子组成

另一个量子核算机能够大展身手的领域是化学领域,生物和制药领域。假如你想了解一个分子体系,例如为了规划一种新药,一个正确的挑选就是在核算机上模仿它的行为。困难在于分子是由许多粒子组成的,而这些粒子悉数遵从量子力学的规则。咱们知道,跟着粒子数的添加,描绘分子体系所需的信息量呈指数添加,这使得核算变得反常困难。“它具有指数级的杂乱性,”Jozas说,“虽然是面临相对小的分子,最好的经典核算机在模仿分子的量子动力学性质时也显得力不从心,可是量子核算机能够担任这项作业。”

暗码学也会获益于量子核算机。例如,当量子态被观测时就会发作塌缩,运用这种性质能够监测信息是否被其他人盗取。运用这种办法,人们能够给每个人分发量子秘钥——一串能够用于对信息加密和解密的字符串。假如有人截获了秘钥咱们立刻就能知道。“这种器材之所以存在,是由于它们只需求几个量子比特,因而这归于量子技能的领域。”Jozsa说。这种办法在2007年初次被用于公共实践,其时它被用来保证在瑞士日内瓦举办的推举中的选票安全搬运。或许从理论的视点咱们很难说量子核算机具有什么优势,可是至少咱们知道损坏咱们的加密办法是要支付一些价值的。

原文地址:

https://plus.maths.org/content/what-can-quantum-computers-do

重视 哆嗒数学网 每天取得更多数学趣文

声明:该文观念仅代表作者自己,搜狐号系信息发布渠道,搜狐仅供给信息存储空间服务。
  • 重磅不断!欧洲央行开闸放水 降息重启量化宽松 人民币一度飚涨逾500点!美联储跟不跟?
  • 极彩登录官方网站-多头孤立无援!精炼油大增抵消原油库存骤降 美伊或化解僵局
  •   ①全球经济紧张局势副作用对欧元的冲击可能超过美元

      

  • 欧元兑美元或许还要再跌一波 背面有哪四大原因?

    2019-09-15
    请关注微信公众号
    微信二维码
    不容错过
    Powered By Z-BlogPHP