量子计算简述_量子并行计算

1、量子概念

1.1、定义

量子(Quantum)属于一个微观的物理概念。如果一个物理量存在最小的不可分割的基本单位[1]，那么称这个物理量是可量子化的，并把物理量的基本单位称为量子。现代物理中，将微观世界中所有的不可分割的微观粒子（光子、电子、原子等）或其状态等物理量统称为量子。
量子这个数学概念的意思究竟是什么呢？就是“离散变化的最小单元”。
量子这个概念最早由德国物理学家普朗克在1900年提出的，他假设黑体辐射中的辐射能量是不连续的，只能取能量基本单位的整数倍，这很好地解释了黑体辐射的实验现象。即假设对于一定频率的电磁辐射，物体只以“量子”的方式吸收和发射。

量子假设的提出有力地冲击了牛顿力学为代表的经典物理学，促进物理学进入微观层面，奠定了现代物理学基础，进入了全新的领域
经典力学中的概率反映的是信息的缺乏，可以通过减少这些因素的干扰来增强预测能力。而量子力学的概率是一种本质的随机性。

1.2、基本性质

1.2.1、量子测不准（不确定关系）

也称为不确定性原理，即观察者不可能同时知道一个粒子的位置和它的速度，粒子位置的总是以一定的概率存在某一个不同的地方，而对未知状态系统的每一次测量都必将改变系统原来的状态。也就是说，测量后的微粒相比于测量之前，必然会产生变化。

1.2.2、量子不可克隆

量子不可克隆原理，即一个未知的量子态不能被完全地克隆。在量子力学中，不存在这样一个物理过程：实现对一个未知量子态的精确复制，使得每个复制态与初始量子态完全相同。

1.2.3、量子不可区分

量子不可区分原理，即不可能同时精确测量两个非正交量子态。事实上，由于非正交量子态具有不可区分性，无论采用任何测量方法，测量结果的都会有错误。

1.2.4、量子态叠加(superposition)

量子状态可以叠加，因此量子信息也是可以叠加的。这是量子计算中的可以实现并行性的重要基础，即可以同时输入和操作个量子比特的叠加态。

1.2.5、量子态纠缠(entanglement)

两个及以上的量子在特定的(温度、磁场)环境下可以处于较稳定的量子纠缠状态，基于这种纠缠，某个粒子的作用将会瞬时地影响另一个粒子。爱因斯坦称其为: “幽灵般的超距作用”。
在量子力学中，体系的状态可以用一个函数来表示，称为“态函数”（是的，你既可以把它理解为一个函数，也可以把它理解为一个矢量，两者不矛盾，怎么方便怎么来）。单粒子体系的态函数是一元函数，多粒子体系的态函数是多元函数。如果这个多元函数可以分离变量，也就是可以写成多个一元函数直接的乘积，我们就把它称为“直积态”。如果它不能分离变量，我们就把它称为“纠缠态”。
如：F(x, y) = xy + 1，就可以说X和Y是纠缠的
用一个态(|01> + |10>)/√2作例子，我们可以把它记为|β01>。这个态的特点是，你对它测量粒子1的状态，会以一半的概率发现粒子1处于|0>，粒子2处于|1>，另一半概率发现粒子1处于|1>，粒子2处于|0>。你无法预测单次测量的结果，但你可以确定，粒子1变成什么，粒子2就同时变成了相反的状态。

1.2.6、量子态相干性(interference)

量子力学中微观粒子间的相互叠加作用能产生类似经典力学中光的干涉现象。

1.3、量子信息

量子力学有一条基本原理叫做“叠加原理”：如果两个状态是一个体系允许出现的状态，那么它们的任意线性叠加也是这个体系允许出现的状态。
利用微观粒子状态表示的信息称为量子信息。量子比特(quantum bit或qubit)是量子信息的载体，它有两个可能的状态，一般记为|0>和|1>，对应经典信息里的0和1。状态和是二维复向量空间中的单位向量，它们构成了这个向量空间的一组标准正交基。量子比特的状态是用一个叠加态表示的，
如: |$\phi$>=$\alpha$|0>+$\beta$|1> ，其中${\alpha }^2+{\beta }^2=1$
叠加原理说的是：如果一个体系能够处于|0>和处于|1>，那么它也能处于任何一个a|0> + b|1>，这样的状态称为“叠加态”。
而且测量结果为|0>态的概率是${\alpha }^2$，而得到|1>态的概率是${\beta }^2$。这说明一个量子比特能够处于既不是|0>又不是|1>的状态上，而是处于|0>和|1>的一个线性组合的所谓中间状态之上。经典信息可表示为011000，而量子信息可表示为|${\phi }_1$>|${\phi }_2$>|${\phi }_3$>

• 经典比特是“开关”，只有开和关两个状态（0和1），而量子比特是“旋钮”，就像收音机上调频的旋钮那样，有无穷多个状态（所有的a|0> + b|1>）。显然，旋钮的信息量比开关大得多。

一个经典的二进制存储器只能存一个数：要么存 0，要么存 1。但一个二进制量子存储器却可以同时存储0和1这两个数。两个经典二进制存储器只能存储以下四个数的一个数: 00，01，10 或 11。倘若使用两个二进制量子存储器，则以上四个数可以同时被存储下来。按此规律，推广到N个二进制存储器的情况，理论上，N个量子存储器与N个经典存储器分别能够存储个$2^N$数和1个数。由此可见，量子存储器的存储能力是呈指数增长的，它比经典存储器具有更强大的存储数据的能力，尤其是当 N 很大时(如 N=250 )，量子存储器能够存储的数据量比宇宙中所有原子的数目还要多。

1.4、量子门

在量子计算，特别是量子线路的计算模型里面，一个量子门 (Quantum gate，或量子逻辑门)是一个基本的，操作一个小数量量子比特的量子线路 。它是量子线路的基础，就像传统逻辑门跟一般数字线路之间的关系。
与多数传统逻辑门不同，量子逻辑门是可逆的。 然而，传统的计算可以只使用可逆的门表示· 举例来说，可逆的Toffoli门 可以实做所有的布尔函数。 这个门有一个直接等同的量子门，也因此代表量子线路可以模拟所有传统线路的操作。
量子逻辑门使用酉矩阵表示。 就像常见的逻辑门一般是针对一个或两个比特进行操作，常见的量子门也是针对一个或两个量子比特进行操作。 这也代表这一些量子门可以以2 × 2或者4 × 4的酉矩阵表示。
量子门常使用矩阵表示，操作K个量子比特的门可以用2k x 2k 的酉矩阵表示。 一个门输入跟输出的量子比特数量必须要相等。 量子门的操作可以用代表量子门的矩阵与代表量子比特状态的向量作相乘来表示。
例如：
阿达马门
阿达马门是只对一个一个量子比特进行操作的门。 这个门将基本状态 |0> 变成 $\frac{|0>+|1>}{\sqrt{2}}$ ，并且将 |1> 变成 $\frac{|0>-|1>}{\sqrt{2}}$ 。这个门可以以阿达马矩阵表示：

H = 1 2 ( a b c d ) H=\frac{1}{\sqrt{2}}\bigl(

$$\begin{matrix} a & b \\ c & d \end{matrix}$$ \bigr) H=2 ​1​(ac​bd​)

因为矩阵的每一列正交，因此H 是一个酉矩阵。

1.5、量子并行计算原理

由于量子比特可以同时处于两种状态的叠加态，所以量子门操纵它时，实际上同时操纵了其中的两种状态。
所以，若一个量子计算机同时操纵N个量子比特，那么它实际上可以同时操纵$2^N$个状态，其中每个状态都是一个N位的经典比特。这就是量子计算机的并行计算能力。

2、典型量子算法

2.1、Shor算法

大整数素因子分解难题指的是：将两个大的质因子p1、p2相乘容易，N=p1*p2，但是将它们相乘的结果分解为两个素因子十分困难。经典算法求解该问题时计算复杂度会随着问题的规模指数增长，目前最有效的传统求解方法复杂度为：
O(exp[$n^{1/3}(logn{)}^{2/3}$])
众所周知，RSA公钥密码正是基于这样的一个数学难题。
1994年，应用数学家Shor 提出了一个实用的量子算法，通常称为Shor算法。它的出现使得大整数分解问题在量子计算机中在多项式时间内解决成为可能，它计算复杂度仅为
O($n^2$(logn)(loglogn))。
显然，相比经典算法，Shor算法相当于进行了指数加速。算法主要思想是将整数质因子分解问题转化为求解量子傅里叶变换的周期，将多个输入制备为量子态叠加，进行并行处理和操作，从而到到了量子加速的目的。
在实际应用中， 2001年，IBM公司的研究小组首次在开发的核磁共振（Nuclear magnetic resonance，NMR）量子计算机中使用Shor算法，成功将15分解成3×5，这一成果引起业界广泛的关注和讨论。理论上，一旦更多量子比特的量子计算机研究成功，对于1000位大整数，采用 Shor算法可以在不到1秒内即可进行素因子分解，而采用传统计算机分解需要年（而宇宙的年龄为年）。由此可见在量子计算机面前，现有的公开密钥 RSA体系不再安全。

2.2、Grove算法

搜索问题指的是从个未分类的元素中寻找出某个特定的元素。对于该问题，经典算法逐个地进行搜寻，直到找到满足的元素为止，平均需要N/2,时间复杂度为O(N)
1996年，计算机科学家Grover在提出一个量子搜索算法，通常称为Grover算法。采用该量子算法进行搜索仅需$\left(\frac{\pi }{4}\right)\sqrt{N}$次,复杂度为O($\sqrt{N}$)。相比传统算法，它进行了二次加速，再次体现了量子计算并行带来的高效优势。举一个直观的例子，若要从有着100万个号码的电话本中找出某个人的号码。经典方法是逐个地进行搜索，平均需要搜索50万次才能找到正确的号码。而采用Grover的量子算法，它会首先将100万个号码制备为量子叠加态。然后在制备的量子叠加态上通过反复执行量子操作的迭代，每一次迭代，它将放大正确的态（寻找的电话号码）的概率，同时减少非正确的态的概率。当进行$\left(\frac{\pi }{4}\right)\sqrt{10^6}\approx 785$次后，正确态的概率接近于1，此时去测量，可以正确态的结果，从而得到查找的电话号码。
由于很多问题都可以看作一个搜索问题，如寻找对称密码(DES/AES等)的正确密钥，搜索方程的最佳参数等，因此Grover算法的用途十分广泛。

2.3、HHL算法

求解线性方程是一个基本的数学的问题，在工程等领域有重要的广泛。对于方程，其中A是N*N矩阵，是N维向量，求解N维未知向量。若采用 Gauss 消元法可以在$O(N^3)$时间内求解。
2008年，Harrow、Hassidim A和Lloyd S三位学者提出了一种可以在$O(lo{g}_2(N))$时间内求解线性方程组的量子算法[14]，通常称为HHL算法。同样地，需要将多个输入制备为量子态叠加，从而进行量子并行操作。
由于机器学习算法中的某些求参过程同样可看作是该类问题，因此学者们已经将 HHL 算法应用到机器学习领域，比如 K-means 聚类,支持向量机，数据拟合等算法中，从而达到加速的目的。

2.4、量子机器学习与深度学习算法

在量子算法中，有一类算法是应用在机器学习或深度学习领域。由于近年来人工智能和机器学习/深度学习的研究热潮，同样带动了量子机器学习/深度学习的发展和研究。

众所周知，传统的机器学习/深度学习算法仍然面临计算瓶颈的挑战。然而，若充分利用量子计算的并行性，则可以进一步优化传统机器学习算法的效率，突破计算瓶颈，加速人工智能进程。量子机器学习的研究可追溯到1995年，Kak最先提出量子神经计算的概念。相继学者们提出了量子聚类、量子深度学习和量子向量机等算法。2015年，潘建伟教授团队在小型光量子计算机上，首次实现了量子机器学习算法。
从经典—量子的二元概念出发可以将机器学习问题按照数据和算法类型的不同分为4类，如表1所示。

表1 机器学习分类

量子机器学习的训练数据必须以某种可以为量子计算机识别的格式载入（即制备量子叠加态），经过量子机器学习算法处理以后形成输出，而此时的输出结果是量子叠加态的，需要经过测量得到最终结果，该流程如图1（量子机器学习的基本流程）所示。

表2概述了目前文献中见到的一些典型量子机器学习算法，及其所需资源和性能改善特征。
表2 主要量子机器学习算法

• 如前所述，量子机器学习算法相比经典算法，有以下显著优势：

(1) 量子加速。由于量子态的可叠加性，相比传统计算机，量子算法可以在不增加硬件的基础上实现并行计算，在此基础上利用Shor算法、HHL算法和Grover搜索等算法，可实现相对于完成同样功能的经典算法的二次甚至指数加速。

(2) 节省内存空间。将经典数据通过制备量子态叠加编码为量子数据，并利用量子并行性进行存储，可实现指数级地节省存储硬件需求。

3、量子计算机

所谓量子计算机，它是指具有量子计算能力的物理设备。为什么要出现这种设备呢？主要有两个原因：(1) 外部原因：摩尔定律失效。根据摩尔定律，集成电路上可容纳的晶体管数目每隔24个月增加一倍，性能也相应增加一倍。然而，一方面随着芯片元件集成度的提高会导致单位体积内散热增加，由于材料散热速度有限，就会出现计算速度上限，产生“热耗效应”。另一方面元件尺寸的不断缩小，在纳米甚至埃尺度下经典世界的物理规律不再适用，出现“尺寸效应”。(2) 内部原因：量子计算机的强并行性。这是量子计算机相比传统计算机的显著优势，量子计算机和量子算法相互结合，可以将计算效率进行二倍加速甚至指数加速，例如传统计算机计算需要1年的任务，使用量子计算机可能需要不足1秒的时间。

不同于传统计算机，量子计算机用来存储数据的对象是量子比特；不同于传统计算机，量子计算机用使用量子逻辑门进行信息操作，如对单个量子操作的逻辑门：泡利-X门，泡利-Y门，泡利-Z门和Hadamard门等；对两个量子操作的双量子逻辑门：受控非门CNOT，受控互换门SWAP等等。

这些量子的逻辑门的操作可以看做一种矩阵变换，即乘以幺正矩阵（可看做正交矩阵从实数域推广到复数域）的过程。图10以Hadamard门为例，表述了对量子态|0>的形象操作过程。

由图可知，Hadamard门可以将一个量子态变成两个量子态的叠加状态。形象地说，猫生的状态通过Hadamard门转换成生和死的叠加态（概率为状态幅度的平方，概率各为50%）。这种性质十分有用，是实现并行计算基础，可以将N个输入数据转换成一个叠加的量子态，一次量子计算操作，相当于进行了N个数据操作，即实现了N次的并行，后文提到的量子算法正是利用这些量子逻辑门的变换特性。其他量子逻辑门的幺正矩阵有所不同，但操作也类似，这里不做赘述。

此外，量子计算机用使用的量子逻辑门是可逆的；而传统计算机的逻辑门一般是不可逆的。前者操作后产生的能量耗散，而后者进行幺正矩阵变换可实现可逆计算，它几乎不会产生额外的热量，从而解决能耗上的问题。与传统的计算机相同的是，量子计算机的理论模型仍然是图灵机。不同的是，量子计算目前并没有操作系统，代替用量子算法进行控制，这决定了目前的量子计算机并不是通用的计算机，而属于某种量子算法的专用计算机。量子计算机和传统计算机的比较结果如表3所示。

表3 量子计算机VS 传统计算机

量子计算机的基本原理如图11所示。它主要的过程如下：
(1) 选择合适的量子算法，将待解决问题编程为适应量子计算的问题。
(2) 将输入的经典数据制备为量子叠加态。
(3) 在量子计算机中，通过量子算法的操作步骤，将输入的量子态进行多次幺正操作，最终得到量子末态。
(4) 对量子末态进行特殊的测量，得到经典的输出结果。

迄今为止，科学家用来尝试实现量子计算机的硬件系统有许多种，包括液态核磁共振、离子阱、线性光学、超导、半导体量子点等。其中，超导和半导体量子点由于可集乘度高，容错性好等优点，目前被认为是实现量子计算机的两种可能方案[1]。最近，IBM宣布的研制50比特和谷歌研制的72比特量子计算机都是基于低温超导系统的方案。

   $ umask  
      0022##表示拥有者（u）不用去掉权限，其他两个去掉w（写）
1
2