突破 0 和 1 的思维：量子计算介绍

1 什么是量子计算？

量子计算是一种使用量子逻辑进行通用计算的方法，被普遍认为是一种更新型的计算机技术。

在传统计算机中，信息量的基本单位是比特，它只能取 0 或 1 中的一个值。在量子计算机中，信息量的基本单位为量子比特或量子位。通过量子力学现象，这些量子位可以同步进行大量计算。理论上，利用量子力学现象，量子计算可以极大地改进信息存储和处理方式，算法比传统计算更高效，从而能更快地解决各种难题。

这会带来巨大的影响，比如说，今天我们使用的很多加密方法并不是理论上不可攻破的，而是由于目前计算机的物理限制，攻破的时间可能需要10000年，时间太长，我们也就认为这些加密是安全的了。但是，对于量子计算机而言，攻破可能就是分分钟的事情，你存在银行的钱都不安全了，影响之大不言而喻。

2 量子计算历史？

• 1982年，理查德·费曼在一个著名的演讲中提出利用量子体系实现通用计算的想法，开启了量子计算的研究
• 1985年，大卫·杜斯提出了量子图灵机模型，证明了通用量子计算机的理论可行性
• 1994年，彼得·秀尔提出量子质因数分解算法后[9]，证明量子计算机能做出离散对数运算[10]，而且速度远胜传统计算机。这个算法对于量子计算的发展起到了很大的推动作用，因其对于现在通行于银行及网络等处的RSA加密算法可以**而构成威胁之后，量子计算机变成了热门的话题，除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。
• 1996年，Lov Grover提出了可以用于数据库搜索和函数取反的 Grover 算法，进一步证明了量子计算相比于传统计算机的优势。
• 2011年，加拿大的D-Wave 系统公司发布了一款号称“全球第一款商用型量子计算机”的计算设备“D-Wave One”，含有128个量子位。
• 2019年，Google 在 nature 上发表文章，表明他们利用 54 量子比特的 Sycamore 量子计算机在 200 秒内完成了一个计算，而同样的计算用当今最强大的超级计算机 Summit 执行，需要约 10000 年。这也就是之前被广泛报道的 Google 实现了量子霸权（所谓量子霸权，指的就是量子计算机能够解决“经典（非量子）”计算机在合理时间范围之内无法解决的复杂难题这一关键性节点），这项成就被多方认为是量子计算领域的重大里程碑事件。

3 量子计算机如何工作？

一般来说，完成一次计算，需要三个步骤：

提供输入 -> 执行计算 -> 提取输出

提供输入

在传统计算机中，计算机运行的单位是比特，取值为 0 或 1。而量子计算机中，运行单位是量子比特（Qubit），但它的取值比 0 或 1更加复杂，可以处于不同的状态。

量子比特，以及它们所处于的不同状态，用于量子计算机的信息存储和表达。

执行计算

在传统计算机中，通过一些逻辑门（与门、或门、非门等），比特按照顺序被处理，实现一些逻辑运算。而在量子计算机中，也存在一些功能类似的门作用在 Qubit 上，设计不同门的组合实现算法逻辑，实现计算的执行。

量子门，通过修改量子比特的状态，实现计算。

提取输出

在传统计算机中，计算的结果是一个确定的单一取值，可以直接获取。而在量子计算机中，由于量子状态存在叠加和纠缠，量子计算的结果需要一个特定的观测操作，获取到单一的结果，而同时这个计算结果又有一定的概率性，需要多次计算获得答案的样本，并累积对所提供最佳答案的信息，结合统计学可以得到某一答案为正确答案的可能性。通过调整置信度阈值来提供最佳的速度和准确度。

观测操作和结果统计，实现了量子计算的输出提取。

4 量子比特及其状态用于信息表达

基底

传统计算机中，0 和 1 构成比特取值空间中的基础取值。类似的，在量子态空间中，也存在一组基，是量子比特的基础取值。对于一个量子比特的空间，这组基底是（使用狄拉克标记右括向量表示，也叫 ket），也就是量子比特的 0 和1 ：

$| 0 \rangle = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]$∣0⟩=[10​]

$| 1 \rangle = \left[ \begin{array}{c} 0 \\ 1 \end{array} \right]$∣1⟩=[01​]

叠加态

不同于传统计算机，一个比特的取值非0即1，在一个时间只存在一种状态。而量子比特则可以是1 同时也可以是 0，两种状态同时存在，可以表达成如下的形式，其中 $\alpha$α he $\beta$β 是两个复数。

当 $\alpha$α 和 $\beta$β 其中一个为 0 时，处于基态，而都不为 0 时则处于叠加态。

纠缠态

对于两个及以上的量子比特，还存在一种特殊的叠加态，叫做纠缠态。当几个粒子在彼此相互作用后，由于各个粒子所拥有的特性已综合成为整体性质，无法单独描述各个粒子的性质，只能描述整体系统的性质，这种现象叫做量子纠缠。

其定义如下，两个量子比特的基如下：

对于一个 2-qubit 的量子态

如果不能够表达成 product state 的形式，则称为纠缠态，例子如下：

在量子计算中，量子纠缠的意义很大，它可以使空间上分离的多个量子比特之间发生了联系，实现多个比特的联合计算，进而实现相比于传统计算机的指数级加速效果。

5 量子门用于信息处理

上面介绍了量子比特及其状态，量子计算机通过它们来表达信息。而对于计算的执行和信息处理则是通过量子门来实现的。

幺正矩阵

若一 $n$n 行 $n$n 列的复数矩阵 $U$U 满足

$\displaystyle U^{\dagger }U=UU^{\dagger }=I$U†U=UU†=I

其中$\ I_{n}\,$ In​为n阶单位矩阵，$ U^{\dagger }$ 为 $U$U 的共轭转置，则 $U$U 称为幺正矩阵。

量子计算机使用量子门来对量子比特进行操作，而这些操作的算符都是幺正矩阵，将系统从一个状态变换到另一个状态，也叫幺正变换。

只通过幺正变换进行运算看似严格，但已经被证明 [Deutsch, 1985]，这样的量子计算机可以实现图灵完备。

6 观测门用于信息提取

传统计算机，我们可以在任意时间来直接读取它的状态。而对于量子计算机，量子比特的状态不能够直接获得，必须通过观测门来收集得到。

薛定谔的猫

我们都听说过薛定谔的猫的故事，在打开盒子之前，猫处于一种既生又死的叠加态，而一旦打开盒子，猫就到达了一种确定的状态，要么生要么死，因为你的观测，导致猫死了，这就是所谓的好奇害死猫。

这里面说明了一点，就是观测动作会使量子从叠加态塌陷到确定态。观测导致态的塌陷，这对于薛定谔的猫是不好的，但对于量子计算机来说是必要的，这将有助于我们提取得到一次计算的结果。

结果概率性

对于一个量子状态，观测会使其以一定的概率塌陷到一个确定的状态，注意，这里的结果状态有概率性，并不是每次的答案都是一样的，多次计算会给出多种可能的答案样本。

因此，量子计算机在设计时需要考虑多种答案的情况，结合统计学来计算多种答案中某一答案正确的可能性，可以通过调整该置信度来平衡速度和准确度。

7 算法如何设计？

至此，我们知道了量子计算机的工作原理：

1. 量子比特用于存储和表达信息，在计算前，量子计算机被预先定义在某一种状态。
2. 量子门来处理信息和执行计算，在计算中，实现对量子比特状态的变换。
3. 观测门用于提取信息来获得结果，在计算后，通过观测门得到量子比特的状态，并结合统计方法获取答案。

因此，算法的设计主要就是对量子门的排列组合实现特定的逻辑。在量子计算中，有几个重要的量子门可以了解一下。

X-Gate

X-Gate 实现量子位的反转，类似于传统计算机的非门，在量子计算机中则实现了基向量系数的交换。X-Gate 的矩阵如下：

$X = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right]$X=[01​10​]

比如某个量子比特经过 X-Gate 后的结果为：

$X \left[ \begin{array}{c} \alpha \\ \beta \end{array} \right] = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{c} \alpha \\ \beta \end{array} \right] = \left[ \begin{array}{c} \beta \\ \alpha \end{array} \right]$X[αβ​]=[01​10​][αβ​]=[βα​]

Hadamard 门

Hadamard 门的矩阵如下：

$H = \frac{\sqrt{2}}{2} \left[ \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right]$H=22​​[11​1−1​]

对基态进行运算结果如下，可以发现，H 门的作用可以将基态变换称为均匀的叠加态：

$H| 0 \rangle = \frac{\sqrt{2}}{2} \left( | 0 \rangle + | 1 \rangle\right)$H∣0⟩=22​​(∣0⟩+∣1⟩)

$H| 1 \rangle = \frac{\sqrt{2}}{2} \left( | 0 \rangle - | 1 \rangle\right)$H∣1⟩=22​​(∣0⟩−∣1⟩)

C-NOT 门

C-NOT 也就是受控非门，它有两部分组成：Control 和 Target。对于两个量子比特的受控非门，如果 control qubit 是$| 0 \rangle$∣0⟩，则没有变化；如果 control qubit 是 $| 1 \rangle$∣1⟩，则 target qubit 会取非。例如：

$CNOT_{12}|00\rangle = |00\rangle$CNOT12​∣00⟩=∣00⟩

$CNOT_{12}|01\rangle = |01\rangle$CNOT12​∣01⟩=∣01⟩

$CNOT_{12}|10\rangle = |11\rangle$CNOT12​∣10⟩=∣11⟩

$CNOT_{12}|11\rangle = |10\rangle$CNOT12​∣11⟩=∣10⟩

这个门实现了 qubit 之间的联系，类似传统计算机中的条件判断，不同的控制值会导致不同的计算操作。C-NOT 门可以用于制造或者销毁量子纠缠。

总结一下，X-Gate 是非门，也叫 NOT-Gate，实现对量子态的反转。Hadamard 门可以实现基态向叠加态的变换。C-NOT 门可以实现创建或销毁纠缠态。通过这几个门，就可以实现对量子比特状态的改变。

8 硬件如何实现？

上述都是量子计算的理论，虽然理论基础证明了量子计算的可行性，但仍然缺少很多实用的算法来解决传统的计算问题。除了算法的缺失，硬件的实现离商用也还有很长的距离。

目前有几种方法可以构建量子计算机，如下图所示，给出了一些方法及其优缺点的对比，其中最受商业青睐的类型是绝热量子计算机和门模型量子计算机。

如果要构建完全可扩展的量子计算机，量子技术的发展，还需要克服一些障碍。例如，噪声会导致量子系统退相干并失去其量子特性。量子系统对噪声(即该系统定期调整的因素)的敏感度 远高于传统计算机。在设计量子纠错方案(也被称为“容错量子计算”)，以及推动工程技术发展以抑制噪声影响方面，仍有很大提升空间。

9 有什么用？

量子计算机不是万能的，要使用量子计算机解决“正确”的问题。

优化问题

虽然量子计算机具有强大的并行计算能力，不过没有人认为量子计算机会对文字处理或者邮件系统带来巨大的革命。但是在一些优化和搜索问题上，量子特性却能发挥重大的作用，比如：

• 在众多路经中寻找最优化的路径
• 在大数据集上进行特性数据的搜索和查找
• 发现新的化学催化剂
• 利用因数分解来解密数据

抽样问题

绝热量子计算机可以执行的另一功能。抽样可以顺利随机生成某些现象的 随机样例，而经典计算机却很难有效做到。 然而，如果可以控制复杂的量子状态(本 身具有概率性)，便可更为有效地从这些状态抽样。

其他

对于其他一些可以转化为优化问题和抽样问题的问题，比如机器学习的基础是抽样和优化方法，所以完善这些技术就可以提高机器学习的能力。

参考文献：

• An Introduction to Quantum Computing, Without the Physics
• https://www.accenture.com/_acnmedia/pdf-38/accenture-quantum-computing-breakthrough-one-zero-thinking.pdf
• https://www.accenture.com/_acnmedia/pdf-54/accenture-807510-quantum-computing-rgb-v02.pdf
• https://www.sciencemag.org/news/2016/12/scientists-are-close-building-quantum-computer-can-beat-conventional-one
• https://github.com/desireevl/awesome-quantum-computing

作者：厚之成

• 现在注册滴滴云，有机会可得30元无门槛滴滴出行券
• 新购云服务1月5折 3月4折 6月低至3折
• 滴滴云使者招募，推荐最高返佣50%