1. 首页
  2. 量子计算

揭秘档案【量子算法】

引言:从1946年埃尼阿克的问世,到2017年中国的“神威太湖之光”问鼎超级计算机的榜首。计算机的运算能力越来越强,运算速度越来越快,体积是越来越小,着实让人吃惊。而今量子计算机缓缓到来,基于量子计算的量子算法,以及解决问题的复杂程度成了一个值得关心和学习的问题。

Keywords: 量子算法,计算复杂性,量子力学

我们可以用普通的计算机处理数据,比如:125*239=?很显然这时候计算机就可以很快的计算出结果。但是如果我现在想要求的是29031这个数字的质因数分解,这时候计算机可能需要花很长一段时间来处理这个问题了。当我们想要质因数分解的数字N,达到几千万的时候,普通计算机可能需要运算几百年或者上千年。而此时如果采取量子算法,则上面的大数分解问题便可以迎刃而解,几乎瞬间就可以完成大数分解。

经典算法本质上与量子力学毫无关系,也完全不依赖量子物理,只是数学上的技巧而已。而量子算法则是融入了量子力学很多的特征,比如:量子的相干性量子叠加性量子并行性纠缠性,波函数塌缩等。这些纯物理性质进而大大提升了计算的效率,自成一体构建出一种新型的计算模式——量子算法。一些特殊的问题,按照经典计算复杂性理论是不存在有效算法,但是在量子算法中能够找到有效算法。其有效性体现在,处理“足够多”的数据量,经典算法随着数据量的增加,消耗的时间远远超过量子算法。

揭秘档案【量子算法】

通常计算复杂性理论有两个基本概念:

Concept:

  • 1、输入规模 $L=log_2 N$,输入数N的二进制码的位数便是存储它所需要的量子比特数。
  • 2、某算法 $\Omega$ 的复杂性$f_{\Omega}(L)$,该算法的效果,比如执行该算法所花费的时间T或者运行步骤n.

Definition:

如果一种算法$\omega$的复杂性$f_{\Omega}(L)$,随着输入规模L增加以不快于多项式$poly(L)$增速,当且仅当运算步骤n满足:

$$n\leq poly(log_2 N)$$

其中 $poly(x)$, 为$x$的任意多项式,就称此算法$\omega$为有效算法,否则称为无效算法

通常数学是作为一种计算工具为物理学科服务,现在则可以通过量子物理来协助数学上突破计算极限。故而经典计算机复杂性理论需要做出相应的修正,以便契合量子计算理论。

首先我们假量子算法有两个存储器,我们简记为A和B。首先对A所持有的量子比特,通过幺正演化实现$\pi/2$的旋转,此时我们可以得到系统的初态:

$$|0\rangle_A(\otimes|0\rangle_B)\Rightarrow\frac{1}{\sqrt{q}}\sum_{a=0}^{q=1}|a\rangle_A(\otimes|0\rangle_B)$$

这时为便是实施算法f的多重量子逻辑门操作组合成的一个$U(f)$算符。它作用在A和B上,利用量子算法的并行性,同时对A中的变量a 每一项都进行作用。算计完成对$f(a)$的计算,然后利用U中的相互作用存储于B中各对应的量子态,最终使得两个存储量子态纠缠起来。

$$U(f)\frac{1}{\sqrt{q}}\sum_{a=0}^{q=1}|a\rangle_A(\otimes|0\rangle_B)=\frac{1}{\sqrt{q}}\sum_{a=0}^{q=1}U(f)|a\rangle_A(\otimes|0\rangle_B)=\frac{1}{\sqrt{q}}\sum_{a=0}^{q=1}|a\rangle_A\otimes|f(a)\rangle_B$$

最后根据根据实际需要对(A或者B)其中一个存储器进行测量,对应的(B或者A)的量子态就会塌缩,最终会达到相应的计算目的。

最为典型的量子算法有:Shor算法(质因数分解),QEA算法(组合优化求解),Grover算法(量子搜索算法)等。这些量子算法可能处理的问题不同,但是都是采用了量子力学物理性质进行计算。每一种算法都有其独特性,比如Shor算法对质因素分解将直接威胁RSA加密体系,Grover算法在搜索方面,指数级的加速。这些都有潜在的巨大价值,如果对量子算法感兴趣的朋友,可以参考NielsenChuanghe合著的《量子计算和量子信息》,以及张永德老师的《量子信息物理原理》

当然一个值得推荐的网站是: https://math.nist.gov/quantum/zoo/ 

近年来的量子算法皆收录其中,去那里你也会挖到不少宝贝。

 

参考资料:

【1】MichaelA.Nielsen, IsaacL.Chuang, 尼尔森,等. 量子计算和量子信息:量子计算[M]. 清华大学出版社, 2004.

【2】张永德. 量子信息物理原理[M]. 科学出版社, 2006.

本文由量客特约作者撰写,转载需授权,欢迎至信: Support@qtumist.com ,转载请注明出处:https://www.qtumist.com/post/3147

发表评论

登录后才能评论