第58页 Introduction and Overview 1.4-1.6

量子计算机上的经典计算，例如Toffoli门：
($$|a, b, c\rangle \rightarrow |a, b, c\oplus ab \rangle$$)
若连续进行两次：
($$|a, b, c\rangle \rightarrow |a, b, c\oplus ab \rangle \rightarrow |a,b,c\rangle$$)
即Toffoli门是可逆门，逆是它本身。
矩阵为：
($$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0  & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0  & 0 & 0 & 0 & 0\\ 0 & 0 & 0& 1  & 0 & 0 & 0 & 0\\  0 & 0 & 0 & 0 & 1  & 0 & 0 & 0 \\  0 & 0 & 0 & 0  & 0 & 1  & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1& 0\end{bmatrix}$$)
当然量子计算机的目的显然不是为了模拟经典计算机。

量子并行性
举例阐述原理：
设($f(x): \left\{0,1\right\}\rightarrow\left\{0,1\right\}$)，考虑初态为($|x,y\rangle$)的双量子比特的量子计算机。
易正明存在Unitary矩阵($U_f$)使得($|x,y\rangle \rightarrow |x,y\oplus f(x)\rangle$)。若y=0，则第二个qubit的终态就是f(x)的值。
($$
\left\{
\begin{align}
x: |0\rangle \xrightarrow{Hadamard} \frac{|0\rangle+|1\rangle}{\sqrt{2}} \\
y: |0\rangle\
\end{align}
\right\}
\xrightarrow{U_f} \frac{|0,f(0)\rangle+|1,f(1)\rangle}{\sqrt{2}}$$)
即单个f(x)线路用来同时计算了多个x的函数值。
($$|0\rangle ^{\otimes n} |0\rangle \xrightarrow{Hadamard} \xrightarrow{U_f} \frac{1}{\sqrt{2^n}}\sum_{x}|x\rangle |f(x)\rangle$$)

Deutsch 算法
($$|\psi _0\rangle = |01\rangle \xrightarrow{Hadamard\times 2} |\psi _1\rangle=[\frac{|0\rangle + |1\rangle}{\sqrt{2}}][\frac{|0\rangle - |1\rangle}{\sqrt{2}}]$$)
($U_f$)作用到($|x\rangle(|0\rangle -|1\rangle)/\sqrt{2}$)得到($(-1)^{f(x)}|x\rangle(|0\rangle -|1\rangle)/\sqrt{2}$) 
(因为($x=\left\{0,1\right\}$)且($f(x)=\left\{0,1\right\}$)，代入计算可以很容易地得到上述结果。)
($U_f$)作用到($|\psi_1\rangle$)上可得
($$
|\psi_2\rangle=
\begin{cases}
\pm[\frac{|0\rangle + |1\rangle}{\sqrt{2}}][\frac{|0\rangle - |1\rangle}{\sqrt{2}}] & {f(0)=f(1)} \\
\pm[\frac{|0\rangle - |1\rangle}{\sqrt{2}}][\frac{|0\rangle - |1\rangle}{\sqrt{2}}] & {f(0)\neq f(1)}
\end{cases}
$$)
Hadamard作用到($|\psi_2\rangle$)上
($$
|\psi_3\rangle=
\begin{cases}
\pm|0\rangle[\frac{|0\rangle - |1\rangle}{\sqrt{2}}] & {f(0)=f(1)} \\
\pm|1\rangle[\frac{|0\rangle - |1\rangle}{\sqrt{2}}] & {f(0)\neq f(1)}
\end{cases}
$$)
即
($$|\psi_3\rangle=\pm|f(0)\oplus|f(1)\rangle[\frac{|0\rangle - |1\rangle}{\sqrt{2}}] $$)
所以，通过测量第一量子比特就可以确定($f(0)\oplus f(1)$)。


Deutsch-Jozsa 算法
与前者差不多的，就是把初始比特换成了($|0\rangle ^{\otimes n}|1\rangle$)

目前有三类优于已知经典算法的量子算法：
1. 基于Fourier变换的量子算法：
如，Shor's fast algorithms for factoring and discrete logarithm；
2. 量子搜索算法；
3. 量子仿真。

量子计算的能力
P
NP
NP-complete
PSPACE
BQP

实验量子信息处理
Stern-Gerlach实验：一般的量子力学书上都讲了的

实际处理中可能的障碍主要有：1) 噪声；2) 量子力学不正确。

Threshold theorem\阀值定理


量子信息
Shannon entropy: ($H(p_j)=-\sum_j p_j log(p_j)$)

von Neumann entropy

量子不可区分性
非正交量子状态不可区分

(to be continued...)