量子计算模型

量子计算机究竟是怎样计算的？本文的参考书[2]中第四章开头引用了Scott Aaronson的一句话，非常适合用在介绍量子计算模型的文章开头。读完本文如果只能记住一句话，那就记住这句：量子计算机不能瞬间执行完一个暴力搜索算法——如果有人以为量子计算机求解经典算法难以解决的问题(如大整数分解问题)是靠暴力搜索的话。

If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

—Scott Aaronson

量子计算机可以运行量子计算模型，这是它超越经典计算机、解决经典计算机无法解决的问题的原因。但是，量子计算模型并不是能解决任意问题的万金油，也不是把任何算法的运行速度都提高指数倍的金钥匙。有些问题在经典模型下目前只有指数时间解法，但在量子模型下存在多项式时间解法。而另外一些问题，在量子模型下没有明显更快的解法。

适合量子计算模型的问题

这一节内容对于理解量子计算模型本身没有什么作用，只是大致介绍下量子计算模型善于(以及不善于)解决哪些问题。接下来的内容主要参考了[1]。

量子算法解决数论方面的难题似乎特别在行，如大整数分解、离散对数、椭圆曲线离散对数，以及求解Pell方程。不过，即使是量子计算机擅长的数论领域，新的算法的研究也并不是一帆风顺。

Shor在1994年提出了一个能同时破解大整数分解问题、离散对数问题的量子算法，后来就被称为Shor算法。但下一个给经典问题带来指数倍加速量子算法在八年之后才被设计出来，也就是求解Pell方程的算法。

求解Pell方程，即寻找整数和满足，其中为整数。求解Pell方程的经典算法已经有非常古老的历史，仅次于欧几里得算法。Pell方程的求解难度至少不亚于大整数分解，且目前已知的最快求解算法也比大整数分解算法慢指数量级。

Pell方程在密码学领域似乎没有什么存在感。Pell方程是一类丢番图方程，最早提出它的人是谁不得而知，不过并不是Pell，实际上没有任何证据表明Pell和Pell方程有任何联系(除了名字) [3]。后来，Buchmann和William基于Pell方程构造了一个密钥交换协议，设计这个协议的目的是为了让Pell方程优秀的困难性有用武之地，这样即使大整数分解被破解了，还能有一个密钥交换协议可以用。只可惜，Pell方程在Shor算法提出的八年后也被破解了。

现在许多的量子算法研究都围绕着HSP (Hidden Subgroup Problem)。许多问题可以归约到HSP，包括大整数分解、Pell方程等。其中，大整数分解归约到可数群上的HSP，Pell方程则归约到不可数的群上的HSP，这两个问题归约到的群都是阿贝尔群，而在阿贝尔群上的HSP问题已经被量子计算机解决，所以大整数分解和Pell方程都被量子计算机解决了。

图同构问题归约到对称群上的HSP，uSVP问题归约到dihedral群，这两类群都是非阿贝尔的，而非阿贝尔群上的HSP还没有被解决。所以图同构和uSVP问题还没有解决。

至于NP难(或称NPC、NP完全)问题，普遍相信量子计算机是不能够解决的。不过，与此同时，大家也相信密码算法是很难基于NPC问题构造的。目前已知的能够用来构造密码算法的问题，从大整数分解到离散对数，都不是NPC的(要不然，根据NPC问题的定义，量子计算机就把整个NP都破解了)。

数学基础

要理解量子计算模型中的状态，需要理解一个运算，叫做张量积(Tensor Product)。两个矩阵的张量积定义如下：

可以看到(不同于矩阵乘法)矩阵的张量积可以对两个任意维度的矩阵计算。一个的矩阵，乘以的矩阵，得到一个的矩阵。如果把向量看成特殊的矩阵，同样可以得到向量的张量积。下面是几个示例：

示例1：

示例2：

示例3：

我们把向量叫做一阶张量，矩阵叫做二阶张量。我们发现，两个同方向的一阶张量的张量积仍然是一阶张量，但两个方向不同的一阶张量的张量积就得到了一个二阶张量。

同样的，两个二阶张量的张量积仍然只是一个二阶张量，但是如果我们想象一个在第三个维度方向上有长度的向量或者矩阵，和一个矩阵做张量积，就可以得到一个三阶张量，也就是一个立体矩阵。不过，这在我们的讨论范围之外，这里只用到二阶以内的张量和张量积。

用量子模型描述经典计算

量子计算模型是经典计算模型的“超集”，换句话说，经典计算模型其实是一类特殊的量子计算模型，这就像实数是一类特殊的复数一样。为了理解量子计算模型，我们首先用一种特殊的方式来描述经典模型。

在经典计算模型中，任何一个时刻，计算的状态可以用一个字符串刻画。假设这个字符串由个比特组成。我们说这是一个比特的计算模型。在计算的每一步，你可以对这个比特中的若干个进行一个操作。比方说，你有两个指令，“非”指令和“异或”指令。“异或”指令可以指定三个连续的比特，如，令。一个程序由一系列这样的指令构成。一个经典计算机可以支持若干这样的经典指令。

例：设，输出为0000，程序有如下指令组成：

那么，这个计算过程也可以描述如下：

• 0000：初始状态
• 1000：第一步后
• 1010：第二步后
• 1010：第三步后

上述是一个经典计算过程的经典描述。接下来，开始用不那么直观的、更加接近量子计算模型的方式来描述上述经典模型。

第一步

考虑到个比特的计算状态共有种可能，我们用一个大小的One-Hot向量来表示计算状态。所谓的One-Hot，就是指这个向量只有一个位置为1，其他位置都是0。这个向量中的每个位置和比特字符串的每个取值一一对应。实际上，我们可以把这个比特字符串对应到它表示的二进制数对应的位置。例如0000对应位置0，0101对应位置5，等等。

还是上面那个例子，计算过程就变成了：

• ：初始状态（位置0）
• ：第一步后（位置8）
• ：第二步后（位置10）
• ：第三步后（位置10）

可以看到，用这种描述方式，每一步计算其实都是把1挪来挪去。

第二步

用的矩阵来描述指令。首先看一下最简单的“非”指令怎样用一个矩阵描述。

在上面的例子中，假如“非”指令作用在第一个比特上，它所起的作用就是把0000变成1000，把1000变成0000，把1001变成0001，0001变成1001。换句话说，如果1在位置0上，就移动到位置8，如果在位置8上，就移动到位置0，等等等等。

我们可以构造这么一个矩阵，它的作用是把向量的0号位置和8号位置交换，1号位置和9号位置交换，总之，把号位置和号位置交换。总体来看，这个矩阵的作用是把向量的前8个位置和后8个位置互换；也可以表述为，将这个向量往右“旋转”8个位置。我们知道这个矩阵就是一个旋转矩阵：

上面这个矩阵就代表了“对第一个比特执行NOT”这个指令。

如果要表示“对第二个比特执行NOT”这个指令，这个矩阵该是什么样子呢？这个矩阵写起来就比上个矩阵复杂多了。幸好我们有张量积这个工具。上面这个矩阵，我们把它写成张量积的形式：

我们用表示矩阵

于是上述翻转第一个比特的矩阵表示为。类似地，翻转第二个比特的矩阵是。

上述矩阵表示可以拓展到个比特的情况。特别地，当时，本身就是对单个比特进行翻转的操作，即将0变为1，将1变为0。如果用One-Hot向量表示，就是一个2维向量，作用在上得到，作用到上得到。所以把称为交换矩阵。

每一个指令对应的矩阵，都可以这样推算：

1. 只考虑这个指令涉及到的几个比特，得到一个小的矩阵
2. 拓展到个比特的矩阵，可以通过将这个小的矩阵和单位矩阵做张量积得到

例：考虑一个操作两个比特的指令：。当为时，它不做任何操作，当为时，它会翻转。

1. 只考虑它涉及到的这两个比特，即的情况。此时。这个矩阵保持00和01不变，将10和11翻转。用One-Hot向量表示，则是保持和不变，只交换和。所以，这个矩阵如下

   

2. 将这个矩阵记为。将其扩展为操作4个比特中的前两个比特的矩阵，即为。如果是操作中间两个比特，则对应的矩阵为。以此类推。

用上述方式，我们可以为所有指令推出其对应的矩阵，就不再对每个指令详细推导了。

第三步

这一步中，我们引入将要用来描述量子模型的符号，来重新描述一下上述过程。

我们把维比特串对应的那个One-Hot向量记为。例如表示，即1在位置5上的那个向量。如果接触过量子力学的话，应该对这个记号不陌生，它被称为狄拉克记号。另外也要记得这只是一个记号，它只不过是一个向量而已，每次遇到这个记号，在心里默默将它换成对应的One-Hot向量即可。

于是，只能操作单比特的二阶矩阵，作用到上得到，作用到上得到。

将扩展到作用在四个比特中的第一个比特上的16阶矩阵，它作用在上得到。类似地，矩阵作用在上得到的是。可以看到，用狄拉克记号可以直观地将指令、矩阵和矩阵作用在向量上的效果联系起来。

类似地，矩阵作用到和上保持不变，而将和互换。其扩展之后的矩阵作用到更多的比特上的效果也是类似，不再详述。

最后，我们可以观察到一个现象：将两个狄拉克记号表示的向量合并，等价于对其求张量积。例如，，。可以通过张量积的定义验证这些等式。

类似地我们可以发现，取若干个向量，如，和，分别作用上一个矩阵，如，和，分别得到，和，将其结果求张量积，得到，它等于先求这些向量的张量积，再作用上这些矩阵的张量积。也就是说。由此，我们发现，使用狄拉克记号和张量积的表示方式，写下来的矩阵和向量，和原来的指令和比特串表示方式一模一样。

例如，将NOT指令作用在比特串110101的最后一个比特上，将XOR指令作用在前两个比特上，得到比特串100100，用矩阵和向量的表示方式，就是作用在向量上得到向量。

综上，我们得到了经典计算模型的量子描述方式。如果只看最后的形式，似乎只是在玩符号游戏。不过，一旦考虑到量子效应，这两种表示方式就完全不同了。

量子计算模型

注意到，在经典模型下的这些指令推导出的矩阵，全都是排列矩阵。它们的作用在一个One-Hot向量上，得到的结果一定也是一个One-Hot向量。量子计算模型比经典模型更强大的地方在于，它引入了带有复数的矩阵。这样的矩阵作用在一个One-Hot向量上之后，可能会得到一个非One-Hot向量。这样的状态是无法用经典计算状态描述的，被称为叠加态。

考虑叠加态之后，计算状态所有可能数量就不再是只有种了，实际上可以在一整个维的复线性空间中取值了，而那个One-Hot向量正是这个维线性空间的一组基。我们称这样一个量子计算模型有个qubit(量子比特)。

只有一个qubit时，所有可能的状态是一个二维空间，这个空间的一组基包含两个向量，和，或者记为和。相对于经典状态只能是或者，量子状态可能是两者的一个线性组合

用传统的向量表示，其实就是。这个状态无法再用经典状态表示了。如果一定要用形象的思维去理解，可以说，目前的比特串状态“以的概率等于0，以的概率等于1”。然而，这样的表述仍然不准确，因为和并不是概率。只有当计算结束，我们需要得到一个结果，对这个状态进行“测量(Measure)”的时候，状态才会从纠缠态退化到经典状态，究竟会退化到哪个状态，是一个随机事件，其概率等于这个状态的系数的模平方，即。所以，和需要满足，即这个向量是单位向量。所有的门对应的矩阵也都是正交矩阵，保持向量的大小不变。

上文提到的矩阵，即交换向量的两个位置的那个矩阵，在这里的作用也是一样。它将变成。矩阵不会改变计算状态的叠加性。它会把经典状态变为经典状态，同样地，处于叠加态的状态，在的作用下仍然属于叠加态。这是因为是经典模型下的指令对应的矩阵，它只是一个排列矩阵。

一个非经典状态下的矩阵的例子如

这里这个系数的存在是为了让成为单位正交阵，保持向量的模不变。作用在向量上得到。在向量上则得到。注意到，的平方就是单位阵，即它是它自己的逆。所以，它再次作用在这两个叠加态的向量上，就会再次分别得到和。

将矩阵扩展到能够处理个qubit的方式也和经典状态下类似。例如，矩阵可以作用在五个qubit对应的向量上。为了推出作用的结果，将其写作，矩阵作用之后，相当于把作用在中间的上，其他部分不变，得到，等于，等于。可以看到，和单独作用在上很相似，只不过前后各增加了两个qubit。

如果一个量子计算模型中，所有的门都是像和这样只作用在单个qubit上，那么这个量子模型很容易就可以用经典模型虚拟出来。为每个qubit 创建一个二维复数向量保存的状态。因为每个门都只单独作用在一个qubit上，只需用矩阵乘在对应的向量上。计算结束后对结果进行测量时，只需对每个qubit进行一个伯努利采样，拼在一起得到最终的结果。

不过，只需要一个能够作用在两个qubit上的矩阵，就可以将状态变到无法用上述方法模拟。这样的矩阵多次作用之后，表示这个状态所需的系数就多达指数级。

小结

本文简要介绍了量子计算模型。首先概述了适合用量子计算模型解决的问题。接着在经典模型下引入了量子模型的表示方式。最后，简单介绍了一下能够使计算状态进入叠加态的矩阵，以及对叠加态的测量。

参考资料

[1] Daniel J. Bernstein, etc. Post Quantum Cryptography. Chapter 2. 2008.

[2] Jack D. Hidary. Quantum Computing: An Applied Approach. Springer.

[3] James Kraft, etc. An Introduction to Number Theory with Cryptography. 2018.