量子聚类算法分析与研究

量子聚类算法分析与研究(论文12000字)
摘要：量子聚类算法是在经典聚类算法的基础上发展起来的新型算法。它采用量子的方法来对经典的聚类算法进行改写，从而解决经典聚类算法在处理大数据高维度数据时出现的速度慢，耗能大的问题，为经典聚类算法带来指数级的加速。本文首先介绍了基础知识，包括经典聚类算法和量子计算。之后我们在深入研究量子聚类算法的基础上，提出了一种基于最近距离的量子k-means算法，通过在待分类点和聚类中心之间添加辅助量子构成纠缠态，对辅助量子进行测量从而计算两点之间的距离。最后我们研究了基于近邻距离的量子聚类算法，并对其中的一步进行了改进。通过对样本点进行聚类来缩小近邻点的搜索范围，从而为算法带来了加速。
关键词：聚类算法；量子计算；k-means算法；k-近邻算法；指数加速
 
Analysis and Research on Quantum Clustering Algorithm
Abstract：Quantum clustering algorithm is a new algorithm developed on the basis of the classical clustering algorithm. It use quantum method to rewrite the clustering algorithm to solve the problem of slow speed and expensive cost when dealing with large amounts of data in high dimension. And bring exponential acceleration for classical clustering algorithm. In this paper, we first introduce basic knowledge, including the classical clustering algorithm and quantum computing. After that, on the basis of the further study of quantum clustering algorithm , we proposes a quantum k-means algorithm based on the nearest distance. We construct the entanglement state of the centroid of cluster and the point to be classified, an auxiliaryparticle is adjoined. Then we measure the auxiliaryparticle and then get the distance between two points. Finally, we study the quantum clustering algorithm based on nearest neighbor and give out some improvement. By clustering sample points, we reduce the search scope of neighboring points, thus bring algorithm acceleration.
Keywords: clustering algorithm; quantum computing; k-means algorithm; k-nearest-neighbor algorithm; exponential acceleration

目录
摘要    1
Abstract    2
1 绪论    3
2 基础知识简介    4
2.1 量子理论发展概述    4
2.2 量子计算术语    4
2.2.1量子叠加    4
2.2.2 量子纠缠    4
2.2.3 量子比特    5
2.2.4 量子逻辑门    5
2.3经典的机器学习聚类算法    6
2.3.1 k-means聚类算法    7
2.3.2 k-近邻聚类算法    8
2.3.3 决策树算法    8
3量子聚类算法概述    9
3.1量子流形嵌入    10
3.2量子层次聚类    10
3.3基于最近距离的量子聚类算法    11
4 基于最近距离的量子k-means算法    11
4.1空间中点与距离的量子表示    11
4.2算法步骤    12
4.3效率分析    14
5 基于近邻距离的量子聚类算法及其改进    15
5.1 Wiebe算法回顾    15
5.1.1 假设    16
5.1.2 算法步骤    16
5.2改进的Wiebe算法设计    18
5.2.1 算法思想    18
5.2.2 算法详细步骤    19
5.2.3 效率分析    20
6 总结与展望    21
参考文献：    21
致谢    23