日志

转量子优化聚类算法

已有 795 次阅读2016-4-13 22:30 |个人分类:转贴|系统分类:学习体会

量子优化算法最本质的特征就是利用了量子态(quantum state)的叠加性(superposition)和相干性(coherence)，以及量子位(qubit)之间的纠缠性(entanglement)。它是量子力学直接进入算法领域的产物，它和其他经典算法最本质的区别就在于它具有量子并行性(parallelism) o

我们也可以从概率算法去认识量子算法。在概率算法中，系统不再处于一个固定的状态，而是对应于各个可能状态有一个几率，即状态几率矢量。如果知道初始状态几率矢量和状态转移矩阵。通过状态几率矢量和状态转移矩阵相乘可以得到任何时刻的几率矢量。量子算法与此类似，只不过需要考虑量子态的几率幅。因为它们是平方归一的，所以几率幅度相对于经典几率有橱倍的放大，状态转移矩阵则用Walsh Hadamard变换、旋转相位操作等酉正变换实现。

量子力学是反映微观物质世界运动规律的理论，是对客观存在的一种数学模拟和理论刻画。在经典力学中，一个力学系统的状态可以由其具体位置:和动量P来表述，并服从牛顿运动定律。在量子力学中，由于微观粒子具有的波粒二象性，其运动规律只能以概率的形式表述。因为宏观运动是大量微观粒子相互作用的整体体现，所以宏观物体状态变量及其规律，也可以结合微观粒子特征后，可用于对微观粒子系统描述。

量子力学用希尔伯特(Hilbert)空间的波函数来描述微观粒子的状态，波函数本身不是力学变量，也不具有任何经典物理量的意义，而是用来刻画具体量子力学量的各种可能值和出现这些可能值的概率。应用波函数，可以找到与经典力学对应的量子变量。

量子退火用于最优化的思想虽源于模拟退火，但其理论依据却完全不同，量子退火是利用量子跃迁的隧道效应的机制，而模拟退火是基于热力学的退火原理。量子退火的过程对应于模拟退火中的热力学转移，它可以利用两种方法来研究一时间度量的薛定愕等式和量子蒙特卡洛(Monte Carlo)原理，这两个动力系统实际上是等效的，但是这两个方法都可以找到最优解，而且速度均比模拟退火法快，找到最优解的概率要远大于模拟退火法。

目前，量子退火在最优化问题研究中取得了很大的进步，并逐渐开始在实际问题中的得到应用。与模拟退火方法相比较，量子退火在退火收敛速度和避免陷

入局部极值方面有一定优势，这主要是因为量子的隧道效应使得粒子能够穿过比其自身能量高的势垒直接达到低能量状态。

Deutsch指出利用量子态的相干性可以实现并行量子计算[[zi] 0 1994年PeterShor就提出了分解大数质因子的量子Shor算法[[zz]，它仅需几分钟就可以完成用1600台经典计算机需要250天才能完成的RSA-129问题(一种公钥密码系统)。使当前公认为最安全的经典计算机不能破译的公钥系统RSA[lo]，可以用量子计算机容易的破译。19%年Grower提出量子Grower搜索算法证明量子计算机在穷尽搜索问题中比经典计算机有。(而)的加速。

Grower算法是最能体现量子并行性的算法，也是搜索算法中最快的算法。利用量子计算巨大的并行性，它可以很容易的实现对所有可能状态的穷尽搜索，解决所有求解困难而验证容易的NP问题[[11]，遍历搜索的目的是从一个杂乱无序的集合中找到满足某种要求的元素，要验证一个元素满足要求容易，但反过来，查找合乎要求的元素则往往要大费周折，因为这些元素可能并没有按照这种要求有序的进行排列，并且这些元素的数目又很大，在经典算法中，只有逐个试验，“遍历搜索”，显然，运算步骤和被搜索集合元素数N成正比，若该集合中只有一个元素符合要求，为使搜索成功率达到100%，一般说来步骤数要接近N，而在Grower算法中，搜索成功的运算步骤只与橱成正比〔iz]，它对状态空间的快速搜索是通过概率幅的求反放大实现的，由此可以设想，它对优化问题也能构成快速搜索，使用改进的Grower算法可以使它不仅可以解简单的决策问题，而且可以在并行计算函数值的同时，使高函数值状态凸现出来[[13]，即解决优化问题，而算法的参数可以用经典算法学习。

聚类分析(Clustering Analysis)是研究如何用数学的方法将一组样品、对象、指标、属性进行分类的方法，聚类算法包括统计算法、机器学习方法、神经网络方法和面向数据库的方法等，聚类是模式识别中一个重要的问题。目前我们常用的聚类方法是基于距离的分割聚类算法，它仅仅根据数据间的几何相似性进行分类，是一种无监督的学习方法，所以，一般说来，它的效果并不如人意。而且在现有的聚类算法中聚类数目一般需要事先指定，如Kohenon自组织算法、K均值算法、模糊C均值聚类算法等。然而，类别数在很多情况下是不可知的，而且各类聚类算法的结果一般都要依赖于初值，即使类别数目保持不变，聚类的结果也相差很大。受到物理学中量子机理和特性的启发，我们可以利用量子理论解决此类问题，一个很好的例子就是基于相关点的Pott自旋和统计机理提出的量子聚类模型，它把聚类问题看作一个物理系统，通过求解一系列随温度变化的自由能函数的全局极小来得到聚类问题的最优解。许多算例均表明，对传统聚类算法无能为力的几种聚类问题，该算法都得到了比较满意的结果。

1990年以后，小波分析同时朝着几个方向发展。1992年，Wicherhauser和Coifman等人沿着频带划分的思想，用一个尺度函数生成一组包括

小波函数在内的“小波包”，实现了全频域的渐细估计，为信号的自适应频带划分提供了工具。
最近，Andreas Klappenecker通过研究指出:在量子计算机上可以实现周期化的小波包变换和小波变换，而且实现周期化的小波包变换要比实现小波变换容易，并且还给出了具体的量子电路的实现方法。假设信号可以用n个量子比特表示，N=2"为输入信号的长度，在经典计算机上，我们需要O(N)步运算来实现小波变换，O(N1ogN)步来实现小波包变换。在量子计算机上，则只需要O(log2 N)个基本量子门运算来实现小波与小波包变换，而且实现小波包算法比小波算法需要更少的计算量。