• [量子计算]量子搜索Grover算法

    搜索算法是最常用的一类算法了,然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下,算法复杂度为\Omicron(N)N为数据规模。而量子计算机中存在着量子搜索算法,也称为Grover's算法,它的时间复杂度是\Omicron(\sqrt N)。听起来似乎提升不是非常大,然而在数据规模较大的情况下,量子搜索算法的优越性还是非常惊人的。例如,用Grover算法破解通用的56位加密标准(DES),只需要2^{28} \approx2.68 * 10^{8}步,而经典算法则需要2^{55} \approx3.6 * 10^{16}。如果每秒钟计算十亿次,则经典计算需要11年,而量子算法则只需要3秒钟【参考北大物理学院讲义】。

    1、 Grover算法理论基础

    Grover's算法的基本思路其实非常容易理解,而且存在非常直观的可视化解释(这一点是非常棒的!)。Grover… 【查看更多】

  • [量子计算]相位估计算法

    本文出自:【InTheWorld的博客】 (欢迎留言、交流)

    量子相位估计算法

    量子相位估计算法(Quantom Phase Estimation)也称作量子特征值估计算法,是一个比较基本的算法。它的作用直观说来就是来估计一个酉变换的特征值。由于酉矩阵拥有一个性质:酉矩阵的特征值都是模为1的复数。所以对酉矩阵而言,其特征值和相位基本是对等的(因为模长已经确定了)。

    量子傅里叶变换

    在量子相位估计算法中,需要使用到量子傅里叶反变换。因此,我们简单了解一下量子傅里叶变换的相关知识。经典的离散傅里叶变换作用于一个复向量(x_{0}, x_{1},\cdots,x_{N-1}),并把它映射到另一个向量(y_{0}, y_{1},\cdots,y_{N-1}),其映射关系如下:

    y_{k}=\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} {x_{j}e^{-2\pi ijk/N}}【查看更多】