当前位置: > 热博

量子时代,我们需要量子算法

时间:2022-10-02 02:08:44 热博 我要投稿

文/陈根

       当前,量子时代正在加速到来。量子领域中,最为人们所关注的就是颠覆经典计算的量子计算。作为一种依照量子力学理论进行的新型计算,量子计算能够利用量子的状态重叠和相互纠缠来产生巨大的计算能力。

       当然,正如经典计算一样,量子计算想要运行,也需要遵循一定的算法——就像普通算法是用来支持普通计算机解决问题的程序一样,量子算法是为超高速量子计算机设计的算法。量子算法不仅成全了量子计算机的无限潜力,也为人工智能带来了新的发展可能。

量子计算机也是可以计算的

       基于量子叠加态最让人们期待的应用,就是运算功能超级强大的量子计算机。

       在量子计算出现以前,经典计算机采用二进制的“位”(用“0”或“1”表示)作为信息存储单位,进而实现各种运算。而经典计算运算过程则是经由对存储器所存数据的操作来实施的。并且,经典计算机无论其存储器有多少位,一次只能存储一个数据,对其实施一次操作只能变换一个数据。因此,在运算时,必须连续实施多次操作,这就是串行计算模式。

       与经典计算机不同,量子计算机的信息单元是量子位。量子位最大的特点就是其可以处于“0”和“1”的叠加态,即一个量子位可以同时存储“0”和“1”两个数据,而传统计算机只能存储其中一个数据。比如一个两位存储器,量子存储器可同时存储“00”“01”“10”“11”四个数据,而传统存储器只能存储其中一个数据。

       也就是说,n位量子存储器可同时存储2n个数据,它的存储能力将是传统存储器的2n倍。因此,一台由10个量子位组成的量子计算机,其运算能力就相当于1024位的传统计算机。而对于一台由250个量子位组成的量子计算机(n=250),它能存储的数据将比宇宙中所有原子的数目还要多。

       换言之,即使把宇宙中所有原子都用来造成一台传统的经典计算机,也比不上一台250位的量子计算机。

       不过,一直以来,以怎样的方式才能把这些量子位连接起来,怎样为量子计算机编写程序,以及怎样编译它的输出信号,都是实现量子计算机超强运算能力的严峻挑战。直到1994年,贝尔实验室的彼得·肖尔(Peter Shor)提出了一种量子算法,能有效地分解大数,把分解的难度从指数级降到了多项式。

       彼得·肖尔从理论上展示了量子计算机能够把质因数分解问题的求解,从指数时间降到多项式时间。目前通用的计算机加密方案——RSA加密,利用的就是质因数分解的时间复杂性:用目前最快的算法对一个大整数进行质因数分解,需要花费的时间都在数年以上。但通过彼得·肖尔的算法,一台量子比特数足够多的量子计算机,能够“轻易”破解RSA模型下的任何大整数。彼得·肖尔因此荣获1999 年理论计算机科学的最高奖——哥德尔奖。

       根据彼得·肖尔的测算,分解一个250位的大数,传统计算机用今天最有效的算法,再让全球所有计算机联合工作,也需要几百万年。而量子计算机只需几分钟。量子计算机分解250位数时,进行的是10的500次方的并行计算。这是量子领域一个革命性的突破,这意味着,量子计算机也是可以进行计算的,并由此引发了大量的量子计算和信息方面的研究工作。

       在彼得·肖尔开发出第一个量子算法不久后,1996年,贝尔实验室的洛弗·格罗弗(Lov Grover)也称他们发现了一种可以有效搜索排序的数据库的算法。该算法能够在非结构化数据中进行闪电般的搜索。普通搜索算法花费的时间通常与要搜索的项目数n成正比,而格罗弗算法复杂度仅为n的负二次方。因此,如果将数据大小变为原来的100倍,普通算法执行搜索所需时间也会变为100倍,而格罗弗算法只需要原来所需时间的10倍。

当量子算法结合人工智能

       自Peter Shor发表第一个量子算法(分解大数质因子量子算法)以来,数学家和计算机科学家们就已经开发出其他量子算法来解决经典计算机难以解决的问题。在这几十种量子算法中,许多都比我们所知道的最有效的经典算法快几个数量级。当然,这些算法只有在它们所处的独特量子环境中才能实现。

       实际上,量子计算领域的一些最重要的工作就是创建模拟各种量子系统的算法,这些系统从激光技术到化工医学无所不包。这些量子算法将在很大程度上超过类似的经典计算,而为量子计算机赋予超强的计算能力。

       目前,进行分子模拟的经典算法仅限于它可以模拟的分子类型,这些算法通常只限于自旋轨道少于70个的分子,并且,由于且模拟的复杂性增长得非常快,以至于变得越来越难以处理。

       而一个量子比特就能足够有效地代表这些轨道中的一个,一个只有100个量子比特的量子计算机将能够进行经典计算机望尘莫及的分子模拟。这些模拟可能揭示各种以前未知的化合物,并为各种疾病提供新的治疗方法。

       从深度优先搜索(depth-first search)到绝热优化(adiabatic optimisation),量子算法应用广阔,而且在不断进步。当这些算法真正投入使用,商业、行政、医学、工程等领域一些最令人沮丧的,棘手的,指数级的问题都将迎刃而解。

       量子算法除了为量子计算机的无限潜力,也为人工智能带来了新的发展可能。基于量子的叠加和纠缠等原理,使得量子算法非常适于解决人工智能和机器学习中核心的优化(Optimization)过程类问题,所以从2018年开始,以谷歌为代表的企业纷纷开始投入量子人工智能,特别是与深度学习相结合的领域。

       在量子算法和人工智能结合的领域里,具有代表性的成果包括Google公司在2020年提出的Tensorflow Quantum(TFQ)框架。TFQ是一种量子-经典混合机器学习的开放源代码库,允许研发人员在设计、训练和测试混合量子经典模型时,可以模拟量子处理器的算法,在最终联机时,还可以在真实量子处理器上运行这些模型的量子部分。TFQ可用于量子分类、量子控制和量子近似优化等功能。

       可以说,人工智能和机器学习是量子算法发展的关键。人工智能想要快速获取“智慧”,只要通过量子算法和人工智能的结合,让它在人类社会中迅速学习,在寻找最优解的问题上,只需几个月时间就能超越人类。

       IBM的理论工作已经证明,即使仅访问经典数据,我们也可以在某些受监督的机器学习应用程序中实现指数级加速。

       QC Ware QC Ware开发了两种类型的数据加载器,即并行数据加载器和优化数据加载器,它们都将经典数据转换为量子状态以用于机器学习应用,而且还可以使用一种优化的距离估计算法。

       Matthias Troyer(微软)提出一个普遍的观点,为避免“输入瓶颈”,我们应该着眼于“小数据,大计算”。比如,CQC成立了一个团队来研究量子自然语言处理的相关问题。Hartmut Neven(Google)则发明了另一种独特但微妙的量子机器运行原理。

       虽然量子算法许诺了人们无限美好的计算前景,不过,当前,量子算法的执行仍然缺乏可用的量子硬件——这些算法所缺乏的是与之相对应的,具有足够量子比特的,足够强大的量子计算机。这些硬件挑战本质上是技术性的,而且克服这些困难的途径也是明确的。但是,如果量子机器学习要成为量子计算机的“杀手级应用”,那么,这些困难必须被克服,这些困难也终将被克服。