量子计算机

好处

德义奇证明，量子计算机无法实现超越算法的任务，也就是说，它无法比普通的图灵机做得更多。但他同时证明，它将具有比传统的计算机大得多的效率，用术语来讲，执行同一任务时它所要求的复杂性（complexity）要低得多。

为什么快

• 根本原因是量子比特 （qubit)是处于叠加态。
• 传统计算机的一个比特，要么就是0，要么就是1,只能代表一个数。
• 而量子比特却可以既是0又是1，它可以是0和1任意比例的叠加态：
  • 比如它可能有30%的概率是0,70%的概率是 1,或者49%的概率是0,51%的概率是1..
  • 一个量子电路，可以同时代表传统电路的很多很多个状态。
  • 意味着你对这个量子电路操作一次，就等于对相应的传统电路操作很多很多次。

下面我做一个非常直观的类比。它并不很精确， 但是容易看明白。

• 想象这里有一个湖，湖水上方有一个光源 S,水面下方有一个点D。
• 现在我们想知道，光线从S点到D点，走的是什么样的路线？
• 它不是一条直线，因为光线会在湖水表面发生一次折射。
• 关键在于那个折射点是在哪里。
  

传统的计算方法，就相当于把水面上每个折射点都考虑一遍

• 这样就有无数条路线，把每条路线都算一遍，看看怎么走从S点到D点最快，真实路径就是最快的路径。
• 这是巨大的计算量。

而量子方法，则是真的给你做一次实验，让光同时沿着所有可能的路径从S点往D点走，

• 最终的真实路径是所有这些路径的叠加态。
• 每条路径有不同的波函数，它们会互相抵消，最终只留下真实路径。
• 在我们这个例子里真实路径只有一条， 但在别的情境下真实路径可以是一个概率分布。

传统方法是一个一个地算，量子方法是全都参与进来一起算，这就是本质区别。
而量子计算机能这么做的前提是你必须确保那些所有可能的路径都参与进来，而这就要求它们的量子态必须互相协调，只有这样才能发生干涉和抵消。

劣势

量子计算机最大的问题，在于不够稳定。
只要稍微被“测量”到，量子叠加态就会马上坍缩，只留下一个结果。
所以量子计算机还有一个很严重的问题是，很难简单把计算结果给输出来。
一旦我们对这个结果进行测量，整个量子叠加态就会瞬间坍缩，从而把正确结果给湮灭了。

所以量子计算机的计算过程会出现大量错误比例，基本都是由“比特错误和相位错误”构成。
但这个问题，可以通过一些算法和机制来解决。
简单说，就是为了解决量子出错的问题，需要不断进行量子纠错。

因此，用量子计算机进行计算，需要要把同一个计算重复上万遍，然后再把这上万个具体的  0  或者  1  统计一遍，才能重新得出正确的运算结果。

除了需要量子纠错的难题之外，量子计算机还在制造难度上存在比较大的瓶颈。

谷歌解决量子纠错问题

• 任何计算机，包括经典计算机，都会随时发生某个比特出错的事情，这就需要纠错，最直观的办法就是把每个比特都做个备份。
• 量子比特更容易出错，可是量子力学又禁止直接复制一个量子比特，所以纠错就更麻烦。
• 此前有个说法是科学家在未来几十年都会被纠错问题困扰…
• 而Google这次却是发明了一个实时纠错的办法，能让量子比特越多，出错率反而越低！跟上一代芯片相比，Wlow的总出错率降低了整整20倍。
• 思路大约是用若干个量子比特组成3×3或者7×7的方阵，叫做「逻辑量子比特(logical qubits)」
  • 这样方阵里有一个比特出错了也没关系。方阵越大，出错的概率就越低。
• 这就是边际效益递增，这就是找到了缩放定律，这就打开了把量子芯片做大做强的道路。

和经典计算机的差异

因为量子比特是具备“可能性”状态，所以在并行计算上，量子计算机的计算速度是远超过经典计算机。

特别是涉及到一些“概率计算”“随机计算”“可能性计算”方面的问题计算时，可以充分发挥量子计算机这个并行计算的特性。

但反过来，一些普通的线性计算问题，量子计算机则体现不出这种对经典计算机的碾压优势。

比如说，两个数相乘，不管这两个数字多大，经典计算机也可以很快计算出这两个数字因子的乘积，在这种线性问题上，量子计算机并没有比经典计算机快多少。

但反过来，给你这个“乘积”，要计算是由哪两个因子相乘，只要这个大数不是偶数，那么经典计算机要反过来计算这个乘积会由哪两个数相乘，就会计算得比较慢，数字越大越难。

但是量子计算机就不一样，量子计算机可以轻易的计算出任意一个大数的因子。因为量子计算机可以一次性把所有可能性计算出来，而不像经典计算机得一次次去把所有可能性计算一遍。

量子计算机本身就是基于量子叠加态去进行量子计算，所以在这种可能性问题上，有巨大的优势。

量子计算机的快，也是主要快在这个地方上。

而这些“概率、可能性、随机”领域的问题，恰好就是材料、制药等领域最容易被卡瓶颈的地方。

能解决的问题

现实是量子计算机并不能用来解决所有的传统计算问题一一它能亚处理很有限的一些问题。

• 或者我们应该这么说：你想用量子计算机求解一个什么问题，就必须先发明对应的量子算法才行
• 可是直到目前为止，科学家只发明了非常少的几个量子算法，只能解决几个特定的问题。

秀尔算法

• 能让量子计算机用于质因数分解
• 因为主流的加密系统高度依赖质因数分解，所以原则上量子计算机可以用来破解密码。
• 有些人甚至据此说Googlel的量子芯片已经对比特币构成威胁.…这是极其夸大的说法，
• 那需要几百万甚至几亿个量子比特才行。
• 目前的量子计算机做质因数分解也就算个3×5、5×7之类

「格罗弗(Grover）算法」

• 用于搜索。
• 比如从一大堆输入值里找到最可能得到特定 输出值的解，经典计算机需要一个一个试， 量子计算机可以“一起”试。