邱俊玲 張 盼

（1. 河南工業(yè)貿(mào)易職業(yè)學(xué)院 信息工程系，河南 鄭州 450000；2. 鄭州康寧特環(huán)境工程科技有限公司，河南 鄭州 450000）

量子算法在大數(shù)據(jù)時代的應(yīng)用淺析

邱俊玲1張 盼2

（1. 河南工業(yè)貿(mào)易職業(yè)學(xué)院 信息工程系，河南 鄭州 450000；2. 鄭州康寧特環(huán)境工程科技有限公司，河南 鄭州 450000）

量子計算機(jī)的提出不僅在計算機(jī)領(lǐng)域，而且在物理、通信、材料等很多領(lǐng)域產(chǎn)生了巨大的反響，目前各國都加入到量子計算機(jī)的研發(fā)中，量子算法、構(gòu)建、物理實現(xiàn)等方面都有很多進(jìn)展。隨著信息技術(shù)的進(jìn)步，人們對數(shù)據(jù)處理的需求和速率要求變得日益苛刻，在這種背景下，量子技術(shù)與大數(shù)據(jù)處理技術(shù)的結(jié)合成為突破大數(shù)據(jù)處理的曙光。

量子算法；大數(shù)據(jù)；數(shù)據(jù)挖掘

1 引言

隨著信息量的增多，當(dāng)今時代正面臨著大數(shù)據(jù)的沖擊。大數(shù)據(jù)推動了科學(xué)技術(shù)的變革，促進(jìn)了行業(yè)間的融合，人們在享受大數(shù)據(jù)給社會帶來的機(jī)遇，同時也承受著它帶來的挑戰(zhàn)。根據(jù) 2014年的統(tǒng)計數(shù)據(jù)，全球每分鐘有 204,000,000封往來郵件 ，F(xiàn)acebook 上有 2,460,000篇共 享 ，Twitter上 產(chǎn) 生277,000條微博 ，亞馬遜上產(chǎn)生 83,000美元的在線交易等。這些海量的數(shù)據(jù)量使數(shù)據(jù)庫的信息越來越巨大，隨之所需的數(shù)據(jù)處理算法也越來越復(fù)雜。如何在海量、復(fù)雜的數(shù)據(jù)中提取出有用的信息，如何將信息進(jìn)行可靠傳遞，成為了信息時代的難題。眾多學(xué)者也就此問題進(jìn)行了大量的研究 ：《Nature》曾 在 2008年 推 出“Big Data 專 刊”，《Science》也 在 2011年推出“dealing with data ”專刊[1]，可見科學(xué)界對大數(shù)據(jù)問題的關(guān)注。

量子技術(shù)自上世紀(jì)80年代被提出以后，以其獨(dú)特的并行數(shù)據(jù)處理能力被廣大研究和應(yīng)用人員所推崇，其理論最初是物理學(xué)界依據(jù)物理問題提出的，但隨著其理論和實踐的深入研究，量子計算也被計算機(jī)科學(xué)、信息科學(xué)、材料科學(xué)、心理學(xué)等領(lǐng)域廣泛研究。雖然實用的通用量子計算機(jī)并未實現(xiàn)，但量子學(xué)研究的腳步從未停止，2013年初，D-wave公司出品的 D-wave Two 專用量子計算機(jī)問世，其處理器達(dá)到 512量子位，是目前商用市場上最強(qiáng)大的量子計算機(jī)，也預(yù)示著通用量子計算機(jī)實現(xiàn)的可能性。

2 量子算法的發(fā)展

1982年，Argonne 實驗室的 Paul Benioff最早提出使用量子力學(xué)來描述可逆計算機(jī)，提出二能階的量子系統(tǒng)能進(jìn)行仿真計算；隨后，F(xiàn)eynman提出了量子計算機(jī)可以模擬量子多體系統(tǒng)的演化，構(gòu)造了哈密頓量，針對經(jīng)典機(jī)所對應(yīng)的各種邏輯門。1985年，Deutsch 建立了第一個量子圖靈機(jī)模型，提出量子計算網(wǎng)絡(luò)及兩個量子比特的算法[1]，自此量子理論引起了廣大學(xué)者的關(guān)注，量子計算的概念開始進(jìn)入研究領(lǐng)域。1994年，Peter Shor提出能夠在多項式時間內(nèi)計算的大數(shù)質(zhì)因子分解算法，實現(xiàn)了相對于經(jīng)典算法的指數(shù)級加速。1997年 Grover提出的 Grover量子搜索算法，針對未排序數(shù)據(jù)庫將經(jīng)典計算情況下的NP難題轉(zhuǎn)化為能夠在多項式時間內(nèi)求解的 P 問 題 ，同 樣 有 力 地 證 明 了 量 子 計 算 的 高 效 性 特 點(diǎn)[2]。2002年 Han.k.H 等人提出了量子遺傳算法，將傳統(tǒng)的遺傳算法和量子計算理論相結(jié)合，用量子位編碼表示染色體，采用量子旋轉(zhuǎn)門構(gòu)造的酉變換實現(xiàn)染色體的進(jìn)化過程。在此基礎(chǔ)上，國內(nèi)外學(xué)者提出了新的量子遺傳算法。麻省理工大學(xué)的 Farhi教授提出的量子絕熱演化算法，解決了 3-滿意度問題、Exact Cover問題等。此外，量子漫步理論、量子博弈理論、量子演化博弈等理論都是新的量子理論[3]。

3 量子計算的特性

傳統(tǒng)的馮·諾依曼機(jī)是基于二進(jìn)制位（bit）來對信息處理的，即所有數(shù)據(jù)都以0和1的狀態(tài)編碼、存儲和運(yùn)算。其基本思想是存儲和程序控制，數(shù)據(jù)通過一定方式輸入并存儲在存儲器中，等待機(jī)器指令對其操作，結(jié)束后存入存儲器。雖然計算機(jī)領(lǐng)域飛速發(fā)展，CPU集成率越來越高，存儲器容量越來越大，但依然是基于這種思想。如果晶體管繼續(xù)減小，當(dāng)晶體管的尺寸達(dá)到電子級，電子的活動就要滿足量子力學(xué)原理[4]，也就是說計算機(jī)發(fā)展的未來離不開量子理論的研究和實踐。

量子計算的基本單元是量子比特（qubit），量子比特與傳統(tǒng)計算機(jī)的信息單元 bit有所區(qū)別，不再是單一的兩種狀態(tài)（0和1），而是0和1的相應(yīng)量子態(tài)疊加：

式中用|>符號來表示正交態(tài)。

量子比特的物理載體是任意兩態(tài)的量子系統(tǒng)，如光子、電子等 ，量子可同時處于|0>和|1>兩態(tài)。即一個量子比特可以是|0>狀態(tài)，可以是|1>，也可以是兩者的疊加態(tài)，只要滿足上述公式的條件，這種疊加態(tài)使得量子計算可以實現(xiàn)絕對的并行計算。對于一個N個比特的存儲器，如果是傳統(tǒng)存儲方式，那么它只能存2N個可能數(shù)據(jù)中的任何一個，如果是量子存儲方式，則可以同時存儲2N個數(shù)，因此它的存儲能力是呈指數(shù)級增加的。

4 大數(shù)據(jù)與量子算法的結(jié)合應(yīng)用

4.1 大數(shù)據(jù)的定義

大數(shù)據(jù)的概念研究得比較早，普遍關(guān)注度很大，不論把大數(shù)據(jù)稱為海量數(shù)據(jù)或大規(guī)模數(shù)據(jù)，其本質(zhì)都是一樣的。Gartner公司給出了大數(shù)據(jù)的定義：即巨量、高速和多樣化的信息資源，需要合算地、創(chuàng)新地進(jìn)行信息處理。另外基于大數(shù)據(jù)特性的3V和4V定義認(rèn)同率也較高。3V認(rèn)為大數(shù)據(jù)的特征包括規(guī)模性、多樣性和快速性；4V則在此基礎(chǔ)上增加價值性。規(guī)模性即數(shù)據(jù)的規(guī)模，包括數(shù)據(jù)的大量存儲和大量處理，一般來說數(shù)據(jù)都在PB級；多樣性指數(shù)據(jù)的來源和類型種類的多樣，如文本數(shù)據(jù)、影音數(shù)據(jù)、傳感器信號等，多種數(shù)據(jù)的交織；快速性是指其數(shù)據(jù)的不斷增長和所需的處理速度的要求，目前世界上90%的數(shù)據(jù)都在近兩年產(chǎn)生；價值性則是指大數(shù)據(jù)背后所蘊(yùn)含的財富。還有學(xué)者把第四個V定義為真實性或靈活性，其本質(zhì)都反映了處理大數(shù)據(jù)的內(nèi)在要求[5]。4.2 大數(shù)據(jù)處理的研究現(xiàn)狀

在大數(shù)據(jù)處理算法方面，Havens提出了模糊 C 均值聚類，用以近似求解大規(guī)模數(shù)據(jù)。Lu 和Li在小規(guī)模采樣的基礎(chǔ)上，采用簡單隨機(jī)游走方法用來估計大數(shù)據(jù)的規(guī)模。Zhang等人使用粗糙集方法實現(xiàn)大數(shù)據(jù)挖掘。Gomes等提出了在動態(tài)特征空間中挖掘 recurring concepts的方法，同時降低內(nèi)存損耗。在大數(shù)據(jù)處理平臺方面，中國人民大學(xué)高性能數(shù)據(jù)庫研究小組實現(xiàn)了 LinearDB，該方法是采用 Postgresql技術(shù)實現(xiàn)的。中科院研究所開展了索引優(yōu)化的研究并利用分布式內(nèi)存來提高M(jìn)apReduce的性能。大數(shù)據(jù)處理的開源軟件為大數(shù)據(jù)分析提供了技術(shù)基礎(chǔ)，包括文件系統(tǒng)HDFS、MapReduce 運(yùn)行庫、NoSQL 等[5]。

國內(nèi)外對大數(shù)據(jù)的研究還集中在對大數(shù)據(jù)一體機(jī)方面，IBM、Oracle、EMC 曙光等都先后推出了大數(shù)據(jù)一體機(jī)，這代表了企業(yè)對大數(shù)據(jù)處理問題的重視及面對問題的各種嘗試。此外還有各種大數(shù)據(jù)軟件平臺 ，如 IBM 推出的 InfoS-phere 可以幫助公司發(fā)現(xiàn)和分析隱藏在大量數(shù)據(jù)中的信息，這些數(shù)據(jù)往往被忽視或不容易用傳統(tǒng)方法處理。BigInsights用來分析和處理用戶感興趣的數(shù)據(jù)的數(shù)量、種類和速度的增加。微軟的 power pivot可以將大量的數(shù)據(jù)從多個數(shù)據(jù)源導(dǎo)入單個excel工作薄中，創(chuàng)建異構(gòu)數(shù)據(jù)之間的關(guān)系。

盡管在大數(shù)據(jù)處理方面，相關(guān)學(xué)者進(jìn)行了大量的研究，各大企業(yè)也進(jìn)行了很多嘗試，然而利用傳統(tǒng)方法處理大數(shù)據(jù)的問題還有很多，比如傳統(tǒng)的數(shù)據(jù)處理模式不能滿足大數(shù)據(jù)發(fā)展的需求，大數(shù)據(jù)規(guī)模的降低方面缺少有效的方法，大數(shù)據(jù)的分析和處理代價太大等，這些問題隨著數(shù)據(jù)信息的不斷變化，已成為當(dāng)今時代的挑戰(zhàn)。面對這些問題，很多學(xué)者把目光轉(zhuǎn)向了量子力學(xué)，嘗試?yán)昧孔铀惴▉斫鉀Q大數(shù)據(jù)方面的某些問題。

4.3 量子算法在大數(shù)據(jù)挖掘方面的應(yīng)用

(1)解決經(jīng)典問題

大數(shù)質(zhì)因數(shù)的分解是基于Shor算法提出的，利用量子計算的特性，有些經(jīng)典的計算難題就有希望得到很好的解答[1]。例如大數(shù)的因數(shù)分解問題 ，要分解一個數(shù)字 N，利用傳統(tǒng)計算機(jī)的編程來計算，算法是從2開始試驗?zāi)芊癖徽?，一直?N 的平方根為止，嘗試次數(shù)最多是 2（2/N）次。如果計算機(jī)每秒做 1012次運(yùn)算，要分解一個 300位的數(shù)字需要 15萬年，但利用Shor算法只需要不到1s鐘，將指數(shù)級的運(yùn)算次數(shù)縮減到多項式級，大大縮短了運(yùn)算時間。這些看似理論化的問題在實際生活中有重要的實用價值，比如在繁雜的銀行用戶數(shù)據(jù)中，針對不同用戶提出針對性的投資措施等。

郭光燦指出在后摩爾時代，晶體管的電子管數(shù)目越來越多，當(dāng)達(dá)到電子級時就不能再用摩爾定律解釋，此時就成了量子行為，在量子世界，量子密碼是第一個可能走向應(yīng)用的方向，可見量子技術(shù)的發(fā)展是一個必然趨勢。比如目前銀行和網(wǎng)絡(luò)上普遍應(yīng)用RSA算法，它的可靠性是以數(shù)論中大整數(shù)分解的困難性為基礎(chǔ)的，當(dāng)量子計算機(jī)成為現(xiàn)實，再用RSA算法加密傳遞就相當(dāng)于明文傳輸。

(2)量子搜索

大數(shù)據(jù)時代信息數(shù)量和種類都非常多，除了有用信息還有很多無用信息，面對海量的數(shù)據(jù)如何在最短時間內(nèi)準(zhǔn)確找到所需的數(shù)據(jù)很重要，所以編程人員最先學(xué)的完整的程序設(shè)計方法就是排序、篩選。量子搜索是基于 Grover算法實現(xiàn)的，量子搜索相對于因式分解并不算發(fā)生質(zhì)的變化，然而在大數(shù)據(jù)條件下，它使得實際條件下能計算的問題范圍擴(kuò)大了，并且隨著搜索次數(shù)的增加，準(zhǔn)確度和確定性也隨之增加。

5 結(jié)束語

量子算法在國際上的影響力很大，各國都已經(jīng)拿出人力、財力投入到量子計算領(lǐng)域的研發(fā)，而量子算法在大數(shù)據(jù)時代的應(yīng)用也將越來越實用。2016年我國發(fā)射了“墨子號”衛(wèi)星，這是全球第一顆量子通信衛(wèi)星，預(yù)示著我國對量子技術(shù)的重視，也顯示了我國在量子應(yīng)用方面的先進(jìn)性，相信不遠(yuǎn)的將來量子技術(shù)會給國民經(jīng)濟(jì)和生活帶來更巨大和深遠(yuǎn)的影響。

[1]徐煒，肖智，楊道理．量子算法在大數(shù)據(jù)挖掘中的應(yīng)用前景淺析[C]．2013中國信息經(jīng)濟(jì)學(xué)會學(xué)術(shù)年會暨博士生論壇論文集，2013．

[2]錢國紅．量子算法及其在數(shù)據(jù)挖掘中的應(yīng)用[M]．杭州：浙江工業(yè)大學(xué)，2012．

[3] 方糧．量子計算機(jī)- 量子算法與物理實現(xiàn)[J]．計算機(jī)工程與科學(xué)，2012，34(8)：32-43．

[4]郭光燦．量子計算機(jī)的發(fā)展現(xiàn)狀與趨勢[J]．中國科學(xué)院學(xué)報，2010，25(5)：516-524．

[5]徐計，王國胤，于洪．基于粒計算的大數(shù)據(jù)處理[J]．計算機(jī)學(xué)報，2015，38(8)：1497-1516．

Application of QuantumAlgorithm in Big DataAge

Qiu Junling1Zhang Pan2
(1.Henan Industry and Trade Vocational College,Zhengzhou 450000,Henna; 2.Zhengzhou Kangningte Environmental Engineering Technology Co.,Ltd,Zhengzhou 450000,Henna)

The advent of quantum computer has generated tremendous repercussions not only in the computer field but also in physics,communications,materials,and many other fields.Now many countries have joined the development of quantum computers.There is a lot of progress in quantum algorithms,construction,physical implementation and other aspects.With the progress of information technology,people's demands for data processing and speed become increasingly harsh,in this context,the combination of quantum technology and big data processing technology breaks through the dawn of big data processing.

quantum algorithm;big data;data mining

TP311.13

A

1008-6609(2017)05-0047-03

邱俊玲(1987-)，女，河南鄭州人，碩士，助教，研究方向為計算機(jī)應(yīng)用。