揭秘档案【量子算法】

引言：从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算法在搜索方面，指数级的加速。这些都有潜在的巨大价值，如果对量子算法感兴趣的朋友，可以参考Nielsen和Chuanghe合著的《量子计算和量子信息》，以及张永德老师的《量子信息物理原理》。