1936 年，阿兰·图灵发表了图灵机理论，证明了存在一种计算机可以执行任何能被算法表达出来的计算过程。1945 年，第一台图灵完备的电子计算机 ENIAC 投入使用，它和后续的电子计算机改变了人类的历史进程。关于量子计算的研究始于 1980 年代。尽管时至今日，尚未出现能进行复杂计算的量子计算机，但量子计算的相关理论已经成熟。
一般来说，完成一次计算需要做三件事：
提供输入 -> 执行计算过程 -> 提取输出
对于电子计算机而言，输入和输出都可以表达为一串比特。计算过程，就是处理单元在程序的控制下，通过 AND, OR, NOT 等逻辑门电路修改这些比特的过程。
而量子计算机，输入的是量子比特（qubit）。计算过程是量子门（quantum logic gates）修改量子比特的状态（quantum state）。输出的是量子比特观测的结果。
因此，理解量子计算，需要搞清楚量子比特、量子门和量子观测。考虑到量子计算的物理实现有多种方法，且许多细节均为机密，本文只会阐释量子计算的理论基础。
量子比特
传统的比特有且只有 0 和 1 两个状态。如果存在一个比特，那么它在某时刻的状态必须是 0 和 1 之间的一个。量子比特与传统的比特不同，它的状态在理论上用一个长度为 2 的列向量表示。首先我们定义如下两个量子比特 \(| 0 \rangle\) 和 \(| 1 \rangle\).
\[
| 0 \rangle = \left[
\begin{array}{c}
1 \\
0 \end{array}
\right]
\]
\[
| 1 \rangle = \left[
\begin{array}{c}
0 \\
1 \end{array}
\right]
\]
量子比特 \(| 0 \rangle\) 和 \(| 1 \rangle\) 是量子比特的计算基态（computational basis state）。或者说，它们是量子态空间的一组基。
任何一个量子比特 \(| e \rangle\) 都可以表达为 \(\alpha| 0 \rangle + \beta| 1 \rangle\) 的形式，其中 \(\alpha\) 和 \(\beta\) 是两个复数，且它们的模的平方和等于 1，也就是
\[
| \alpha |^2 + | \beta |^2 = 1
\]
上述的限制又称为归一化条件。
比如说，\(0.6 | 0 \rangle + 0.8 | 1 \rangle\) 是一个量子比特，\(\frac{1-i}{2} | 0 \rangle + \frac{1+i}{2} | 1 \rangle\) 也是一个量子比特，但 \((1-i) | 0 \rangle + (1+i) | 1 \rangle\) 就不是一个量子比特，因为它不满足归一化条件。按照数乘矩阵的规则，上面两个量子比特又可以写作
\[
\left[
\begin{array}{c}
0.6 \\
0.8 \end{array}
\right]
\]
和
\[
\left[
\begin{array}{c}
\frac{1-i}{2} \\
\frac{1+i}{2} \end{array}
\right]
\]
直观上讲，量子比特可以视为传统比特的一种叠加态（superposition）。比如说，\(0.6 | 0 \rangle + 0.8 | 1 \rangle\) 可以视为 0.36 (\(0.6^2\)) 个比特 0 和 0.64 (\(0.8^2\)) 个比特 1 的一种叠加状态。
量子门
正如数字电路中的逻辑门可以修改比特的状态一样，量子门可以修改量子比特的状态。量子门既可以只有一个输入和一个输出（转变单个量子的状态），也可以具有多个输入和多个输出（转变多个量子的状态）。输入和输出的数目应当相等，也就是说不可以吞噬量子。下面介绍两个单输入输出的量子门和一个多输入输出的量子门。
NOT 门
NOT 门作用于单个量子比特，它可以交换两个基向量的系数：
\[
NOT(\alpha| 0 \rangle + \beta| 1 \rangle) = \alpha| 1 \rangle + \beta| 0 \rangle
\]
量子的 NOT 门是数字电路中 NOT 门的一个扩展。举一个直观的例子，假如原先的量子态是 0.36 个比特 0 和 0.64 个比特 1 的叠加态，那么经过 NOT 门之后，就变成了 0.64 个比特 0 和 0.36 个比特 1 的叠加态。
单输入输出的量子门可以使用一个 \(2 \times 2\) 的矩阵来表示。一个量子经过量子门之后的状态，由该量子状态向量左乘量子门矩阵的值决定。NOT 门对应的量子门矩阵为
\[
X = \left[
\begin{array}{cc}
0 & 1 \\
1 & 0 \end{array}
\right]
\]
因此，某个量子比特经过 NOT 门的结果为
\[
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]
\]
Hadamard 门
Hadamard 门同样作用于单个量子比特，它可以依照系数分解现有的量子态：
\[
H(\alpha| 0 \rangle + \beta| 1 \rangle) = \frac{\alpha + \beta}{\sqrt{2}} | 0 \rangle + \frac{\alpha - \beta}{\sqrt{2}} | 1 \rangle
\]
用矩阵来表示就是
\[
H = \frac{\sqrt{2}}{2} \left[
\begin{array}{cc}
1 & 1 \\
1 & -1 \end{array}
\right]
\]
虽然 Hadamard 门和数字电路中的 AND 和 OR 门并无直接的关联，但它在不少量子计算算法中有重要的应用。有兴趣的读者可以自行证明，连续使用两次 Hadamard 门之后，量子会回到原先的状态——这个行为和 NOT 门是一致的。
单输入输出的量子门可以有无穷多种，只要满足量子比特状态向量左乘量子门矩阵的结果依然满足量子比特的归一化条件即可。在这里我们不加证明地给出如下定理：
某个 \(2 \times 2\) 的复矩阵能作为量子门的一个表示，当且仅当其共轭矩阵等于其逆矩阵。
受控 NOT 门
在计算机程序中，充满着条件判断语句：如果怎样，那么做什么，否则做别的什么。在量子计算中，我们也期望一个量子比特的状态可以因为另一个量子比特而改变，这就需要多输入输出的量子门。下面要介绍的是受控 NOT 门（CNOT 门）。它具有两个输入和两个输出。如果把输入和输出当作一个整体来看，这个状态可以用 \(\alpha| 00 \rangle + \beta| 01 \rangle + \gamma| 10 \rangle + \theta| 11 \rangle\) 来表示。其中 \(| 00 \rangle\), \(| 01 \rangle\), \(| 10 \rangle\), \(| 11 \rangle\) 是长度为 4 的列向量，它们由 \(| 0 \rangle\) 和 \(| 1 \rangle\) 拼接而成。
这个整体也需要满足归一化条件，即
\[
| \alpha |^2 + | \beta |^2 + | \gamma |^2 + | \theta |^2 = 1
\]
CNOT 门中，第一个输入是比特 0 的部分，会维持第二个输入的状态；而第一个输入是比特 1 的部分，会以 NOT 门的方式作用于第二个输入的状态。第一个输入的量子比特会原样输出，而第二个输入的量子比特的状态由上述的叠加态决定。用数学公式来表达就是
\[
CNOT(\alpha| 00 \rangle + \beta| 01 \rangle + \gamma| 10 \rangle + \theta| 11 \rangle) = \alpha| 00 \rangle + \beta| 01 \rangle + \gamma| 11 \rangle + \theta| 10 \rangle
\]
量子观测
从上面关于量子门的介绍可以看到，一个量子比特处于两个量子态 \(| 0 \rangle\) 和 \(| 1 \rangle\) 的叠加态；两个量子比特组合成的整体，处于四个量子态 \(| 00 \rangle\), \(| 01 \rangle\), \(| 10 \rangle\) 和 \(| 11 \rangle\) 的叠加态。以此类推，\(n\) 个量子比特处于 \(2^n\) 个量子态的叠加态，这相对于 \(n\) 个传统的比特却只有一个固定的状态相比，是巨大的优势。然而物理定律也有它的限制——确切地知道一个量子比特的状态的方法是进行一次观测，但观测会使得叠加态坍缩，变成一个确定的状态。一个量子比特在观测之后得到的信息是传统的比特，它的值只能是 0 和 1 之间的一个。一个叠加态会塌缩成 0 或者 1，是由叠加态中的系数 \(\alpha\) 和 \(\beta\) 决定的。这个叠加态塌缩成 0 或 1 的概率分别为 \(| \alpha |^2\) 和 \(| \beta |^2\)。类似的，一个双量子比特的系统，其观测结果为 00, 01, 10, 11 的概率分别是 \(| \alpha |^2\), \(| \beta |^2\), \(| \gamma |^2\) 和 \(| \theta |^2\).
这样的物理定律导致量子计算的结果是不确定的，它有一定的概率输出一个错误的结果。在实际应用中需要额外的手段来验证输出的正确性。量子计算使用的算法，如果能在观测的上一步尽可能地减少量子比特的叠加态，就能以大概率得到正确的结果。
组合起来
我们把上面提及的几个部分组合起来，所谓量子计算，无非就是：
- 从一组计算基态开始（每个量子比特被初始化成 \(| 0 \rangle\) 或 \(| 1 \rangle\) 作为计算的输入）；
- 根据预定的算法，通过一系列量子门；
- 经过量子观测得到一串比特作为结果。
值得说明的是，在现阶段，实现每一个量子门，都需要人工操纵物理实验设备，写量子计算的程序还远没有敲字符那么简单。
物理学家尚未证明量子计算的界限在哪里，不知道它是否可以用来模拟任何物理过程。从 1980 年代到现在，量子计算应用于实践似乎仍遥遥无期，但它的某些应用，如解算蛋白质结构，以及破解不对称加密密钥，已经引发了不少关注。我们无法知道它的大规模普及是否会像电子计算机一样再次改变人类社会。