秀尔算法（Shor's algorithm）是一种非常著名的量子算法，甚至可以说是量子计算的一块金字招牌了。Shor's algorithm可以在多项式时间内完成大整数质因数分解。所以Shor's algorithm从诞生之时，就和以RSA算法为根基的加密技术形成了不可调和的矛盾。2001年，IBM的研究小组使用Shor's algorithm完成了15 = 3×5这个整数分解运算 。时至今日，快20年过去了，量子计算机没有摧毁RSA。未来这一天来临的时候，希望我们已经准备好了。下图是，经典大数分解和秀尔算法的复杂度对比。
完整的Shor算法是需要经典计算机和量子计算机协作完成的。其中量子计算机实现一个周期查找的函数，经典计算机负责整个算法流程的控制，以及调用量子算法。
首先、还是表达一下Shor's algorithm的问题描述：给定一个合成数N… 【查看更多】
搜索算法是最常用的一类算法了，然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下，算法复杂度为\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秒钟【参考北大物理学院讲义】。
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}}… 【查看更多】
本文出自:【InTheWorld的博客】 （欢迎留言、交流）
学习量子力学是几年前立的Flag了，一直没有真正投入时间。主要的原因还是“要吃饭”，而且一些层出不穷的新技术也有点迷惑了我。不过本质上还是自己科学品味太差，二来加上意志力不够坚定。目前已经花了一段时间学量子力学、量子信息，写在这里权当做笔记吧！
Deutsch-Jozsa是一个简单的量子算法例子。虽然从实用角度讲，这个算法意义不大，但是却能很好的体现量子计算的优越性。首先是问题的描述：
考虑一个黑盒子，我们称为oracle。它可以计算一个比特的布尔函数。每做一次计算，我们就称为是
对oracle的一次查询。对于这个函数，存在以下四种可能:
| 输入 | 0 | 1 | 0 | 1 |
|---|---|---|---|---|
| 输出 | 1 | 0 | 0 | 1 |
第（1,4）列或者（2,3）列组合而成的情况，我们称oracle为常数函数；第（1,2）列，或者（3,4）列… 【查看更多】
最新评论