最近在学习量子计算，写下一点对量子计算的简单介绍，水平有限，如有不对之处欢迎指出，欢迎交流。
在过去的80年里，传统计算机飞速发展，完成了从图灵模型的提出到物理实现再到快速小型化的惊人过程。然而传统计算机有其局限性，在发展中逐渐展现出以下两个问题：
随着晶体管和集成电路的发明，计算机快速进入小型化阶段。以至于英特尔创始人之一摩尔(Gordon Moore)在1965年提出了著名的摩尔定律来预测这一趋势：芯片上集成的晶体管数量每18-24个月就会翻一倍。摩尔定律已经成功预测了过去40多年的芯片发展。如今，以CORE i7处理器为例，其集成的晶体管数目已达到7.31亿个。但随着晶体管的集成数目越来越多，晶体管之间的距离就会越来越小。这不仅会使得芯片更加难以制作，还会使得元件间的量子效应越来越明显，直至发生量子隧穿效应，导致元件间的漏电。这给传统芯片的微型化盖上了天花板。一般而言，计算机问题可以分为p(polynomial)和np(non-polynomial)两种问题。p问题即多项式复杂度问题，指的是计算机的计算工作量以输入N的多项式函数来增长，而在np问题即非多项式复杂度问题中，计算工作量以非多项式函数增长，例如指数函数等。传统计算机处理p问题并不困难，就算是稍复杂的问题也可以通过增加晶体管集成度来提高运算速度。但是对于np问题，计算时间将成指数增长，对于较大的输入，计算时间将极长，传统计算机无法完成。所以解决np问题对传统计算机而言是一个巨大的挑战。基于量子力学而建立的量子计算机可以帮助解决这些传统计算机所遇到的问题。为此，下面先来介绍一下量子计算机。
量子计算机最初由费恩曼(R.P.Faynman)于1982年提出，他认为要想模拟复杂量子系统，就需要使用基于同样原理的量子机器，这样机器处理的能力才能和量子系统的复杂度相匹配。在那之后，伴随着诸如激光调控原子等技术的进步，物理学家们将量子计算机逐步变成了现实。和传统计算机结构类似，量子计算机也是从量子比特(quantum bits/qubits)到量子逻辑门(quantum logic gates)再到量子电路(quantum circuits)，逐步构建起来。
量子比特(qubits)传统计算机的比特通过电平(电压)实现，只有两种状态0或者1。而单个量子比特同样也有两种基本状态，即纯量子态(pure quantum state)或本征态 |0⟩\left|0\right\rangle 和 |1⟩\left|1\right\rangle 。但量子比特不同于传统比特的地方在于，量子比特遵循量子力学的规律，它还可以处于叠加态(superposition state)，即： |ψ⟩=C0|0⟩+C1|1⟩\left|\psi\right\rangle=C_0\left|0\right\rangle+C_1\left|1\right\rangle ,其中 |C0|2\left| C_0\right|^2 和 |C1|2\left| C_1 \right|^2 为量子态处于0或1态的概率， C0C_0 和 C1C_1 可以取满足 |C0|2+|C1|2=1\left| C_0 \right|^2+\left| C_1 \right|^2=1 的任意复数值。也正是这种叠加态的特性，使得量子比特可以将信息存储在系数 C0C_0 和 C1C_1 中，携带比传统比特更多的信息参与计算。
对于多个量子比特，其状态可以表示为 本征态的组合。以两个量子比特为例：|ψ⟩=C00|00⟩+C01|01⟩+C10|10⟩+C11|11⟩\left|\psi\right\rangle=C_{00}\left|00\right\rangle+C_{01}\left|01\right\rangle+C_{10}\left|10\right\rangle+C_{11}\left|11\right\rangle ， |ij⟩\left|ij\right\rangle 表示qubit1处于 ii 态，qubit2处于 jj 态。量子信息就存在 CijC_{ij} 系数中。每当我们需要提取结果，去测量量子比特时，它们都会按照概率坍缩到其中一个纯态。
量子比特的物理实现有已经有多种方法。它们均选择有两个可明显区分的本征态的量子系统作为量子比特。典型的系统包括：
传统计算机有三个基本的逻辑门：与、或、非，通过这三个门的组合来实现对比特的运算操作。量子计算机中也通过构建逻辑门来实现对量子比特的操作。经典的单比特逻辑门有 NOT门(0110)\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} ，Z门 (100−1)\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} ，Hadamard门 12(111−1)\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} 。以NOT门为例，我们将单个比特的状态写成矩阵形式： (c0c1)\begin{pmatrix} c_0 \\ c_1 \end{pmatrix} ，并将逻辑门作用到其上，可得到新的比特状态：(c1c0)=(0110)(c0c1)\begin{pmatrix} c_1 \\ c_0 \end{pmatrix}=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} c_0 \\ c_1 \end{pmatrix} 。若初始态为 |0⟩\left| 0 \right\rangle ,则矩阵为 (10)\begin{pmatrix} 1\\ 0 \end{pmatrix} ，通过NOT门后得到 (01)\begin{pmatrix} 0 \\ 1 \end{pmatrix} 即 |1⟩\left|1\right\rangle态，这就实现了态的翻转。除此之外，还有两比特逻辑门像C-NOT门，其输入是两个量子比特。
逻辑门的物理实现同样有多种方法。以二能级原子作为量子比特，两能级之间的能量差为 E1−E0=ℏωE_1-E_0=\hbar\omega 。将一束频率为 ω\omega 的激光照向原子，根据光和原子的相互作用可知，原子将会发生拉比振荡(Rabi oscillations)，在基态和激发态之间来回翻转，控制合适的时间，即可实现从 |0⟩\left|0\right\rangle 态翻转到 |1⟩\left|1\right\rangle 态。
除了上述介绍的方法外，对于不同的量子比特系统，还有着不同的逻辑门实现方法。这里就不再介绍了。
量子电路(quantum circuits)通过将单比特逻辑门和两比特逻辑门进行组合，即可实现量子电路。将一串处于初始态的量子比特输入电路中，经过逻辑门的操作后，再输出为一串处于量子叠加态的比特，最后进行测量，让量子比特坍缩获得结果，即完成了一个量子电路的功能。
以上就是对量子计算机的简单介绍。让我们回到开篇提到的传统计算机所面临的问题。对于传统芯片面临的微型化问题，量子计算机由于本就建立在量子力学的基础上，所以不会遇到这样的天花板，不过如今的量子计算机都非常巨大，如何小型化是一个问题。针对传统计算机无法解决的np问题，量子计算机基于量子纠缠原理，可以实现数据的并行计算。通过设计巧妙的算法，np问题在量子计算机上就有可能转化为p问题，如著名的Shor算法和Grover算法。
如今的量子计算机发展也同样面临着一些急需解决的问题。量子计算机依赖于量子比特的叠加态，而叠加态很容易会受到环境的干扰而坍缩，从而破坏计算过程。因此如何将它们与环境隔离不受环境干扰，成了一个重要问题。这个问题也同样制约着量子计算机的大型化，因为更多的量子比特，不仅会更加容易与环境作用，而且会展现出经典物理的特性。不过已经有不少的方案被提出来，以解决这些问题。如将每一个量子模块控制在一个适当的大小，模块与模块之间通过光子携带信息来进行交流，这样可以避免过大的系统带来的问题。
参考文献：
[1]C.P.Williams Explorations in Quantum Computing(2011)
[2]M.A.Nielsen and I.L.Chuang Quantum Computation and Quantum Information(2000)
[3]M.Fox Quantum Optics(2006)
