01大数分解

说起这个新对手，我们不得不先从大数因数分解讲起。

我们知道在现代密码学中，有许多密码系统用来保护信息，它们利用大数分解来进行加密。

现在如果我给你一个400位的数字，事实证明你很难直接分解出它的因数。两个数的乘法很容易，如果把两个200位的数相乘，你可以很快的计算出结果。如果用计算机来计算的话，甚至会更快。但是一个400位的数字，让你计算出它的两个因数，你很难解出来。

但事实上有个量子算法能解决这个问题，它是由Peter Shor在1994年提出，已经被证明量子计算机能够非常快速的分解大数。

有很多方法可以估计量子计算机运行该算法的时间。一种估计是，如果你使用超级计算机来分解一个400位的数字，大概需要60万年。

但如果你用量子计算机来计算，假设我们已经有了一台合适的量子计算机，你只需要几个小时甚至几十分钟就能完成计算。

所以Peter Shor的这个量子算法，也许是最著名的量子算法。

02量子算法

Peter Shor的这个算法是非常数学化的，所以我将以不同的方式呈现它。

实际上这个经典算法本身很有趣，因为它涉及到一些著名的先驱科学家的工作。它也确实是由一些著名的物理学工作启发而成。这个物理或者化学分支，叫做X射线晶体学。

这个著名的工作起源于Roentgen在1895年的发现，他偶然发现了一种他称之为X射线的神秘现象，也因此在1901年获得了第一届诺贝尔物理学奖。

但人们很难确定它是一个粒子还是一个波，直到1912年，Von Laue提出了一个很棒的想法：把X射线照射到像盐这样的晶体上。按照当时的科学理论水平，如果能得到晶体的衍射图案，那就能证明他肯定是波。因为粒子不会相互干涉。

在1913年，Braggs父子推导出了衍射现象的数学公式。这个工作意义重大。一旦你能用数学公式来分析和预测，那么就能运用在实验中。

我们来做个假设。假设你有一个未知结构的晶体，你拍摄了一些X射线照片，也许从各个角度都拍摄了。现在根据数学公式，你甚至就能恢复出晶体的结构。这个方法也在接下来的许多年由它产生了许多诺贝尔奖。

03光学算法

事实上，科学家们后来变得越来越有野心。他们从最初的无机材料分子，到后来分析诸如蛋白质这样更复杂的生物大分子。

类似地，如果我们想分析一个整数，只需要根据这个整数来构造一个晶体，然后用X射线去照射它。

那我们该怎么做呢？

第一步就是设计出这个经典算法，而我们正在设计的就是这种光学算法。

然后想象一下，用X射线去给这个整数N拍照。不过，首先你需要足够聪明地去构造出一个晶体，然后你用X射线去拍照，看一下衍射图案。当然也许你需要多试几次。接着，你分析照片就可以得到这个数字的因数。实际上这是可以完成的，尽管里面涉及到一些复杂的数学。

但如果你想天真的去建造这个晶体，那整个银河系，甚至整个宇宙都不够大。

现在我们进入下一步，也是最关键的一步。

第一，实际上我们只需要几个样本点就够了，并不需要指数级的样本数。我们只需要多项式量级的样本数。

现在的问题是如何去采样？即使是采一个样本点？也是很困难的。因为如果你取一个样本进行计算，你需要对指数多的项求和。

所以，如果你使用经典算法来计算，它仍然很难。但是指数多的项求和是非常结构化的，如果你用一种聪明的方式去计算，即如果你有一台量子计算机，那么你可以使用量子傅里叶变换来进行计算。

这样你就可以进行并行搜索，并指数级的节省时间。这对采一个样本点意味着什么呢？

现在就是最精彩的地方了，波粒二象性将会起作用了。波粒二象性告诉我们，即使只有一个光子，仍然能通过它。事实上，一个光子通过装置后的概率分布将与经典情形相同，这样你就会得到完全相同的分布。

因此如果我能采样，只需要发射一个光子并探测光子着陆的位置。这个样本点包含了整个晶体的信息，最终的结果是把这些组合在一起，得到一个多项式运行时间的量子算法。

好了，现在终于把这个大数因数分解的问题及量子计算机如何解决的问题阐述清楚了。

04新对手——随机磁电路

现在到了这篇文章的核心部分，也就是这个量子计算机的新对手——随机磁电路。

如今，来自日本东北大学和美国普渡大学的科学家们受到神经网络原理的启发，发明了一种新的硬件，也能够实现因数分解，而且这种硬件的制造工艺和使用方法比量子计算机更简单。现在它只需8bit就能对945执行因数分解。

这就是包含纳米磁体的集成电路，完整的名称是：随机行为纳米磁性隧道结（MTJ）。目前相关论文已于2019年9月18日刊登在《Nature》杂志上。

与量子计算机有何不同

下图展示了普通计算机、量子计算机和随机磁电路的区别：

a表示普通计算机，只有0和1两种状态，区别就在于栅极上带的是哪种电荷；而量子计算机可以同时处于0和1的状态叠加，也就是经典模型——薛定谔的猫，只要箱子没打开，你就无法知道猫是死还是活，就是“死和生”的叠加状态。

d表示这篇论文提出的随机磁电路。它的每个位也具有0和1的两种状态，这取决于磁体中的电子的总体自旋是向下还是向上。随机磁位在0和1状态之间随机波动，并且在每种状态下具有一定的概率，在图中由箭头大小表示。

随机磁电路与现有的磁阻随机存储器原理类似，不过其能垒更低。对于随机磁电路中的位来说，由于0和1之间的能量差距很小，随机弛豫力导致纳米磁体在两种状态之间随机波动，研究人员这种比特叫做随机比特，简称p比特（p-bit）。

不同p比特之间通过磁场产生相互作用，调节纳米磁体的直径和厚度可以改变其消磁所用的时间。为了让磁体之间形成随机神经网络的模块，研究人员将随机MTJ与NMOS晶体管连接起来，获得一个三端p比特。

优点

在论文提到的因数分解算法中，只需n个p比特就可以编码高达2ⁿ⁺²的整数，这种关系比当前的量子计算机方案需要的比特数更少。

除了在存储和算法上的优势外，随机磁电路相比量子计算机还有两大优点。

首先，纳米磁铁芯片可以使用已有的磁阻随机存储器（MRAM）工艺制造，而量子计算机则需要高度复杂的制造工艺。

其次，纳米磁芯片可以在室温下工作，而量子计算机需要冷藏才能保持在绝对温度1K以下。因为要维持低温，量子计算机需要消耗大量能量，计算机本身每一瓦的功率，则需要大约一千瓦的制冷功率，这会增加开发和操作的难度。

应用前景

用于质因子分解的纳米磁芯片方法仍处于起步阶段，需要进行许多开发才能将它转变为实用的计算引擎。其中的挑战有：将数千个磁位相互连接起来，在集成电路中组合磁位和普通的晶体管。

与量子计算相比，这些要求能够更快更容易地实现，未来许多机构的资金可能会从量子计算转向纳米磁芯片。

随机磁电路是对MRAM技术进行微小的修改就能实现的，研究人员认为，这种技术未来还可以在优化、采样和机器学习领域找到应用。