Deutsch-Jozsa algorithm

一个玩具模型，没有任何实际的用处，但是让大家理解了量子并行性。假设存在一个Oracle machine^[1] 。简单理解就是一个黑箱子，输入长度为n的数据串会返回0/1中的一个值。这个Oracle可能有两种属性：1. 输出结果0和1概率均等（balance） 2. 永远只返回一个值，0或者1 (constant)。你的任务是检验一个未知的Oracle 属于上述哪一类。

经典算法要验证这个问题需要暴力尝试，最坏情况要尝试 次。但是量子并行算法只需要一次尝试。（留给读者思考为什么只用一次）

Grover's algorithm

搜索算法。在NP问题中，Grover算法在unstructured database搜索特定解，相比经典算法有quadratic quantum speed up。不过这个搜索（目前来说）不是用在经典数据上的，而是在希尔伯特空间中寻找需要的state。

其中 . 算法的核心就是先初始化一个state（可任意），通过在Hilbert space的一系列inversion和relection操作，最后得到目标态（可不止一个） .

Quantum Fouier Transform and periodicity

量子信息中极其重要的算法，类比傅里叶变换在经典信息论中的重要性。理解同样可以类比经典傅里叶：经典傅里叶把函数从时序到频域做变换；量子傅里叶把一个态 map到另一个basis 上，即

.

看起来只是换个基，但是实际用处非常大。一个最经典的应用就是找函数的周期。

Integer factorisation

著名的Shor算法，也是让量子计算一炮而红的算法。在此之前大家都怀疑量子到底能不能加速计算，Shor算法的出现消除了大家的顾虑。而且shor算法加速的是数论中最难的质因数分解问题，也是RSA加密算法的根基。

Shor算法基本的idea就是数论的一同操作，把分解质因数扔到量子的Hilbert space里，转化为一个找周期的问题。之后参考上面的Quantum Fouier Transform (QFT)找到这个周期。

Phase estimation

著名大佬Kiteav提出的算法，用于估算一个unitary operator下本征向量的phase （或本征值）。此算法在解线性方程组的量子算法^[2]中有直接应用，在此不展开。

Hamiltionian Simulation

通过一连串的quantum gate的组合，模拟一个任意的Hamiltionian系统的演化。这也是Feynman最早提出量子计算的构想：simulate quantum system with quantum computer。

目前有很多冷原子和凝聚态的体系可以做Hamiltionian的模拟，但是一个体系只能模拟一类的Hamiltionian（analogue simulation）。而这里的Hamiltionian Simulation算法理论上可以模拟任意想要的体系（digital simulation）。

Quantum cryptography

量子加密内容太多了，也有很多资料可以参考，在此不展开。最经典的量子秘钥分配可以参考BB84和Ekert91协议。

Quantum error correction

量子纠错算法同样是一个大坑，内容很多。5-bits code, 7-bits code, 9-bits code不一而足。

量子纠错的核心：一个qubit容易出现error，我们把它map到一个更大的Hilbert空间。由于冗余的空间，少量的错误并不会摧毁最开始的信息。

随手复习之前的课写个short note，非常粗浅。希望对初学者有帮助。

参考

1. ^https://zh.wikipedia.org/wiki/%E9%A0%90%E8%A8%80%E6%A9%9F
2. ^https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations