第三周将学习量子计算的一些算法和DIY
本文只记录官方笔记中没有的或我觉得重要的内容
官方笔记我放在最后
量子计算平台
最后一个死活无法注册
本人更推荐第一个IBM, 量子比特数上限最高, 操作种类多, 而且我感觉IBM更靠谱
注意IBM与本源量子的最后结果的表达形式是反的, IBM结果低位是寄存器低位, 本源量子结果低位是寄存器高位注意
黑盒子Uf是一种固定操作, 相当与一个大型量子门, 输入为$x, y$, 输出为$x, y\oplus f(x)$
Deutsch’s Problem
constant function: 返回结果永远相同
balanced function: 一半输入的结果为1, 另一半为0
为什么有多余的1个qubit输入(y)?
如果没有, thus it is not unitary, 只有像官方笔记(2)那个公式那样定义才行, 此时maps orthonormal basis to orthonormal basis
其实y可以是m个比特, 上面微软的Quantum Oracles链接里解释的蛮详细的
其余见最后的官方笔记
经典计算机需要2次, 量子计算机只需1次
Quantum Computer Prototype, DIY
理解下面这个公式和官方笔记公式(7)很重要
对于Uf变换$$\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1}\mid x\rangle\left(\mid 0\rangle - \mid 1\rangle\right) \stackrel{U_f}{\longrightarrow} \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1}\mid x\rangle\left(\mid f(x)\rangle - \mid 1\oplus f(x)\rangle\right ) = \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} \left(-1\right)^{f(x)} \mid x\rangle\left(\mid 0\rangle - \mid 1\rangle\right)$$
从左往右, 第一个bit是路径, 第二个bit是偏振
官方笔记中对于路径的记录应该错了, 应该和课件中一样, 左边是$\mid 1\rangle$, 右边是$\mid 0\rangle$
对于图12-15的左半部分是由公式(4)(5)(6)推出, 而右半部分是实际物理意义
图12-15中的$\mid x\rangle$指的是路径, $\mid y\rangle$指的是偏振
对于图12, 很好理解, 即什么都不动
对于图13, 即不管光子走哪边, 都取反
对于图14, 当光子走左边时(实际上同时走左右), 就将偏振取反
对于图15, 当光子走右边时(实际上同时走左右), 就将偏振取反
图12, 图13变成$$\pm \frac{1}{\sqrt2}\left(\mid 0\rangle + \mid 1\rangle\right)$$
图14, 图15都只改变了一个符号, 故变为$$\pm \frac{1}{\sqrt2}\left(\mid 0\rangle - \mid 1\rangle\right)$$
对于不同的函数, 图像会不一样, 常数函数亮的地方会是平衡函数暗的地方, 因为Half-waveplate delays the photon on exactly half of its period, 使原本两个波峰中的一个变成波谷, 相消变暗
More Algorithms
Deutsch-Jozsa Problem
对于公式(9), 在减号两边同时应用H门, 得到两个和式, 考虑这两个和式中$y=0$的那一小项, 正好相消
即观察前n位, 不可能全为0
经典计算机需要$2^{n-1}+1$次, 量子计算机只需1次
Bernstein-Vazirani Problem
经典计算机需要n次, 量子计算机只需1次
Simon’s Problem
问题描述:
对于函数$f : \{0,1\}^n \rightarrow \{0,1\}^n$, 保证存在一个$a \in \{0,1\}^n$, 使得对于任意x, $f(x)=f(y)$成立当且仅当$x=y$或$y = x\oplus a$, 求$a$
对于笔记(10)上面一行的公式, 当$a\cdot y$不为0(即为1时), 加法左边和右边相消为0, 所以最后剩下的一定满足$a\cdot y=0$
经典计算机需要$2^{n-2}$次(假设我们有足够的内存), 量子计算机只需O(n)次
尾记
这些量子算法都使用了量子平行性(quantum parallelism), 使量子计算能力指数级增长
这些量子算法都使用了量子纠缠(entanglement), 通过改变每个状态的概率来得到结果
自己的看法
H门非常有意思, 它实现了量子平行性, 让单一的状态变成一个叠加态(superposition), 让量子计算机能力能指数级增加.
同时各种门(例如CNOT)将各个量子比特纠缠(纠缠即不可分, 而CNOT正是不可分的), 通过一些办法使错误的(不可能的)结果的概率相消成为0, 使得最后能得到的只有正确结果
官方笔记
