团购网站推广怎么做,广州网站建设兼职,太原软件开发公司有哪些,免费静态网页模板下载来源#xff1a;原理Urmila Mahadev#xff08;厄米拉马哈德夫#xff09;花了八年时间在研究生院解决了量子计算领域最基本的问题之一#xff1a;怎么知道量子计算机是否做了量子计算呢#xff1f;2017年春天#xff0c;Urmila Mahadev发现自己处于大多数研究生都会认为… 来源原理Urmila Mahadev厄米拉·马哈德夫花了八年时间在研究生院解决了量子计算领域最基本的问题之一怎么知道量子计算机是否做了量子计算呢2017年春天Urmila Mahadev发现自己处于大多数研究生都会认为相当不错的一个位置。她刚刚解决了量子计算领域的一个主要问题。量子计算是研究计算机的科学它从量子物理学的奇怪定律中获得强大的计算力。德州大学奥斯汀分校的计算机科学家Scott Aaronson认为Mahadev关于“盲计算”的新成果与她之前的论文结合起来显然让她成为“一颗冉冉升起的新星”当时28岁的Mahadev已经在加州大学伯克利分校读了七年研究生——远远超过了大多数学生迫切想要毕业的阶段。现在正如她的博士导师Umesh Vazirani所说的她终于有了一篇“非常漂亮的博士论文”。但是那一年Mahadev并没有毕业她甚至没有考虑要毕业因为事情还没有完成呢。量子计算密码学在五年多的时间里她还有另一个不同的研究目标。她想解决的这个问题被Aaronson称为“量子计算领域最基本的问题之一”那就是如果让一台量子计算机做计算怎么知道它是否真的遵循了你的指令或者它是否真的执行了任何量子计算呢研究人员希望过不了许多年量子计算机就能指数级地加速为我们解答许多问题比如模拟黑洞周围的行为、蛋白质如何折叠等等。但是一旦量子计算机能够完成经典计算机无法完成的计算我们将如何知道它的计算是否正确呢如果你不信任一台普通的计算机理论上你可以亲自检查它的每一个计算步骤。但是量子系统从根本上抵制这种检查。首先量子计算机的内部工作机制极其复杂对于几百个量子比特的计算机要写出关于其内部状态的描述将需要比整个可见宇宙还要大的一个硬盘。此外即使有足够的空间写下这个描述也没有办法得到它。通常量子计算机的内部状态是许多不同的非量子的“经典”态的叠加。就像是薛定谔的猫同时处于“死”和“活”的状态但是一旦测量一个量子态它就会坍缩为其中一个经典态。凝视一台300个量子比特的量子计算机本质上你看到的只会是300个经典比特也就是0和1。Vazirani说“量子计算机非常强大但是也非常神秘。”考虑到这些限制长久以来计算机科学家一直好奇是否有可能让量子计算机提供任何严格的保证证明它确实做了自己宣称的事情。耶路撒冷希伯来大学的计算机科学家Dorit Aharonov问道“量子和经典世界之间的相互作用是否足够强大以至于能够进行对话呢”在研究生二年级的时候Mahadev被这个问题迷住了其中的原因连她自己都不完全明白。在随后的几年里她尝试了一种又一种方法。她说“有很多次我觉得自己做着正确的事情但是接着就出错了有时很快有时过了一年才出现。”但是Mahadev拒绝放弃。她表现出了Vazirani从未见过的持久的决心Vazirani说“从这个意义上说Mahadev绝对是与众不同的。”现在经过八年的研究生学习Mahadev终于成功了她提出了一种交互式协议通过这种协议没有量子计算能力的用户也可以使用经典的密码学让量子计算机做任何他们想做的事情并确信量子计算机正在遵循他们的命令就像是牵着马具任意驰骋一样。Vazirani说Mahadev的方法给用户提供了“让计算机无法摆脱的手段“。○ Mahadev提出的协议。 | 图片来源https://arxiv.org/pdf/1804.01082.pdfAaronson说一个研究生能够独自完成这样一个任务”非常令人震惊“。Mahadev现在是伯克利大学的博士后研究员。近日她在计算机科学基金会的年度研讨会——理论计算机领域最大型的会议之一——上提交了自己的方案。她的作品获得了这次会议的”最佳论文“和”最佳学生论文“奖这对一位理论计算机科学家来说是罕见的荣誉。加州理工学院的计算机科学家Thomas Vidick过去曾与Mahadev合作过他在博客文章中写道Mahadev的研究成果是”近年来量子计算和理论计算机科学的交叉处出现的最杰出的思想之一“。量子计算领域的研究人员之所以兴奋不仅是因为Mahadev的协议能够解决问题还因为她为解决这个问题所采取的全新方法。Vidick写道在量子计算领域使用经典的密码学真的是非常新颖的想法”我希望在这些想法的基础上会继续产生更多成果。“漫长的证明之路Mahadev在洛杉矶的一个医生家庭长大她就读于南加州大学在那里她从一个研究领域漂流到另一个。起初她只确信一点那就是自己不想成为一名医生。后来计算机科学家Leonard Adleman——RSA加密算法的三位创造者中的A——讲授的一门课程让她对理论计算机科学产生了兴趣。之后她申请成为加州大学伯克利分校的研究生并在申请材料中解释说自己对理论计算机科学的所有方面都感兴趣除了量子计算。因为量子计算“听起来像是非常古怪的事情是我知道得最少的事情”。然而一到伯克利Vazirani深入浅出的解释很快改变了她的想法。他向她介绍了一个问题——如何找到一个验证量子计算的协议而这个问题“激发了她的想象力”Vazirani说道。Mahadev解释说“协议就像是谜题。对我来说这种问题似乎比其他问题更容易因为你可以自己立即开始思考协议然后破解它们这样你就会发现它们是如何运作的。” 她选择这个问题作为自己的博士研究课题开始了Vazirani所说的“漫漫长路”。○ Urmila Mahadev。 | 图片来源Quanta Magazine如果一台量子计算机可以解决经典计算机无法解决的问题那并不必然意味着解决方案将难以检验。以大数的因数分解为例一台大型量子计算机可以高效解决这个问题但经典计算机被认为无法完成这个任务。虽然一个经典计算机不能对一个大的数字进行因数分解但它却能够检验量子计算机的因数分解是否正确——只需要将这些因数相乘看看它们是否得出正确答案。然而计算机科学家相信并且最近已经向证明迈出了一步量子计算机能够解决的许多问题并没有这个特性。也就是说一台经典计算机不仅不能解决这些问题甚至也不能判断一个提出的解决方案是否正确。鉴于这一点大约在2004年圆周理论物理研究所的物理学家Daniel Gottesman提出一个问题是否有可能提出任何一种协议通过这个协议一台量子计算机可以向非量子观察者证明自己确实完成了声称的那些事情在四年内量子计算的研究人员已经得到了部分答案。两个不同的团队证明一台量子计算机有可能证明它的计算但是不是向一台纯粹经典的验证设备而是向一个能够进入自己内部非常小的量子计算机的验证设备。研究人员后来改进了这种方法并证明验证设备所需要的只是每一次测量单个量子比特的能力。2012年包括Vazirani在内的一组研究人员证明如果量子计算是由一对无法相互通信的量子计算机进行的那么一台完全经典的验证设备就能够检查量子计算。Gottesman表示那篇论文的方法是针对这种特定情形设计的这个问题似乎陷入了死胡同一些人认为不能再往前走了。大约就在这个时候Mahadev遇到了这个验证问题。起初她试图得到一个“无条件”的结果一个并不假定量子计算机能做什么或不能做什么的结果。在她研究这个问题一段时间且并没有取得任何进展后Vazirani建议了一种不同的可能性——用“后量子”加密post-quantum cryptography。研究人员认为这是一种即使量子计算机也无法破解的加密方法虽然他们还不确定。像RSA加密算法之类用于加密在线交易等信息的方法不是后量子的也就是说一台量子计算机能够破解这种加密方法因为它们的安全性取决于对大数做因数分解的难度。2016年Mahadev和Vazirani在解决另一个问题的时候取得了进展这在后来被证明是至关重要的。他们与如今在OpenAI公司工作的计算机科学家Paul Christiano合作开发了一种方法使用密码学让量子计算机构建所谓的“加密态secret state”这个加密态的描述对于经典的验证设备是已知的但是对于量子计算机本身却是未知的。他们的程序依赖于所谓的“暗门”函数trapdoor function这个函数很容易执行但是要逆转则非常困难除非知道密钥。研究人员还不知道如何真正构建一个合适的暗门函数之后将会提出。另外还要求这个函数是“二对应一”的这意味着每一个输出对应着两个不同的输入。比如说对于平方函数yx²除了数字0之外的每一个输出例如9都有两个对应的输入3和−3。有了这样一个函数就可以让量子计算机按照下面的步骤构建一个加密态首先让计算机构建一个所有可能的函数输入的叠加这听起来或许很复杂但是事实上很容易然后让计算机将函数应用到这个巨大的叠加上函数的所有可能输出的叠加构成一个新的态。输入的叠加和输出的叠加会产生纠缠这意味着测量其中一个会立即影响另一个。接下来要求计算机测量输出态并告诉我们结果。这个测量会导致输出态坍缩为所有可能输出中的一个而输入态也会立即坍缩以与之匹配因为它们彼此纠缠。例如对于平方方程如果测量得到的输出态是9那么输入态会坍缩为3和−3的叠加态。但是如果使用的是暗门函数那么我们就有暗门的秘钥因此可以很容易地找出构成输入态的两种叠加态。然而量子计算机不能。量子计算机不能简单地测量输入的叠加来求出它的构成因为测量会进一步让输入的叠加坍缩让计算机只剩下其中一个输入态而无法求出另一个。2017年Mahadev使用一种名为“错误学习Learning With ErrorsLWE”的加密技术找到了在加密态方法的核心构建暗门函数的方法。利用暗门函数她就能够创建一个量子版本的“盲”计算使得云计算用户可以屏蔽他们的数据这样云计算机即使在计算时也无法读取数据。不久之后Mahadev、Vazirani 、Christiano与Vidick、Zvika Brakerski以色列魏茨曼科学研究所的科学家合作进一步改进这些暗门函数利用加密态方法发展出一种让量子计算机产生可证实的真随机数的安全方法。Mahadev 本可以凭借这些结果毕业但她决心继续工作直到解决验证问题。她说“我从来没有想毕业的事情因为我的目标从来就不是毕业。”不知道能否解决这个问题有时会让人感到压力但是她说“我花时间学习自己感兴趣的东西因此这也就不是真的在浪费时间。”如何加密Mahadev尝试了各种方法试图从加密态方法抵达一种验证协议但是有一段时间她一无所获。然后她有了一个想法研究人员已经证明如果验证设备能够测量量子比特它就能够检验量子计算机。根据定义一个经典的验证设备缺乏这种能力。但是如果这个经典的验证设备能够以某种方式强迫量子计算机自己进行测量然后诚实地报告测量结果呢Mahadev意识到最棘手的部分是在量子计算机知道验证设备会要求哪种测量之前就让量子计算机确定它将要测量的状态。否则量子计算机很容易欺骗验证设备。这正是加密态方法发挥作用的地方Mahadev的协议要求量子计算机首先创建一个加密态然后将它与应该测量的状态纠缠在一起。只有到那时计算机才会知道要进行何种测量。由于量子计算机不知道加密态的构成但验证设备知道Mahadev证明量子计算机不可能在不留下明显的欺骗痕迹的情况下做出严重的欺骗。Vidick写道本质上计算机要测量的量子比特被“设置为密码石”。正因为如此如果测量结果看起来像是一个正确的证明验证设备就能确信它们真的是。“真是个好主意每一次Urmila解释它的时候我都惊呆了。”量子计算机不能破解的密码Mahadev的验证协议连同随机数生成器和盲加密方法都取决于量子计算机不能破解LWE的假设。目前LWE被广泛认为是后量子密码学的优先候选对象而且它或许很快会被美国国家标准与技术研究所NIST采用作为其新的加密标准取代那些量子计算机可能破解的方法。Gottesman警告说这并不能确保这种加密方法真的能抵御量子计算机“但是到目前为止这种方法是可靠的还没有人找到证据证明这种方法有可能被破解。”Vidick写道无论如何协议对LWE的依赖给Mahadev的作品带来了双赢的意味。量子计算机可能欺骗协议的唯一方法是量子计算领域的某个人找到了破解LWE的方法而这本身将会是一项了不起的成就。Mahadev的协议不太可能在不久的将来就在真正的量子计算机上实现。目前这个协议需要太多的计算能力因而不太有实用性。但在未来几年随着量子计算机越来越大以及研究人员对协议进行简化情况可能会改变。Aaronson说Mahadev的协议可能在未来五年内都没有可行性但是“在假想世界里也不是完全不可行。如果一切顺利在量子计算机演化的下一个阶段就可以开始思考这个问题。“考虑到这个领域现在的发展速度有多快这个阶段可能会更早到来。Vidick说毕竟就在五年前研究人员还认为量子计算机要想解决经典计算机无法解决的任意问题还需要很多年。现在人们认为这将在一两年内发生。至于Mahadev解决了自己最喜欢的问题让她有点茫然。她希望自己能明白是什么让这个问题适合自己去研究。“我现在必须找到一个新问题所以很希望能知道这个答案。”然而理论计算机科学家更多地是将Mahadev统一量子计算与密码学一事视为对那些丰富多彩的思想脉络的初步探索而不是故事的结束。原文链接https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/未来智能实验室是人工智能学家与科学院相关机构联合成立的人工智能互联网和脑科学交叉研究机构。未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
