邱俊玲 张 盼

（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-)，女，河南郑州人，硕士，助教，研究方向为计算机应用。