如何知道量子计算机是否已经完成了任何量子计算?

论智 2018-10-10 09:13 次阅读

Urmila Mahadev在研究生院学习了八年,最终独立解决了量子计算中最基本的问题之一:如何知道量子计算机是否已经完成了任何量子计算?

2017年春天,加州大学伯克利分校的博士研究生Urmila Mahadev突然发现自己成了他人眼中的倾佩对象。她解决了量子计算中的一个主要问题,结合之前发表的论文,她俨然已经成为学界一颗冉冉升起的新星。但28岁的她却放弃了毕业,甚至压根没有考虑过毕业。

这是她在伯克利研究生院求学的第七年——很久之前,大多数学生都已经不耐烦地毕业了。

Urmila Mahadev

早在五年前,她的目光就被一个与众不同的研究问题所吸引,Aaronson称之为“量子计算中你可以提出的最基本问题之一”,即:如果你要求量子计算机执行计算,那你该怎么判断它是否按指示执行了任务,甚至只是做了任何和量子计算有关的事?

现在这个问题即将远离学界。在过去的几年里,研究人员一直希望能把量子计算机用于科研,从研究黑洞周围的变化到大蛋白质折叠,量子计算带来的加速效果是指数级的。但是,一旦量子计算机真正执行了经典计算机无法做到的计算,那人类该怎么确保计算结果的可信度?

如果我们不相信经典计算机的结果,我们可以从头开始一步步验证,但量子系统是从根本上就抵制这种检查的。首先,它们的内部工作非常复杂:即便只用几百个量子比特(或“量子位”)写下计算机内部状态的描述,那也需要一个比整个可见宇宙更大的硬盘。

其次,即便我们以某种方式记下这个描述,它也是难以理解的。量子计算机的内部状态通常是许多不同的非量子“经典”状态的叠加,如“薛定谔的猫”。但是,一旦你测量了一个量子态,它就会坍缩成这些经典状态中的一个。也就是说,当看着量子计算机里的300个量子比特时,我们基本上只能看到300个经典比特——0和1。

“量子计算机非常强大,但它也非常隐秘。”

考虑到这些限制因素,计算机科学家们长期以来一直想知道量子计算机是否能提供一些“铁证”,证明自己已经完成某些计算。这也是量子计算和古典计算进行“对话”的桥梁。Mahadev被这个问题迷住是在她读研究生的第二年,在之后的几年里,她一直反复尝试验证方法,而在无数挫折中,她也展现了自己持久的耐心和决心。

经过多年努力,现在她终于让学界见证了她的成功。10月7日,计算机科学顶会FOCS 2018在法国巴黎正式召开,这是理论计算机科学最大的会议之一。在会上,Mahadev带来了论文Classical Verification of Quantum Computations,她提出了一种交互式协议,用密码学为量子计算这批野马安上了“马鞍”。她的作品被授予会议“最佳论文”和“最佳学生论文”奖,这是理论计算机科学家难得的荣誉。

一条漫长的道路

Mahadev在洛杉矶的一个医生家庭长大,出于对成为医生的抵触心理,她在南加州大学求学期间听了RSA加密算法的创造者之一、计算机科学家Leonard Adleman教授的课程,并把专业改成了理论计算机科学。直到在向伯克利研究生院递交申请之前,量子计算于她都是最陌生、最不了解的事情。

但是,到了伯克利,一切就完全不同了。她的博士生导师Umesh Vazirani向她介绍了一个问题:找到一个验证量子计算的协议。这个问题彻底激发了她的学术热情。

有一个基础事实是,也许量子计算机可以解决经典计算机无法解决的问题,但它的解决方案不一定是难以验证的。比如分解大数字,这是个经典计算机无法计算而量子计算机可以高效解决的任务。虽然无法计算,可验证量子计算机的因子分解是否正确对经验计算机来说很容易——它只需要将这些因子相乘,看看它们是否能产生正确的答案。

然而,计算机科学家认为量子计算机可以解决的许多问题不具备上述特征。换句话说,经典计算机不仅无法解决它们,甚至也识别不了解决方案是否正确。鉴于此,2004年的时候,物理学家Daniel Gottesman把“量子验证”这个问题抛给学界。

问题提出的四年内,一些量子计算研究人员得到了部分答案。两个不同的团队证实确实存在一种能证明已经完成量子计算的方法,他们的一个关键想法是利用交互性证明,即给定一定的计算,使得设备(以下称为“证明者”)具有执行计算的能力,但是另一个实体(以下称为“验证者”)不具有。假设证明者是不受信任的,也可能会欺骗验证者,我们要找出一种方法,让验证者从证明者手中拿到高度可信的正确答案。

这个框架起源于20世纪90年代的复杂性理论。其中最简单的方法是验证者可以自己执行验证计算,直接检查证明者的结果。第二种方法是验证者无法执行计算,但证明者可以提供一个简短的“证据”,再由前者完全证明结果。交互式证明是一种协议,通过该协议,验证者可以和更强大但不可信的证明者进行交互。

在Mahadev的成果出现之前,学界通过引入交互式模型,允许验证者使用非常有限的量子计算机,在“量子验证”这个问题上取得了一定进展。简而言之,如果采用上述第一种方法,就是让验证者具备在它选择的两个可能的基础中准备单个量子比特的能力,一次一个,由它把量子比特发送给证明者;如果采用第二种方法,就是让验证者可以一次一个地从证明者处接收单个量子比特,并在它选择的两个基础之一中对它们进行验证。

一般情况下,这两种方法都能验证任意多项式时间量子计算,而其中的重点是验证者准备量子比特的能力,使证明者可以检测到“证据”与预先确定的“诚实行为”是否存在偏差。

但问题依然存在:十年了,对于量子计算机这个“证明者”,我们能否找到一个完全经典的“验证者”?

2012年,包括Vazirani在内的一组研究人员表明,如果一个量子计算机是由一对无法相互通信的量子计算机执行的,那么一个完全经典的验证器可以检查量子计算。虽然这篇论文只讨论了某种特定状态,但它给Mahadev带来了启发:是否能找到一个“无条件”的结果,一个不假设量子计算机能做什么或不做什么的结果。

进行了一段没有进展的研究后,这对师生把目光转向了密码学(各自研究不同的问题)。由于大规模量子计算机在未来可能会出现,密码学领域为了开发可抵抗量子攻击的密码架构,提出了一种名为“后量子密码学”的研究。2016年,他们和OpenAI的计算机科学家Paul Christiano达成合作,共同开发了一种利用密码学方法让量子计算机构建“secret state”(秘密状态,)的方法。

所谓秘密状态,就是一种已为人知的经典验证者,但它不是量子计算机本身。

他们的程序依赖于所谓的“trapdoor”函数——一个易于执行但难以反转的函数,除非你有加密密钥。这个函数需要“二对一”,也就是每个输出对应两个不同的输入。有了它,我们就能用“trapdoor”函数创建秘密状态——首先,要求计算机建立一个函数所有可能输入的叠加;其次,让计算机将该函数应用于此巨型叠加,创建一个新状态,该状态是函数的所有可能输出的叠加。这时输入和输出叠加将被纠缠,这意味着对其中一个进行验证会立即影响另一个。

这之后,我们就能要求计算机检查输出状态并汇报结果,它在检查时可以把输出状态折叠成一个可能的输出,由于输入输出是纠缠的,这时输入也会被折叠。

2017年,Mahadev解决的那个量子计算主要问题就是提出构建“trapdoor”函数的加密方法:Learning With Errors(LWE)。她本可以凭借这个成果毕业,但面对还没有解决的“量子验证”难题,她表示:

我从未想过毕业,因为我的目标从未毕业。

尘埃终落定

还是那个问题:是否存在一个完全经典的验证者。

从交互性证明到秘密状态,Mahadev已经试遍了所有方法,有一段时间,她甚至感到走投无路。但上天还是眷顾她的,一次,她突然萌生了一个新想法:研究人员已经证实,如果验证者能够检查量子比特,那么它也可以检查量子计算机。根据定义,经典验证者不具备这种能力,但是如果经典验证者能以某种方式迫使量子计算机自己执行检查并诚实地报告呢?

这个问题的难点是让量子计算机承诺在验证者检查之前,自己知道对方要测量的状态,Mahadev将其称为量子比特承诺问题。假设证明者声称准备了一个选择的单量子比特状态|φ>(验证者不知道),验证者向证明者询问执行|φ>测量的结果。无论是在计算基础上(Pauli Z的本征基础),还是在Hadamard基础上(Pauli X的本征基础),是否存在一种协议,保证在协议结束时,验证者能够产生与所选基础中的测量结果相匹配的结果?

这个新协议具有以下属性。首先,正如预期的那样,对于任何量子计算,都有一个量子证明者可以使经典验证者相信计算结果的正确性,此属性称为协议的完整性。其次,没有证据可以说服经典验证者接受错误的结果,此属性称为协议的健全性。在Mahadev的结果中,后者的属性有一个转折点:如果证明者不能破坏后量子加密(LWE),那么稳健性就会保持不变。

该协议对LWE的依赖使得Mahadev的成果具有双赢的风格。量子计算机愚弄协议的唯一方法是量子计算世界中能有人想出如何破解LWE。但目前,LWE被广泛认为是后量子密码学的主要候选者,它可能很快就会取代其他可能会被量子计算机破解的标准,被国家标准与技术研究所采用作为其新的加密标准。破解难度可想而知。

在未来几年内,Mahadev的协议暂时还不太可能被部署进真正的量子计算机中,因为协议所需算力太高了。根据专家推测,具体数字应该至少会是5年。但现如今的科学发展是日新月异的,曾经我们认为有些难题可能需要几十年才能解决,但它们纷纷只用一两年就搞定了。

随着量子计算机规模的扩大和协议的不断简化,相信我们会尽快看到这个理论成果落地的那一天。

热门推荐

原文标题:研究生解决量子验证:如何判断量子计算机是否已完成量子计算?

文章出处:【微信号:jqr_AI,微信公众号:论智】欢迎添加关注!文章转载请注明出处。

收藏 人收藏
分享:

评论

相关推荐

为什么量子计算在区块链平台中如此重要

在深入研究量子位、叠加和量子门之前,让我们先来看看当今计算机的内部工作原理。实质上,计算机芯片是由许....

发表于 12-18 13:34 18次 阅读
为什么量子计算在区块链平台中如此重要

量子计算如何恢复和保证数字货币交易的不可变性

量子计算并不是什么新事物,我们已经谈论它几十年了,但是我们现在正在见证这种技术从理论到实现的转变。量....

发表于 12-18 11:22 48次 阅读
量子计算如何恢复和保证数字货币交易的不可变性

量子计算机在人工智能研究领域中的巨大潜力

人工智能研究的突破依赖于更强大的计算机和更高效的算法,基于量子并行原理的量子计算机提供了一种与经典超....

的头像 新智元 发表于 12-16 09:52 345次 阅读
量子计算机在人工智能研究领域中的巨大潜力

微软凭什么赢得美国陆军的订单?这个订单于AR产业有什么启示意义?

苏波表示,十万台的订单对于VR/AR产业是一个标志性事件,也印证了他在2014年所作的判断:即革命性....

的头像 AR工业应用 发表于 12-11 16:53 1220次 阅读
微软凭什么赢得美国陆军的订单?这个订单于AR产业有什么启示意义?

千人计划专家张首晟去世,公司遭美报告点名

数据显示,丹华资本在区块链技术、区块链应用和数字货币领域共计投资事件金额达到约1.88亿元。张首晟看....

的头像 中国半导体论坛 发表于 12-11 10:13 1767次 阅读
千人计划专家张首晟去世,公司遭美报告点名

量子计算何时才能落地

美国方面称,它对这项复杂的技术何时真正大有用武之地毫无头绪。

的头像 人工智能学家 发表于 12-10 14:16 266次 阅读
量子计算何时才能落地

IT行业最基本的科学技术发展前景

今天人工智能要做的事情,整个人类所有计算的事情最终能转化为优化的问题,很多的可能性,我们要找到最佳的....

的头像 山东省物联网协会 发表于 12-10 09:41 472次 阅读
IT行业最基本的科学技术发展前景

美国国家科学院、工程院和医学院发布了关于量子计算前景的报告

委员会特别说明了在创造一个自我加强的技术进步周期——它通向商业应用,进而带来私营部门投资和进一步的技....

的头像 IEEE电气电子工程师学会 发表于 12-08 10:30 622次 阅读
美国国家科学院、工程院和医学院发布了关于量子计算前景的报告

量子计算机是否真的能瓦解区块链

在“击破论”支持者看来,量子计算机可能会对这两道安全防线产生巨大威胁。未来,量子计算机能很快破解哈希....

发表于 12-07 14:05 146次 阅读
量子计算机是否真的能瓦解区块链

量子加密技术竞争加剧 中国目前领先

据报道,高通拥有推动5G商用的独特优势,骁龙855移动平台、骁龙X50 5G调制解调器系列、以及集成....

的头像 澳门威尼斯人官网手机网 发表于 12-07 09:49 573次 阅读
量子加密技术竞争加剧 中国目前领先

Oxford HighQ有望实现量子计算技术元器件商业化

据麦姆斯咨询报道,诞生于牛津大学的一家初创公司Oxford HighQ有望实现量子计算技术元器件的商....

的头像 微流控 发表于 11-30 17:01 368次 阅读
Oxford HighQ有望实现量子计算技术元器件商业化

中国正在发展自己的机器人产业,中国博士毕业生不再需要出国“镀金”

陈国强表示,近年来,中国科学家的收入增长迅速,已经与美国同行的薪酬水平大致相同,有时甚至更高。在清华....

的头像 悟空智能科技 发表于 11-29 17:05 416次 阅读
中国正在发展自己的机器人产业,中国博士毕业生不再需要出国“镀金”

美国商务部针对关键新兴基础技术的出口管制框架意见

保护美国科技领先地位和战略性科技资源已经成为特朗普政府的重大国家安全关切之一,此次丰富出口管制名单是....

的头像 半导体观察IC 发表于 11-26 17:34 1109次 阅读
美国商务部针对关键新兴基础技术的出口管制框架意见

美方严厉管制先进技术出口?韩企很庆幸

压力山大的是韩国方面。半导体产业占其全部出口的2成左右,也是顺差的主要来源。而三星的主要利润也来自于....

的头像 半导体观察IC 发表于 11-26 17:31 1934次 阅读
美方严厉管制先进技术出口?韩企很庆幸

量子技术的发展将会给区块链带来漏洞

牛津大学实验物理学家Alexander Lvovsky告诉Gizmodo:“量子计算机对任何涉及公钥....

发表于 11-23 14:08 140次 阅读
量子技术的发展将会给区块链带来漏洞

一台量子计算机运行一套特殊算法开发出了首套能够运转的量子神经网络

IBM的Q Experience计算机是一种五量子位云端访问的量子系统,对于那些没有数百万美元资金投....

的头像 人工智能 发表于 11-23 09:44 490次 阅读
一台量子计算机运行一套特殊算法开发出了首套能够运转的量子神经网络

十年内量子计算机将能够破解区块链的密码

当信息变成资产时,数据安全、透明度和问责制就变得至关重要。区块链是一种安全的数字记录或分类账。它是由....

发表于 11-22 09:30 142次 阅读
十年内量子计算机将能够破解区块链的密码

美国限制14类技术出口清单,你想买的基本都买不到了

根据2018年国会通过的《出口管制改革法案(ExportControlReformAct)》要求,美....

发表于 11-19 16:45 5332次 阅读
 美国限制14类技术出口清单,你想买的基本都买不到了

量子计算机攒机指南

超导量子计算机,看起来不错,不仅理论体系成熟,而且Google和IBM都已经成功打造出不同量子比特(....

的头像 C114通信网 发表于 11-13 15:12 292次 阅读
量子计算机攒机指南

量子电脑的各种实现方法

最早发展的量子位元是捕获离子(trapped ion),是无线电频率陷阱捕获离子、用雷射控制离子集体....

的头像 DIGITIMES 发表于 11-09 11:14 868次 阅读
量子电脑的各种实现方法

美国国内目前对于量子计算人才的态度和政策趋势

当没有那么多人了解这项技术时,这是一个更大的问题。例如,在称为深度学习的人工智能中,据估计只有不到2....

的头像 将门创投 发表于 11-08 10:19 1224次 阅读
美国国内目前对于量子计算人才的态度和政策趋势

量子网络新突破:量子纠缠理论解决研发障碍

这种新型网络以量子纠缠理论为基础。由于量子纠缠对能够扰乱信号的环境干扰高度敏感,因此量子计算机的研发....

发表于 11-08 10:05 98次 阅读
量子网络新突破:量子纠缠理论解决研发障碍

美国Quantum Xchange公司正式推出了美国首个量子互联网

官网资料显示,Phio是美国第一个也是唯一一个量子安全网络。它将保证商业企业和政府机构能够无视距离并....

发表于 11-04 10:32 366次 阅读
美国Quantum Xchange公司正式推出了美国首个量子互联网

量子计算是什么

量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。对照于传统的通用计算机,其理论....

的头像 发烧友学院 发表于 11-04 10:23 1528次 阅读
量子计算是什么

量子计算研究人才或成下一个大缺口

初创公司Zapata Computing的创始人兼首席执行官克里斯托弗·萨瓦(Christopher....

的头像 人工智能学家 发表于 11-01 10:56 522次 阅读
量子计算研究人才或成下一个大缺口

一种基于人工智能算法的量子纠错系统

在玩这个量子围棋游戏时,玩家——让我们称她为Alice——做出的动作是为了保留代表某种量子态的模式。....

的头像 新智元 发表于 10-31 09:45 471次 阅读
一种基于人工智能算法的量子纠错系统

美国在AI和量子计算领域有落后的趋势

国会正在考虑一项法案,该法案将从2019年到2023年期间为量子研究拨款12.75亿美元。这项名为《....

的头像 新智元 发表于 10-26 10:21 1077次 阅读
美国在AI和量子计算领域有落后的趋势

Gartner发布2019年十大战略性技术,对中国而言将如何布局?

近日,知名咨询及分析机构Gartner发布了最新预测2019年十大战略技术,其中包括:自主化设备、增....

的头像 张康康 发表于 10-25 19:44 997次 阅读
Gartner发布2019年十大战略性技术,对中国而言将如何布局?

量子计算领域最基础的问题

这个问题可绝不仅仅是一个象牙塔学术问题。如果不能证明量子计算机的输出结果确实对应于用户指令,那么不管....

的头像 射频百花潭 发表于 10-25 16:43 851次 阅读
量子计算领域最基础的问题

量子计算是什么?如何把握时代新机遇?

通用量子计算机一旦实现,将对通信安全、导航、成像以及人工智能、生物制药、新材料研发等诸多领域产生颠覆....

的头像 全球技术地图 发表于 10-25 15:31 1138次 阅读
量子计算是什么?如何把握时代新机遇?

第五代通信和万物互联对微波毫米波集成电路的需求提出了全新的要求

这一技术基于量子二能级体系在共振微波场中的拉比振荡现象。量子二能级原子体系,在量子计算和量子精密测量....

的头像 微波射频网 发表于 10-25 10:14 816次 阅读
第五代通信和万物互联对微波毫米波集成电路的需求提出了全新的要求

一种基于人工智能算法的量子误差校正系统

在量子计算机中引入了辅助量子位,并将其定位在储存实际量子信息的量子位之间。通过监控这些辅助量子位,量....

的头像 人工智能快报 发表于 10-25 08:54 449次 阅读
一种基于人工智能算法的量子误差校正系统

量子计算领域一大突破,实现“量子霸权”又近了一步

经典电路在任何意义上都不必是几何局部的,并且可以访问从仅依赖于输入大小的任意概率分布中抽取的随机位元....

的头像 新智元 发表于 10-21 10:00 767次 阅读
量子计算领域一大突破,实现“量子霸权”又近了一步

Gartner公司列出了企业组织在2019年需要探究的几大战略性技术趋势

市场正在迅速从专业数据科学家必须与应用程序开发人员合作创建大多数人工智能增强型解决方案的模式,转变为....

的头像 智能制造 发表于 10-19 11:51 1652次 阅读
Gartner公司列出了企业组织在2019年需要探究的几大战略性技术趋势

重磅!Gartner 2019 年十大战略性技术趋势出炉

10月18日,Gartner公司今天列出了企业组织在2019年需要探究的几大战略性技术趋势。Gart....

发表于 10-19 09:10 1119次 阅读
重磅!Gartner 2019 年十大战略性技术趋势出炉

华为百度阿里科技巨头投重金扎堆研究量子计算

港媒称,量子计算领域近期异常热闹,中国各大科技企业都已进军量子计算领域。记者梳理发现,近日,华为发布....

发表于 10-18 17:42 557次 阅读
华为百度阿里科技巨头投重金扎堆研究量子计算

华为对计算的渴望不止两颗AI芯片

翁文康在华为全联接大会上发布的量子计算模拟器HiQ云服务平台,可用于量子电路的仿真和调测、量子算法的....

的头像 新智元 发表于 10-18 10:58 975次 阅读
华为对计算的渴望不止两颗AI芯片

探讨国内外量子信息技术的生态环境

近日,借中国科学院量子信息重点实验室-问天量子-泰克科技三方成立“量子信息联合创新平台”之际,专访了....

的头像 EETOP 发表于 10-17 17:05 1330次 阅读
探讨国内外量子信息技术的生态环境

新一代可验证安全区块链,可为客户提供有效、可靠的数据信息保护

据和信中欧金融科技研究院执行院长陈邦道介绍,当前,大数据应用对个人隐私和政企敏感数据的保护提出严峻挑....

发表于 10-17 15:44 215次 阅读
新一代可验证安全区块链,可为客户提供有效、可靠的数据信息保护

探索未来的量子计算模拟器与编程框架HiQ

面向未来,华为云在探索量子世界,以巨大的算力潜力、全新的算法视角,致敬未来,即AI与量子计算的结合。....

的头像 嵌入式资讯精选 发表于 10-17 10:30 550次 阅读
探索未来的量子计算模拟器与编程框架HiQ

华为在量子计算领域取得最新进展

量子计算模拟器HiQ云服务平台问世,平台包括HiQ量子计算模拟器与基于模拟器开发的HiQ量子编程框架....

的头像 EETOP 发表于 10-17 10:08 1256次 阅读
华为在量子计算领域取得最新进展

一起学习总书记关于人工智能的部分论述

未来10年,将是世界经济新旧动能转换的关键10年。人工智能、大数据、量子信息、生物技术等新一轮科技革....

的头像 中国人工智能学会 发表于 10-16 10:39 806次 阅读
一起学习总书记关于人工智能的部分论述

厄米拉·马哈德夫:怎么知道量子计算机是否做了量子计算呢?

Mahadev现在是伯克利大学的博士后研究员。近日,她在计算机科学基金会的年度研讨会——理论计算机领....

的头像 人工智能学家 发表于 10-15 16:14 599次 阅读
厄米拉·马哈德夫:怎么知道量子计算机是否做了量子计算呢?

防止中国超车,美国投入15亿美金发展量子计算

展望量子世代,其实美国是非常害怕中国跟欧洲国家的挑战,美国能源部今年九月宣布拿出2.18亿美元投入量....

的头像 章鹰 发表于 10-15 10:00 1741次 阅读
防止中国超车,美国投入15亿美金发展量子计算

高通被微软挖墙角 专注量子计算项目

外媒报道,正在致力于研发量子计算机的微软公司,已经从高通挖来了一批工程师,参与该项目的一款芯片开发。

的头像 半导体行业联盟 发表于 10-14 09:32 805次 阅读
高通被微软挖墙角 专注量子计算项目

微软挖角高通芯片工程师 目的打造量子计算机耐极寒的芯片

由于量子计算人才短缺,企业往往需要借助创业公司或者成熟芯片公司人才来加速发展,微软显然也在从这方面入....

的头像 章鹰 发表于 10-12 08:04 1932次 阅读
微软挖角高通芯片工程师 目的打造量子计算机耐极寒的芯片

伯克利研究生解决量子计算验证问题

量子计算研究人员不仅对Mahadev的协议所取得的成就感到高兴,更对她为解决这个问题所采取的全新方法....

的头像 新智元 发表于 10-11 09:53 529次 阅读
伯克利研究生解决量子计算验证问题

D-Wave首次向公众开放量子计算能力

学习如何在量子计算机上编程需要一些耗费时间。因为它的处理器不像我们用的传统电脑一样,你必须训练芯片来....

的头像 将门创投 发表于 10-10 09:50 462次 阅读
D-Wave首次向公众开放量子计算能力