央视网|中国网络电视台|网站地图
客服设为首页
登录

中国网络电视台 > 经济台 > 资讯 >

交互式证明在量子级别上仍然存在

发布时间:2012年08月02日 03:44 | 进入复兴论坛 | 来源:科技日报 | 手机看视频


评分
意见反馈 意见反馈 顶 踩 收藏 收藏
channelId 1 1 1

  本报华盛顿7月31日电 (记者田学科)麻省理工学院(MIT)今天宣称,该校研究人员攻克了困扰理论计算机科学界十余年的难题:量子级别的交互式证明问题。

  理论计算机科学是计算机科学的一个分支,它主要研究有关计算的相对更抽象化、逻辑化和数学化的问题。交互式证明一直是理论计算机科学的主要研究论题之一,是现今广泛使用的密码学的基础。在传统的交互式证明中,具有有限计算能力的发问者只从一个强大的,但不可靠的应答者那里提取可靠信息。

  计算机科学家在20年前就已经揭示,在交互式证明中,如果提问者能够对多个无所不知的应答者(简称为“多证人”)提出质疑,那么,它会比从单一的应答者(简称为“单一证人”)那里提取更多有效的信息。多证人证明与单一证人相比之所以更为有效,是因为没有应答者知道被其他答案所施加的限制,因此,如果任何应答者企图欺骗的话,会比较容易产生矛盾。然而,在量子计算变得较为普遍之后,计算机科学家开始探讨这种多证人系统在量子级别上是否仍然正常工作,因为在量子级别上,物理粒子之间发生相互缠绕,意味着应答者的量子特性会表现出相互依赖性。

  MIT计算机科学与人工智能实验室博士后托马斯·维迪克和普林斯顿NEC实验室的伊藤设计出一个实验方案,企图通过掩饰提问者意图使应答者造假困难。为显示这种运作过程,研究人员设计出一个图案,在图上可以把问题所对应的答案用一些感觉点绘制出来。假如提问者对两个答案都感兴趣,那么在图上就绘出两个点。然而,提问者所感兴趣的问题不是二个,而是至少三个不同的问题。如果应答者对这些问题的反应点归为一条直线,那么,提问者所关心的答案也是如此;如果答案没有归为一条直线,那么可以认为至少有一个应答者在试图撒谎。

  为此,研究人员认为,在量子级别上阻挡纠缠应答者的多证人交互式证明是存在的。这对于解码者来说是好消息,而对于量子物理学家来说则是坏消息,因为它证明没有一个简单的办法,来设计出一个可以阐明经典物理学与传统物理学之间区别的实验。

  在交互式证明中,提问者提出一系列问题,每一个问题都对下一个问题可能的答案范围进行了限制。提问者自己没有权利计算有效的答案,但它却有权利决定每一个新答案是否符合前面提出的限制。足够的提问之后,提问者或者揭示出矛盾,或者将被应答者欺骗的可能性降低为零。

  “这是一个基本思路,除非你以更高维的方式去做。”维迪克说,“不是用二维,而是用N维,并且思考作为一个小的N维体的所有问题和答案。”

  按照超量子力学的自然法则,如果没有在量子尺寸上得到测定,那么被测定的性能就没有确定的价值。问题是当粒子被纠缠在一起时,它们的概率分布不能分开测定:它们实际上属于一个大分布的一部分,但任何对此分布的数学描述都假设了一个鸟眼透视,在多证人证明中没有一个应答者愿意有这种透视。

  维迪克称,他与伊藤费时一年半完成了该课题,研究成果将在今年10月举行的IEEE计算机科学基础大会上公布。

热词:

  • 量子计算
  • 证人
  • 研究人员
  • 计算机科学家
  • 粒子
  • 理论计算机科学
  • MIT
  • 计算能力
  • 数学化
  • 实验方案
  •