text: 量子计算学习心得(2.2)：量子计算机工作原理
  第2.1节，我们简单回顾了经典计算机的工作原理以及计算通用性的概念：我们看到，经典计算机可以通过简单的逻辑运算的组合，对二进制比特进行处理，并实现有限位二进制数上的所有可能的函数。与经典计算一样的是，量子计算机也以二进制比特0,1为载体，但与经典计算不同的是，量子比特可以有0和1的叠加态，而相应的运算过程也和经典计算有着本质不同。而人们研究量子计算机以及量子算法的热情，来自于量子计算在某些问题上相对于经典计算展现出的所谓量子优越性（quantum supremacy），也就是计算的加速，作为初学者，我们往往希望很快知道这种优越性是如何实现的。而这将是本章最重要的任务。从这节开始一直到本章结束，我们就将逐步揭示量子计算机的工作原理、单量子比特和多量子比特的表示方式以及运算特征、最后用几个著名量子算法初步认识量子计算如何利用叠加原理实现相对于经典计算的优越性。我们知道，经典计算机进行计算的基本载体是一个个的二进制比特，它们可以有很多种实现方式，比如开关的闭合与断开，比如晶体管的高低电压，甚至可以是三体游戏里手持白旗和黑旗的秦卒……物理上，这些二进制比特往往是用具有2个水准的某个宏观物理量实现。比如晶体管的高电平代表1、低电平代表0。单个比特每次的输入要么是 0 ，要么是 1 ；多个比特每次的输入也只能是 00...0 到 11...1 当中的某一个，不可能同时实现输入。但是在量子计算机中，比特的载体不再是经典的、宏观的物理量或者状态，而是微观粒子的某个物理量的本征态（比如能级、自旋、偏振等，第2.2节将以自旋为例来做更详细的介绍）。而我们在第一章知道，微观粒子的状态可以是某个物理量本征态的线性叠加，这就使量子计算机具备了通过叠加态“同时”输入多个比特并“同时”计算它们的函数的可能性。假设微观粒子的某个物理量有两个本征态，并且用一个来表示比特 0 ，另一个表示比特 1 ，于是两个本征态就可以表示为  和  ，它们构成一组基底，叫做计算基底或者计算基（computation basis）。而一个量子比特的状态也就可以是  和  这两个计算基底的叠加态： 或者写成列向量形式： 其中，  为复数，且满足归一化条件： 这个性质可以推广到多个量子比特：在经典计算中，单个比特 0 和 1 可以组成多个比特 00...0 到 11...1。量子比特也类似，在多量子比特中，每个比特都有  和  两个基底，而不同比特的  和  的“组合”就构成了多量子比特的基底。比如两个量子比特的基底可以“组合”成四个新的基底： 其中比特  就意味着第1个比特处于计算基底态  ，第二个比特处于计算基底态  上面四个基底也可以写成： 这四个基底和经典比特一样，可以用来表示从00到11的四个二进制数。推广到更多比特，比如 n 个量子比特，那么它们的状态就可以组合成从  到  一共  个基底： 有时候，为了方便表示和推导，我们也将它们写作十进制形式，即： 而多量子比特的状态，也可以是这些基底的叠加态，分别写成二进制和十进制形式就是：  其中，脚下标bin和dec分别表示二进制和十进制。它们也可以写成矩阵形式： 而多量子比特叠加态中各个系数仍然满足归一化条件，即： 现在，我们对量子比特的表示形式以及可能存在的状态有了初步印象，就可以先大致领略一下量子计算的过程了。一个典型的量子计算的过程，其实可以概括为：“输入→变换→测量→输出”的过程：和经典计算机一样，量子计算机的输入和输出都是二进制比特，不同的地方在于对量子比特的处理方式（也就是第二步提到的“变换”），以及对量子比特的测量（也就是第三步）。先简单说说量子比特的变换，这里我们先不介绍具体的变换种类和规则，而是先简单聊一聊它们不同于经典逻辑门的三个典型特征（这里只是抽象地介绍一下，具体内容会在第4章细说）：1) 可逆性：对于量子比特的变换通过各种量子门来实现，而这些量子门和经典计算机中常见的逻辑门相比，有一个本质不同，就是所有的量子门对量子比特的变换都必须是可逆的（我们会在第4.1节讨论这个特点）；2) 不可复制性：此外，经典计算机中常常会涉及到对比特的复制，这是很多函数运算的基础，然而很遗憾的是，在量子计算机中，不存在任何量子变换实现对量子比特的复制（我们会在第4.6节讨论）。3) 对叠加态的操作：经典计算往往通过逻辑门将一组比特变成另一组比特，对应到量子计算中，这就是从一个计算基底到另一个计算基底之间的变换。而量子门可以将量子比特从计算基底态变成不同基底的叠加态，也可以在叠加态上进行函数运算，对叠加态进行操作，使得叠加态中各个基底的系数（振幅）发生改变。不过，在量子计算中，叠加态的信息是无法直接输出的（第4.6节会讨论为什么），而作为计算结果输出的，最终还是一个个计算基底，这就需要对叠加态进行测量，也就是前面提到的第三步。测量后，量子比特的状态将随机坍缩到某个计算基底态上，将这个计算基底输出，才能得到最终的计算结果。也就是说，如果量子比特经过一系列变换后，状态变为： 那么经过测量后、最终输出结果将是  到  中的一个，得到某个  的概率是  了解了量子计算的大致过程后，我们来简单聊一聊，相对于经典计算，量子计算如何实现加速。前面提到，量子计算机由于可以在叠加态上进行函数运算，这意味着，量子计算机仅需要一步就能同时计算某个函数在所有自变量上的函数值。比如，假如某个量子比特经过量子门的一系列变换后，变为： 那么在这个态上计算某个函数  （这也可以利用量子门实现，今后会讨论），将可以一步得到： 这相当于同时计算了从 0 到  一共  个自变量对应的所有函数值。量子计算中，这样的运算性质称作“量子并行性”，而相比之下，经典计算机只能逐个比特计算这些函数值，总共需要  步。正是因为量子并行性，量子计算才具有了在运算速度上对经典计算机产生碾压性优势（即所谓的“量子优越性”）的潜力。不过，这里之所以说是“潜力”、而不是直接可用的优势，是因为这些同时运算的结果往往还是叠加态，并不是确定的基底（在量子计算中就意味着它不是一个确定的值）。因此，在计算的最后，还需要对叠加态进行测量，然后随机得到一个基底、也就是一个确定的函数值，但这个值却未必是正确的计算结果。比如式2.35所示的状态，它虽然同时计算了从  到  的所有函数值，但它并不能直接给出  的任何整体信息（比如它无法告诉我们，哪些变量  满足  ）。这听起来有些令人沮丧：量子并行性似乎并不能简单地带来实质性的好处。但其实只要设计一些精巧的算法，并行运算的潜力还是能转化为真正加速运算的优势的。而这些量子算法的典型思路，可以概括为一句话：将答案写进叠加态中各基底的系数里。因为决定测量结果出现概率高低的，是各个基底前面的系数，让答案对应的比特前面那个系数尽量接近1、甚至完全等于1，那么这个算法就成功了。比如一些典型的量子算法，就是将函数  的信息“转移”到各个基底前面系数里，然后设计算法，让目标值对应的那个基底的系数达到最大，尽量接近1、甚至在有些特殊算法中等于1。举个例子，假设有一个  位量子比特的函数  ，它的定义域为  。现在假设某个算法的目标是找到函数值  的那个自变量  （假设只有一个自变量满足这个条件）。在经典计算中，如果  没有解析式，不能通过数学方法来计算最大值，那么人们只能调用一个包含了  信息的函数模块，来逐个查询各个  的值，最终找到目标。但是，在量子计算中，同样是调用包含了  信息的模块，我们却可以用它对自变量比特的整个叠加态进行操作，从而改变叠加态中各个计算基底的系数。而算法最终要得到的状态中： 系数  的模方  将远大于其他系数的模方，甚至非常接近1，这样一来，最终测量的时候，就有很大概率得到目标值对应的基底  。这个算法就是我们后面将要介绍的Grover搜索算法，我们将看到，它相对于经典计算逐个自变量查询的“暴力搜索”法，可以实现平方加速（将经典计算中需要  级别的复杂度缩短到  级别的复杂度，具体会在第2.5节介绍）。当然，在见到具体的量子算法案例之前，这段叙述始终会显得抽象和笼统，我们也无法想象如何对叠加态系数进行操作。不过不必着急，我们很快会在本章内（第2.5节）欣赏到包括Grover搜索算法在内的几个典型量子算法的思路，来粗略体验如何将并行计算的潜力转化为实际优势。而在本系列的后半部分，我们还会看到它们的具体细节，从中感受这些算法发明者巧夺天工的设计。而这些量子算法的具体实现，需要各种量子门以及由它们组成的量子电路，就像经典计算机中算法的具体实现需要逻辑门以及由此组成的逻辑电路一样。这些量子门和量子电路也可以表示成直观的图示，接下来我们就先通过图示认识一下量子电路的典型构造。和经典计算机的逻辑电路相同的是，量子电路也是由一条一条的横线表示比特位，横线的左端代表输入，横线的右边代表输出，中间用不同的图形符号表示量子门对各个比特的作用。图2.3是一个典型的经典逻辑电路，图2.4是一个典型的量子逻辑电路（这里只需要直观认识一下量子电路的典型构造，而暂时不用深究其中各个量子门的具体含义作用）。不过，与经典逻辑电路不同的是，量子电路中，比特数量不会在运算过程中增多或减少。比如图2.3所示的经典逻辑电路中，与门和异或门都是两个输入一个输出，比特数量减少；而比特a, b在运算过程中都有复制操作，一个比特分裂成相同的两个，这个操作中比特数量增多；而在图2.4所示的量子电路中，输入和输出的数量总是一致的（这和前面提到的量子门的可逆性和量子比特不可复制定理有关，我们在第4章还会具体介绍），因此量子电路中，各个比特位总是呈现为一条条从左到右贯穿到底的平行线。而在量子电路的最后，为了得到最终的计算结果，我们还需要对需要输出的比特进行测量，也就是图2.4中所示的测量符号：最后在需要输出的比特右端得到最终的输出结果（用双横线表示），就完成整个量子计算的过程。前面介绍量子算法如何加速计算的时候曾经提到，在一些典型的量子算法中，我们往往会调用某些包含某种函数信息的模块，来改变量子比特叠加态中各个计算基底的振幅。在量子电路中，这些函数模块其实也是由一些简单的量子门组合构造而成的（就像我们第2.1节讨论的用基础逻辑门实现任意函数运算一样），这样的模块称作“黑盒子”，用一个带有字母的方框来代替。比如图2.5是今后将要介绍的Deutsch-Jozsa算法的量子电路图，它的任务是探寻某个函数  的某种性质，其中标注有  的方框就是包含  信息的黑盒子。此外，在一个典型的量子电路中，量子比特的线路往往会被分成两组或多组，每组比特将扮演不同的“角色”，我们也用不同的字母来区分它们。比如图2.5所示的电路中，量子比特就由两组“角色”不同的比特构成：第一组有  位比特，标记为  到  ，用于 n 位二进制变量  的输入以及最终计算结果的输出；第二组是一个单比特，标记为  ，简单来说用于“存储”和“转运”变量  的函数  的信息，称为辅助比特。这个量子电路最终只对第一组比特、也就是  到  进行测量，然后通过测量结果来判断函数  的某种性质（第2.5节会有一个简单的介绍）。此外，对于属于同一组的多个比特，有时候也会采用缩写形式，将其表示为一条线路加上斜杠、并且标注上比特的位数，比如图2.5中比特  到  就可以简化为图2.6的形式。关于量子电路的介绍这里就暂时先打住，正如前面所说，我们现在只需要直观了解一下量子电路的典型结构，而不用去理解其中所代表的计算过程，这些事情我们会在将来慢慢去做。本节中，我们先认识了量子计算机的载体：量子比特，并且看到了它和经典比特的最大不同之处：它可以处于不同计算基底（类比于经典二进制比特对应的状态）的叠加态。而接下来，我们笼统地认识了典型的量子计算的过程，并且提到了量子计算最重要的特征：可以在叠加态上进行计算，即所谓“量子并行性”。然后我们简单而抽象地介绍了量子并行性如何实现量子优越性，即量子计算机相对于经典计算机在某些算法问题上的加速，并将实现量子优越性的过程概括成了一句话：将答案写进叠加态的系数里。最后，我们简单认识了实现量子算法的量子电路的典型构造以及表示方式，不过这里我们仅仅是对量子电路有一个第一印象，它涉及的运算过程将在第4章介绍。