针对若干数据挖掘问题的量子算法研究

发布时间：2020-07-31 12:58

【摘要】：作为计算机科学和统计学的交叉子领域,数据挖掘旨在从大量数据中挖掘出其中隐藏的重要信息,是知识发现的关键步骤。此外,数据挖掘可用于挖掘密码系统中明密文隐藏的模式以分析其安全性,因此也是密码分析的一个重要工具。然而,随着信息技术的高速发展,全球数据总量每年指数增长,这使得经典数据挖掘算法未来处理大数据时将面临计算性能的巨大挑战。量子计算利用量子力学基本原理(如量子叠加和量子纠缠)实现计算任务,在解决某些特定问题上相比经典计算具有显著的速度优势。例如,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)时该算法具有指数加速效果。此外,该算法能够被用于两个重要的量子机器学习算法:量子支持向量机和量子线性Q嫻樵げ

本文编号：2776502