【摘要】：作為計(jì)算機(jī)科學(xué)和統(tǒng)計(jì)學(xué)的交叉子領(lǐng)域,數(shù)據(jù)挖掘旨在從大量數(shù)據(jù)中挖掘出其中隱藏的重要信息,是知識(shí)發(fā)現(xiàn)的關(guān)鍵步驟。此外,數(shù)據(jù)挖掘可用于挖掘密碼系統(tǒng)中明密文隱藏的模式以分析其安全性,因此也是密碼分析的一個(gè)重要工具。然而,隨著信息技術(shù)的高速發(fā)展,全球數(shù)據(jù)總量每年指數(shù)增長(zhǎng),這使得經(jīng)典數(shù)據(jù)挖掘算法未來(lái)處理大數(shù)據(jù)時(shí)將面臨計(jì)算性能的巨大挑戰(zhàn)。量子計(jì)算利用量子力學(xué)基本原理(如量子疊加和量子糾纏)實(shí)現(xiàn)計(jì)算任務(wù),在解決某些特定問(wèn)題上相比經(jīng)典計(jì)算具有顯著的速度優(yōu)勢(shì)。例如,Shor量子算法能夠快速分解大數(shù)因子,相對(duì)經(jīng)典算法具有指數(shù)加速,對(duì)被廣泛應(yīng)用的RSA密碼系統(tǒng)安全構(gòu)成嚴(yán)重威脅。近年來(lái),量子計(jì)算已被應(yīng)用到數(shù)據(jù)挖掘領(lǐng)域,且解決多種數(shù)據(jù)挖掘問(wèn)題的高效量子算法已被提出。然而,量子數(shù)據(jù)挖掘算法研究仍處于初始階段,許多數(shù)據(jù)挖掘問(wèn)題尚無(wú)高效量子算法解決。本文對(duì)此展開(kāi)進(jìn)一步研究,針對(duì)若干重要的數(shù)據(jù)挖掘問(wèn)題,提出相比經(jīng)典算法具有顯著加速的量子算法。這些量子數(shù)據(jù)挖掘算法也將為密碼分析量子算法研究提供重要參考。具體來(lái)說(shuō),本文研究包括以下四個(gè)方面。1、針對(duì)關(guān)聯(lián)規(guī)則挖掘的核心任務(wù)——從候選項(xiàng)集中找出頻繁項(xiàng)集,提出一個(gè)量子關(guān)聯(lián)規(guī)則挖掘算法。具體來(lái)說(shuō),對(duì)于Mc(k)個(gè)候選k項(xiàng)集中存在Mf(k)個(gè)頻繁k項(xiàng)集(Mf(k)≤Mc(l))的情況,所提算法通過(guò)并行幅度估計(jì)和幅度放大能夠有效地挖掘出這些頻繁k項(xiàng)集并估計(jì)它們的支持度。該算法的復(fù)雜度為O(k(?),其中ε為支持度估計(jì)誤差。與復(fù)雜度為O(kMk)/ε2)的經(jīng)典算法相比,所提量子算法當(dāng)Mf(k)Mc(k)時(shí)關(guān)于ε和Mc(k)均有平方加速,而當(dāng)Mf(k)≈Mc(k)時(shí)僅關(guān)于ε具有平方加速。2、基于最著名的主成分分析數(shù)據(jù)降維算法,提出一個(gè)量子數(shù)據(jù)降維算法。該算法以量子并行的方式將一個(gè)高維數(shù)據(jù)集投影到低維空間從而獲得相應(yīng)的低維數(shù)據(jù)集。與經(jīng)典算法相比,當(dāng)?shù)途S空間維數(shù)d和原高維空間維數(shù)滿足d=O(polylog D)時(shí)該算法具有指數(shù)加速效果。此外,該算法能夠被用于兩個(gè)重要的量子機(jī)器學(xué)習(xí)算法:量子支持向量機(jī)和量子線性Q嫻樵げ

本文編號(hào)：2776502