量子算法在大數據時代的應用淺析

邱俊玲 張 盼

（1. 河南工業貿易職業學院 信息工程系，河南 鄭州 450000；2. 鄭州康寧特環境工程科技有限公司，河南 鄭州 450000）

量子算法在大數據時代的應用淺析

邱俊玲1張 盼2

（1. 河南工業貿易職業學院 信息工程系，河南 鄭州 450000；2. 鄭州康寧特環境工程科技有限公司，河南 鄭州 450000）

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

量子算法；大數據；數據挖掘

1 引言

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

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

2 量子算法的發展

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

3 量子計算的特性

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

量子計算的基本單元是量子比特（qubit），量子比特與傳統計算機的信息單元 bit有所區別，不再是單一的兩種狀態（0和1），而是0和1的相應量子態疊加：

式中用|>符號來表示正交態。

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

4 大數據與量子算法的結合應用

4.1 大數據的定義

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

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

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

盡管在大數據處理方面，相關學者進行了大量的研究，各大企業也進行了很多嘗試，然而利用傳統方法處理大數據的問題還有很多，比如傳統的數據處理模式不能滿足大數據發展的需求，大數據規模的降低方面缺少有效的方法，大數據的分析和處理代價太大等，這些問題隨著數據信息的不斷變化，已成為當今時代的挑戰。面對這些問題，很多學者把目光轉向了量子力學，嘗試利用量子算法來解決大數據方面的某些問題。

4.3 量子算法在大數據挖掘方面的應用

(1)解決經典問題

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

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

(2)量子搜索

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

5 結束語

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

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

[2]錢國紅．量子算法及其在數據挖掘中的應用[M]．杭州：浙江工業大學，2012．

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

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

[5]徐計，王國胤，于洪．基于粒計算的大數據處理[J]．計算機學報，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-)，女，河南鄭州人，碩士，助教，研究方向為計算機應用。