科学计算机(科学计算机怎么开三次方根)

想象一下有人过来告诉你他们有一个神谕，这个神谕可以揭示宇宙的深层秘密。虽然你可能很感兴趣，但你很难相信它。你想要一些方法来验证oracle告诉你的是真的。

这是计算机科学中的一个核心问题的关键。有些问题在任何合理的时间内都难以解决。但他们的解决方案很容易检查。鉴于此，计算机科学家想知道：问题有多复杂，同时还有可以验证的解决方案？

事实证明，答案是：几乎难以想象的复杂。

在4月发布的一篇论文中，两位计算机科学家大大增加了难以解决但易于验证的问题。他们描述了一种方法，可以检查几乎难以理解的复杂问题的答案。看起来很疯狂， 加州理工学院的计算机科学家托马斯维迪克说，他没有参与这项新工作。

该研究适用于量子计算机 - 根据量子力学的非直观规则进行计算的计算机。量子计算机现在几乎不存在，但有可能在未来彻底改变计算。

新的工作本质上使我们能够利用这个强大的神谕。即使oracle承诺告诉你远远超出你自己解决能力的问题的答案，仍然有办法确保oracle说实话。

直到宇宙的尽头

当问题难以解决但易于验证时，找到解决方案需要很长时间，但验证给定解决方案是否正确则不然。

例如，想象某人给你一个图表 - 一个由线（边）连接的点（顶点）的集合。此人会询问您是否可以仅使用三种颜色为图形的顶点着色，这样任何连接的顶点都不会具有相同的颜色。

在三色图中，每个顶点都是三种颜色中的一种，并且没有连接的顶点共享相同的颜色。这种三色问题很难解决。通常，找到图形的三个着色（或确定不存在图形）所花费的时间随着图形的大小增加而呈指数增长。例如，如果找到具有20个顶点的图形的解决方案需要3 20纳秒 - 总共几秒 - 具有60个顶点的图形将花费大约3 60纳秒，或者大约是宇宙年龄的100倍。

但是，让我们说有人声称有三色图表。不用花很长时间就可以检查他们的说法是否属实。你只需逐个检查顶点，检查它们的连接。随着图形变大，执行此操作所需的时间会缓慢增加，即所谓的多项式时间。因此，计算机不需要花费更长的时间来检查具有60个顶点的图形的三色，而不是检查具有20个顶点的图形。

这很容易，给予适当的三色，以确认其工作，说： 约翰·怀特，在麻省理工学院的物理学家与谁写的新纸张沿阿南德纳塔拉加州理工学院。

在20世纪70年代，计算机科学家定义了一类易于验证的问题，即使有些问题很难解决。对于非确定性多项式时间，他们将类称为NP。从那以后，NP一直是计算机科学中研究最深入的一类问题。特别是，计算机科学家想知道这个类是如何改变的，因为你给验证者新的方法来检查解决方案的真实性。

正确的问题

在Natarajan和Wright的工作之前，验证能力有两个大的飞跃。

要理解第一次飞跃，想象一下你是色盲。有人在你面前的桌子上放了两个方块，询问这些方块是相同还是不同的颜色。这对你来说是不可能完成的任务。此外，您无法验证其他人的解决方案。

但是你被允许审问这个我们称之为证明者的人。让我们说证明者告诉你这两个块是不同的颜色。您将一个块指定为块A，将另一个块指定为块B。然后将块放在背后并随机切换哪个手握住哪个块。然后你揭示块并要求证明者识别块A.

如果块是不同的颜色，这可能不是一个更简单的测验。证明者将知道块A是红色块，并且每次都会正确识别它。

但是如果这些块实际上是相同的颜色 - 这意味着证明者说它们是不同颜色的错误 - 证明者只能猜测哪个块是哪个。因此，只有50％的时间，证明者才能识别A组。通过反复探测有关解决方案的证明者，您将能够验证它是否正确。

Anand Natarajan（上）和John Wright在他们的新作中利用了量子力学。验证者可以发送证明者问题，赖特说，也许在谈话结束时，验证者可以更加确信。

1985年，三位计算机科学家证明，这种交互式证明可用于验证比NP问题更复杂的问题的解决方案。他们的工作为交互多项式时间创造了一类称为IP的新问题。用于验证两个块的着色的相同方法可用于验证更复杂问题的解决方案。

第二个重大进展发生在同一个十年。它遵循警方调查的逻辑。如果你有两个嫌犯，你认为犯了罪，你就不会一起质问他们。相反，你会在不同的房间里询问他们，并检查每个人对另一个人的答案。通过单独询问它们，你将能够揭示更多的真相，而不是只有一个嫌疑人要询问。

两个嫌疑人不可能形成某种分布式，一致的故事，因为他们根本不知道对方给出的答案是什么，赖特说。

他们留下了你可以采取另一步的可能性——Lance Fortnow

1988年，四位计算机科学家证明，如果你要求两台计算机分别解决同样的问题 - 并且你分别询问他们的答案 - 你可以验证一类比IP更大的问题：一个叫做MIP的类，用于多证明互动证明。

例如，通过多证明交互方法，可以验证一系列图形的三色，这些图形的大小比NP中的图形快得多。在NP中，图形大小以线性速率增加 - 顶点数量可能从1增加到2到3到4，依此类推 - 因此图形的大小绝不会与验证其三个大小所需的时间大不成比例-染色。但是在MIP中，图形中顶点的数量呈指数增长 - 从2 1到2 2到2 3到2 4，依此类推。

冰箱内壁结霜以后，阻碍了冰箱里的空气跟制冷管周围的冷空气的热量交换，所以制冷效果大打折扣，同时也会增加冰箱的运行负担，增加能耗。

因此，图形太大甚至不适合验证计算机的内存，因此它无法通过运行顶点列表来检查三色。但是仍然可以通过询问两个证明者分开但相关的问题来验证三种颜色。

在MIP中，验证程序具有足够的内存来运行程序，该程序允许它确定图中的两个顶点是否通过边连接。验证者然后可以要求每个证明者陈述两个连接顶点之一的颜色 - 并且它可以交叉引用证明者的答案以确保三个着色工作。

从NP到IP到MIP的难以解决但易于验证的问题的扩展涉及经典计算机。量子计算机的工作方式不同。几十年来，目前还不清楚他们如何改变这种情况 - 他们是否更难以更容易地验证解决方案？

Natarajan和Wright的新作品提供了答案。

量子秘籍

大家都知道在烈日下暴晒容易中暑，但是您知道吗？在空调房中久了也容易得“阴暑”。

量子计算机通过操纵量子比特或量子比特来执行计算。这些具有奇怪的特性，它们可以彼此纠缠。当两个量子比特 - 甚至是大型量子比特系统 - 被纠缠时，这意味着它们的物理特性以某种方式相互影响。

在他们的新作品中，Natarajan和Wright考虑了一个涉及两个独立的量子计算机的场景，这些量子计算机共享纠缠的量子比特。

这种设置似乎不利于验证。多证明者交互式证明的力量恰恰来自于您可以单独质疑两个证明者并交叉检查他们的答案。如果证明者的答案是一致的，那么他们可能是正确的。但是，两个分享纠缠状态的证明者似乎有更多的权力来持续断言不正确的答案。

事实上，当2003年首次提出两个纠缠量子计算机的情景时，计算机科学家认为纠缠会降低验证能力。包括我在内的每个人的明显反应是，现在你给予证明者更多的权力，维迪克说。他们可以利用纠缠来纠正他们的答案。

尽管最初的悲观情绪，维迪克花了几年时间试图证明相反的情况。2012年，他和Tsuyoshi Ito 证明，用纠缠量子计算机验证MIP中的所有问题仍然是可能的。

Natarajan和Wright现在已经证明情况甚至比这更好：更广泛的问题可以通过纠缠来验证而不是没有它。可以将纠缠量子计算机之间的连接转换为验证器的优势。

要了解如何，请记住MIP中用于验证大小呈指数增长的图形的三种颜色的过程。验证器没有足够的内存来存储整个图形，但它确实有足够的内存来识别两个连接的顶点，并向验证者询问这些顶点的颜色。

对于Natarajan和Wright所考虑的一类问题 - 在非确定性双指数时间内称为NEEXP - 图形大小的增长速度甚至超过了它们在MIP中的增长速度。NEEXP中的图形以双指数速率增长。代替在2的幂次方的速度增加的- 2^1，2^2，2^3，2^4等等-,2 ^ {2-在图中增加顶点的在二的幂的幂的一个速率数^ 1}，2 ^ {2 ^ 2}，2 ^ {2 ^ 3}，2 ^ {2 ^ 4} 等等。结果，图形很快变得很大，以至于验证者甚至无法识别一对连接的顶点。结果，图形很快变得很大，以至于验证者甚至无法识别一对连接的顶点。

Natarajan说:标记一个顶点需要2^n位元，这比验证器的工作内存中的比特数要多得多。

但是Natarajan和Wright证明了，即使不知道向证明者询问哪些顶点，也可以验证一个双指数图的三色。这是因为你可以让提出问题的人自己提出问题。

对计算机科学家来说，让计算机审问自己的解决方案听起来就像让犯罪嫌疑人审问自己一样明智——这肯定是一个愚蠢的提议。除了Natarajan和Wright证明它不是。原因是纠缠。

纠缠态是一种共享资源，Wright说。我们的整个协议都在研究如何使用这种共享资源来生成相互关联的问题。

如果量子计算机纠缠在一起，那么它们对顶点的选择就会相互关联，产生一组正确的问题来验证三种颜色。

与此同时，验证者不希望这两台量子计算机如此纠缠在一起，以至于它们对这些问题的回答相互关联(这相当于一宗犯罪中的两名嫌疑人协调他们的虚假托辞)。另一个奇怪的量子特性处理了这个问题。在量子力学中，不确定性原理阻止我们同时知道粒子的位置和动量——如果你测量一个属性，你就破坏了关于另一个属性的信息。不确定原理严格限制了你对量子系统的任何两个互补性质的了解。

Natarajan和Wright在他们的工作中利用了这一点。为了计算顶点的颜色，他们让两台量子计算机进行互补测量。每台计算机都计算自己顶点的颜色，在这样做的过程中，它会破坏关于其他顶点的任何信息。换句话说，纠缠允许计算机生成相关的问题，但不确定性原理阻止它们在回答问题时串通一气。

维迪克说:你必须强迫证明者忘记，这是纳塔拉詹和赖特在论文中做的主要事情。他们强迫验证者通过测量来消除信息。

他们的工作几乎具有生存意义。在这篇新论文发表之前，我们完全有信心所能掌握的知识的数量限制要低得多。如果我们在NEEXP中面临一个问题的答案，我们别无选择，只能相信它。但是Natarajan和Wright已经突破了这一极限，这使得验证更广泛的计算问题的答案成为可能。

现在他们已经做到了，但还不清楚核查权力的限制在哪里。

它可以走得更远，佐治亚理工学院(Georgia Institute of Technology)的计算机科学家兰斯·福特诺(Lance Fortnow)说。他们给你留下了采取进一步行动的可能性。