量子算法简介
The following article is from 量子科学ABC Author 李绿周
量子计算近年来受到了极大关注,根本原因在于其具有强大的并行性,可以在有效时间内解决一些经典计算机不能有效解决的问题。例如,Shor 算法可以在多项式时间内解决大数因子分解问题,从而对现代 密码造成了极大威胁。然而,量子计算的并行性并非直接可以利用,而是需要根据所解决的问题经过巧妙的算法设计才可能。即便量子计算机研制成功,如果没有相应的量子算法,量子计算的潜能还是得不到实质性发挥。因此,要想利用量子计算解决实际问题,能否设计出快速的量子算法是关键。不夸张的说,量子算法的研究是推动量子计算向前发展不可取代的力量源泉。
量子计算并行性的根源
量子算法的基本框架
量子算法设计的困难性
量子算法研究简明进程
关于量子算法的两个疑问
总结
量子计算并行性的根源
量子算法的基本框架
制备一个叠加态,它表示函数自变量值的线性组合;
作用U_f (函数f所对应的线性算子(矩阵)),根据线性性,它会分别作用在每一个基态上,把函数对每一个自变量的值计算出来,即体现潜在的并行性;
提取想要的信息。通过巧妙的设计,利用干涉现象使得系统最后状态能以很大的概率落到目标点|P(f)>。算法设计的巧妙性就体现在这一步。
量子算法设计的困难性
具有思想性的算法从来不容易,即使在经典计算领域也是如此。任何一个原创性算法都是智慧的结晶。
量子力学的反直观性使得在经典世界积累的算法设计经验可能不再适用,而此时还要求设计出比经典算法更好的量子算法,从而变得雪上加霜。目前人们并不太清楚量子计算能加速解决的问题具有什么特征,进行量子算法设计时基本上是摸着石头过河。
量子计算并行性的根源
Simon算法直接启发了著名的Shor算法的发现,这一点无论是在Shor算法的原文还是在一些知名学者写的量子计算方面的书里都有非常明确地指出来。
Simon算法近年在密码破译方面得到直接应用。虽然它所解决的问题在提出之初并未见明显的应用场景,然而近几年基于Simon算法进行密码破译的研究在不断跟进,在密码学顶级会议Crypto上就有相关工作发表。有趣的是,Simon算法的作者Daniel R. Simon似乎除了提出该算法之外并没有其他关于量子计算的成果。或许他只是在量子计算的花园里丢下一颗种子就走的游客,幸运的是种子已经发芽开花。
HHL算法并未把方程组的解以经典可读取的方式呈现出来,而是把其编码在量子态中,需要经过后续的算法设计来提取我们想要的信息。近年来出现的大量有关量子机器学习的研究主要就是基于HHL算法做后续算法设计。
目前一些量子机器学习方面的研究需要提供更严肃的理论分析。
量子机器学习如果要面对实际数据处理问题,有待突破输入/输出瓶颈。所谓输入/输出瓶颈是指,目前大部分量子机器学习算法或者需要把大规模数据集编码为量子态,或者只是把问题的解生成在量子态中,因此输入阶段的前处理和信息提取阶段的后处理将耗费大量时间,乃至抵消量子算法所节省的时间。
关于量子算法的两个疑问
从经典计算领域来看,算法的研究远远早于计算机的出现。欧几里德算法出现在古希腊时代,而第一台电子计算机是1946年生产的。另外,图灵机的提出正是为了严格地刻画“算法”。
没有算法支持的量子计算机是否还能称为计算机呢?量子算法是量子计算机的必要软件支撑,同时量子算法的研究也是推动量子计算发展的强大动力,从Shor算法的历史地位可见一斑。
抽象层次的算法设计从来不依赖于具体硬件平台,在经典计算领域就是如此。算法本质上是解决问题的一种方法,量子算法是遵循量子力学规律的一种方法。硬件平台只是实现这种方法的一个工具。当然,软硬件之间的互动与交流对于设计更符合实际情况的算法非常必要。
从算法与复杂性研究的角度来看,算法的好坏由复杂度衡量,这依赖于严格的数学证明,而不是在具体硬件平台上的测试。目前量子算法主流的研究是如此。
总结
量子计算机相对与经典计算机在哪些方面有优势?有多大程度的优势?这些问题目前远未搞清楚,这意味着量子算法的研究有非常大的空间。大家都期待量子计算领域有更多具有创新性的算法出现,每一位量子算法研究者也都希望设计出一个代表性算法。然而,罗马不是一天建成的,千里之行始于足下。我们不应只记住Shor算法的巧妙,而忘记前人的努力。事实上,Shor算法是站在Simon算法的肩上,而Simon算法源于那些看似没用的Deutsch-Jozsa算法和Deutsch算法。这个过程正好体现了科学研究的魅力:或许很多研究成果会被大浪淘沙,但正是那些一点一滴的看似无用的研究一步一步孕育着一个新的发现!