[科学] 量子计算机

king

　　20世纪60年代至70年代，人们发现能耗会导致计算机中的芯片发热，极大地影响了芯片的集成度，从而限制了计算机的运行速度。研究发现，能耗来源于计算过程中的不可逆操作。那么，是否计算过程必须要用不可逆操作才能完成呢？问题的答案是：所有经典计算机都可以找到一种对应的可逆计算机，而且不影响运算能力。既然计算机中的每一步操作都可以改造为可逆操作，那么在量子力学中，它就可以用一个幺正变换来表示。早期量子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。在经典计算机中，基本信息单位为比特，运算对象是各种比特序列。与此类似，在量子计算机中，基本信息单位是量子比特，运算对象是量子比特序列。所不同的是，量子比特序列不但可以处于各种正交态的叠加态上，而且还可以处于纠缠态上。这些特殊的量子态，不仅提供了量子并行计算的可能，而且还将带来许多奇妙的性质。与经典计算机不同，量子计算机可以做任意的幺正变换，在得到输出态后，进行测量得出计算结果。因此，量子计算对经典计算作了极大的扩充，在数学形式上，经典计算可看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时完成，并按一定的概率幅叠加起来，给出结果，这种计算称作量子并行计算。除了进行并行计算外，量子计算机的另一重要用途是模拟量子系统，这项工作是经典计算机无法胜任的


　　无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。遗憾的是，在实际系统中量子相干性很难保持。在量子计算机中，量子比特不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干。因此，要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。量子纠错码是经典纠错码的类比，是目前研究的最多的一类编码，其优点为适用范围广，缺点是效率不高


　　迄今为止，世界上还没有真正意义上的量子计算机。但是，世界各地的许多实验室正在以巨大的热情追寻着这个梦想。如何实现量子计算，方案并不少，问题是在实验上实现对微观量子态的操纵确实太困难了。目前已经提出的方案主要利用了原子和光腔相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。现在还很难说哪一种方案更有前景，只是量子点方案和超导约瑟夫森结方案更适合集成化和小型化。将来也许现有的方案都派不上用场，最后脱颖而出的是一种全新的设计，而这种新设计又是以某种新材料为基础，就像半导体材料对于电子计算机一样。研究量子计算机的目的不是要用它来取代现有的计算机。量子计算机使计算的概念焕然一新，这是量子计算机与其他计算机如光计算机和生物计算机等的不同之处。量子计算机的作用远不止是解决一些经典计算机无法解决的问题

king

http://www.physixfan.com/archives/158

量子计算的概念，最早是由费恩曼提出的，从那以后计算机科学家们已经在这个领域里有了不小的进展。量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。量子计算机的基本特征之一，就是它使用的信息单元不是比特，而是量子比特（qubit）。量子比特可以是电子那样的粒子。可以让自旋向上代表1，自旋向下代表0。与传统计算机不同的是，电子可以处于自旋向上和向下的叠加态，即1和0的叠加态。处于叠加态的少量粒子可以携带大量信息。假如我们可以控制仅仅1000个量子比特，那我们也可以用之表示出从1到2^1000的所有数字，并且可以同时对所有数字进行操作，也就是所谓的并行计算。虽然当我们最终读取量子状态时，只能从2^1000个状态中随机的读取其中的一个，而其他的状态都会消失，但是我们可以通过对粒子进行巧妙的处理，用量子计算机求解一些普通计算机没法有效求解的问题，例如对大数分解质因数。用现有的计算机需要花10亿年才能算出来的题，可能用量子计算机花不到一年的就能成功解决。

正是因为用量子计算机可以非常有效的解决对大数分解质因数的问题，现在的密码安全将在不久的将来量子计算机问世的时候轰然瓦解。现在最常用的加密方法当属RSA公钥算法，这个算法就是基于“把两个大质数相乘极为简单，但是要把这个乘积分解为这两个大质数则几乎无法做到”这一事实，具体的算法可以参见《算法导论》有关章节。有了量子计算机的话，我们就不得不重新设计一种量子计算机也无法完成的运算了。

很多人对量子计算机有所误解，认为它可以解决一切困难的数学问题。事实不是如此，量子计算机能解决的问题，也仅仅是一小部分特殊问题。计算机科学家已经证明了，传统计算机能够有效解决的所有问题，用量子计算机同样能够有效解决。但是，对于计算机科学领域里的一类非常重要的问题——NPC问题，量子计算机和普通计算机一样是无能为力的。生活和生产中有很多极为重要的问题不幸属于NPC类。虽然我们还没有真正证明量子计算机不能胜任，正如我们还无法证明P到底等不等于NP一样，但是无数失败的尝试表明，量子计算机在这类问题上比普通计算机好不到哪里去。（如果你第一次听说P、NP、NPC，那么我建议你看一看Matrix67的这篇文章，那里有比较详细系统的介绍。简单来说：P是多项式级时间复杂度能找到解的问题，即所说的普通计算机能够“有效解决”的问题；NP是多项式时间复杂度内可以验证解的正确性的问题，但不一定能在多项式级时间复杂度内找到解；所有的NP问题都可以归约到NPC问题，即一旦解决了一个NPC问题则所有NP问题随之解决）。我们称量子计算机能够有效解决的问题为BQP类问题，这几类问题之间的关系如下图：