作为计算机科学和统计学的交叉子领域,数据挖掘旨在从大量数据中挖掘出其中隐藏的重要信息,是知识发现的关键步骤。此外,数据挖掘可用于挖掘密码系统中明密文隐藏的模式以分析其安全性,因此也是密码分析的一个重要工具。然而,随着信息技术的高速发展,全球数据总量每年指数增长,这使得经典数据挖掘算法未来处理大数据时将面临计算性能的巨大挑战。量子计算利用量子力学基本原理(如量子叠加和量子纠缠)实现计算任务,在解决某些特定问题上相比经典计算具有显著的速度优势。例如,Shor量子算法能够快速分解大数因子,相对经典算法具有指数加速,对被广泛应用的RSA密码系统安全构成严重威胁。近年来,量子计算已被应用到数据挖掘领域,且解决多种数据挖掘问题的高效量子算法已被提出。然而,量子数据挖掘算法研究仍处于初始阶段,许多数据挖掘问题尚无高效量子算法解决。本文对此展开进一步研究,针对若干重要的数据挖掘问题,提出相比经典算法具有显著加速的量子算法。这些量子数据挖掘算法也将为密码分析量子算法研究提供重要参考。具体来说,本文研究包括以下四个方面。1、针对关联规则挖掘的核心任务——从候选项集中找出频繁项集,提出一个量子关联规则挖掘算法。具体来说,对于Mc(k)个候选k项集中存在Mf(k)个频繁k项集(Mf(k)≤Mc(l))的情况,所提算法通过并行幅度估计和幅度放大能够有效地挖掘出这些频繁k项集并估计它们的支持度。该算法的复杂度为O(k(?),其中ε为支持度估计误差。与复杂度为O(kMk)/ε2)的经典算法相比,所提量子算法当Mf(k)<<Mc(k)时关于ε和Mc(k)均有平方加速,而当Mf(k)≈Mc(k)时仅关于ε具有平方加速。2、基于最著名的主成分分析数据降维算法,提出一个量子数据降维算法。该算法以量子并行的方式将一个高维数据集投影到低维空间从而获得相应的低维数据集。与经典算法相比,当低维空间维数d和原高维空间维数满足d=O(polylog D)时该算法具有指数加速效果。此外,该算法能够被用于两个重要的量子机器学习算法:量子支持向量机和量子线性冋归预测,使其摆脱“数据灾难”。3、针对岭回归——一种通过对一般线性回归引入规范化以分析多重共线性数据的线性回归方法,提出一个量子岭回归算法。通过设计并行哈密顿量模拟技术,该算法给出一个能高效估计岭回归预测性能的量子K重交叉验证方法。整个算法首先利用量子K重交叉验证方法确定一个好的岭回归参数使岭回归在该参数下具有很好的预测性能,然后产生一个幅度编码了该岭回归参数下岭回归最优拟合参数的量子态,且该量子态可用于预测新数据。由于使用稠密哈密顿量模拟技术作为基础,该算法能够处理稠密数据矩阵。相对经典算法,当数据矩阵条件数k与其维数N满足k=O(polylogN)时,该算法具有指数加速效果。当k大到使数据矩阵满秩或者近似满秩时,具有多项式加速效果。4、基于近年提出的一个知名经典视觉追踪算法,提出一个量子视觉追踪算法。该算法包括两个阶段:训练和探测。在训练阶段,为了区分目标和背景,训练一个以量子态形式呈现的岭回归分类器,其中岭回归最佳拟合参数被编码到该量子态幅度上。在探测阶段,利用该分类器产生一个幅度编码了所有候选图像块的岭回归响应的量子态。与经典算法相比,当训练阶段、探测阶段图像数据矩阵的条件数KX、KZ和图像数据矩阵维数n满足kX,kZ=(O(polylogn)时,该算法具有指数加速优势。此外,该算法可用于高效实现两个与视觉追踪相关的任务:目标消失探测和运动行为匹配。该算法展示了量子计算在解决计算机视觉问题方面的能力。