量子计算的并行性及其哲学意义.pdf

量子计算的并行性及其哲学意义 王凯宁1 摘要：量子计算作为量子力学与计算科学结合的产物，在最近的三十年来受到了众 多物理学家和计算机科学家的广泛关注，并取得了深入的进展。文章从简单介绍了 量子计算的基本过程入手，比较了量子并行计算与经典并行计算的不同，并简略的 思考了量子计算并行性所内涵的哲学意义。 关键词：量子计算；量子逻辑门；量子测量；并行计算 一、 引言 在过去的三十多年来，量子计算作为量子理论与信息科学结合的交叉科学，受到 了众多物理学家和计算机科技人员的广泛关注，不仅因为其是将量子理论应用于解 决实际问题的重要途径，更因为它为物理学家理解量子力学原理提供了深刻的洞察 力。量子计算和量子计算机的概念起源于著名物理学家费曼(Feynman) 。1982年，费 曼制造了一个抽象的模型，该模型示范了如何利用量子系统做运算，这被认为是最 早的量子计算机的思想模型。随后在1985年，牛津大学的Deutsch提出了第一个量子 计算机的设计蓝图、量子计算机的网络模型, 定义了量子Turing机，预言了量子计算 机的潜在能力。1994年Shor证明了大数质因子分解以及离散对数(discrete logarithm) 问题可以用量子计算机很迅速的解决，1995年Grover给出了在一个没有实现排序的数 据库中有哪些信誉好的足球投注网站的问题可以通过量子计算机大大的提高速度的方案。由于这两个问题对 于经典计算机来说是难于解决的，因而这两个量子算法的提出引起了越来越多的物 理学家和计算机科学家对量子计算的重视,将对量子计算理论和技术的研究在世界 范围内推向了高潮。那么，量子计算的原理及其计算方式是怎样的呢？其特点和优 势又是什么呢？ 二、 量子计算过程 从广义上讲，计算是一个物理操作，它可以看作是作为计算仪器的物理系统按 1 王凯宁，男，出生于1984 年，山西大学科技哲学研究中心 电子邮箱：wkn2002@ 联系电话 照设计好的步骤执行的过程。因此，可以将这一过程总结为：“首先输入原始数据， 从物理的角度看这可以解释为在计算系统中制备出一个初始物理态；然后执行计算， 这个过程实际是按照算法规定的步骤，将给定的初始物理态演化成对应输出物理态 的过程；最后输出计算结果，这可以看作对演化的物理末态进行测量得到所需信息 [1] 的过程。” 因此，我们可以对比于经典计算，通过对量子计算中数据的存储，计 算过程和结果的输出这三个单元的分析来讨论量子计算过程。 1、量子位和量子寄存器：信息的存储 经典的电子计算机从物理上可以被看作是对输入信号序列按一定算法进行变换 的机器，其算法由计算机的内部逻辑电路来执行。为了便于通过电路控制数据的存 取和各种运算操作、用二进制数“0”和“1”表示参与运算的各种数和各种逻辑控 制的状态信息，这样的信息存储单元被称作一个二进制的位(Bit)。当存在N 个这样 的存储单元时，就可以存放一个N 位的数据，代表一个由N 位二进制数组成的信息， 这就是一个N 位寄存器。类似于这种二进制的经典计算语形，在一个二进制的量子 计算机中，定义了一个量子位(Qubit)，它是量子计算过程中的信息存储单元。这个 量子位可以像经典计算机中的位一样，处于“0”态或“1”态。但与之不同的是， 由于量子力学中的态具有叠加性，量子位还可以处于“0”态和“1”态的叠加态， 也就是说它既是“0”态又是“1”态。我们可以用狄拉克符号表示一个量子位为： q a 0 +b 1 ， 其中 a 2 + b 2 1 那么，对于两个量子位组成的语形空间，则叠加态为： Ψ q2 ⊗ q1 c0 00 +c1 01 +c2 11 +c3 10 也就是说这个叠加态处于一个22 维的Hilbert空间，其有四个相互正交的基本态： 00 ，01 ， ，11 。 10 因此，定义一个N 位量子寄存器为N 个量子位的有序集合，则它的叠加态为： Ψ qN −1 ⊗ qN −2 ⊗⊗ q0 Ψ 是2N 维的Hilbert空间中的单位向量，它有2N 个相互正交的基本态。 2N −1 2N −1 2 Ψ ∑ci i ， 其中 ∑ci