参考：量子计算与量子信息1。

基本概念

量子计算和量子信息的研究对象是用量子力学系统能够完成的信息处理任务，牵扯到量子力学、计算机科学、信息论、密码系统。

量子比特

量子计算和量子信息建立在量子比特的基础上。

量子比特像经典比特一样有两个可能状态，分别是：
$$
|0\rangle\ \ \ \ \ \ \ \ \ |1\rangle
$$
记号$|\rangle$叫做Dirac记号，在量子力学中表示状态。

例如，一个量子比特处于状态：
$$
\frac1{\sqrt 2}|0\rangle+\frac 1{\sqrt 2}|1\rangle
$$
通过以上可知，测量时有$50%$概率得到$0$，有$50%$概率得到$1$，这是一个很常见的状态，记作$|+\rangle$。

量子比特的存在是真实的，例如光子的两种不同极化、均匀电磁场核自旋的取向以及围绕单原子的电子的状态。

在原子模型中，电子可能处在基态，也可能处在激发态，分别用$|0\rangle,|1\rangle$来表示，如果用光照射原子，如果能量合适且时间够长，电子可以在$|0\rangle$和$|1\rangle$状态之间移动。如果缩短光照时间，开始处在$|0\rangle$的电子可以移动到$|0\rangle$到$|1\rangle$的中途，也就是进入$|+\rangle$状态。

回到之前的那个概率，根据$|\alpha|^2+|\beta|^2=1$，可以转化为几何表示（$\theta,\varphi,\gamma$为实数）：
$$
|\psi\rangle=e^{i\gamma}(\cos\frac \theta2|0\rangle+e^{i\varphi}\sin\frac \theta2|1\rangle)
$$
但是，由于公共因子$e^{i\gamma}$没有观测效应，所以可以约去，得到有效形式：
$$
|\psi\rangle=\cos\frac \theta2|0\rangle+e^{i\varphi}\sin\frac \theta2|1\rangle
$$
数$\theta,\varphi$定义了三维单位球面的一个点，这个单位球面称作Bloch球面：

理论上来说，由于单位球面有无穷多的点，所以一个量子比特可以包含无穷多的信息，但是我们每次观测只会得到$0$或$1$，测量会改变量子比特的状态，会从叠加态坍缩到和我们测量结果相容的特定状态。例如，对于$|+\rangle$的测量结果是$0$，那么这个量子比特测后状态为$|0\rangle$，所以事实上我们需要测量无穷多完全相同的量子比特才能确定叠加态等式中的$\alpha,\beta$。

多量子比特

假设有两个量子比特，共有四种可能状态：$00,01,10,11$。

同样的，一个双量子比特有四个基态，可以记作$|00\rangle,|01\rangle,|10\rangle,|11\rangle$。

一对量子比特可以处于四个基态的叠加，它的量子状态也包含相应基态的复系数（称作幅度），这样描述双量子比特的状态向量为：
$$
|\psi\rangle=\alpha_{00}|00\rangle+\alpha_{01}|01\rangle+\alpha_{10}|10\rangle+\alpha_{11}|11\rangle
$$
同样的，测量结果$x=00,01,10,11$的概率是$|\alpha_x|^2$，测量之后量子比特处于$|x\rangle$状态，概率之和为$1$的归一化条件表示为：
$$
\sum_{x\in{0,1}^2}|\alpha_x|^2=1
$$
但是，我们测量也可以只测量一个，可以知道测量第一个量子比特为$0$的概率为$|\alpha_{00}|^2+|\alpha_{01}|^2$，测量后的状态为：
$$
|\psi’\rangle=\frac{\alpha_{00}|00\rangle+\alpha_{01}|01\rangle}{\sqrt{|\alpha_{00}|^2+|\alpha_{01}|^2}}
$$
测量后的状态被分母归一化后，仍然满足归一化条件。

Bell态或EPR对是一个重要的双量子态，这是量子隐形传态和超密编码的关键要素，也是其他有趣的量子状态的原型：
$$
\frac{|00\rangle+|11\rangle}{\sqrt2}
$$
Bell态的性质：当测量第一个比特时，有$\frac 12$概率得到$0$并进入测后状态$|\varphi’\rangle=|00\rangle$；$\frac 12$的概率得到$1$并进入测后状态$|\varphi’\rangle=|11\rangle$。也就是说对第二比特的测量结果和第一量子比特的结果一样。

更一般地，可以引入$n$量子比特系统，基态形如：
$$
|x_1x_2\cdots x_n\rangle
$$
且这个量子状态由$2^n$个幅度确定。

量子计算

类似于经典计算机是包含了连线和逻辑门的线路构造的，量子计算机是由包含了连线和基本量子门排列、能处理量子信息的量子线路构造的。

单量子比特门

经典计算机线路是由连线和逻辑门构成，连线用来传送信息，逻辑门用来处理信息，将一种形式的信息转换为另一种。

例如对于单比特的逻辑门，唯一的不平凡门就是非门，得到$0→1,1→0$，也就是状态交换。

类似的去研究量子比特的量子非门，量子非门的作用是线性的：
$$
\alpha|0\rangle+\beta|1\rangle→\alpha|1\rangle+\beta|0\rangle
$$
根据线性性质，可以将量子非门用矩阵表示：
$$
X=\begin{bmatrix}0&1\\1&0\end{bmatrix}
$$
也可以把量子态$\alpha|0\rangle+\beta|1\rangle$写成向量形式，上面为$|0\rangle$的幅度，下面为$|1\rangle$的幅度：
$$
\begin{bmatrix}\alpha\\\beta\end{bmatrix}
$$
得到量子非门的输出：
$$
X\begin{bmatrix}\alpha\\\beta\end{bmatrix}=\begin{bmatrix}\beta\\\alpha\end{bmatrix}
$$
所以，单量子比特的量子门可以用$2\times2$的矩阵给出，这里用作量子门的矩阵有限制，需要让量子状态满足归一化条件，表示单量子比特门的矩阵$U$满足的条件为酉性，满足：
$$
U^\dagger U=I
$$
这里的$U^\dagger$是$U$的共轭转置矩阵，对$2\times 2$的单位阵是和很容易验证的。

共轭矩阵将矩阵元素中复数的参数取反，例如：

对于矩阵：
$$
A=\begin{bmatrix}
3+i&5\\2-2i&i
\end{bmatrix}
$$
得到共轭转置矩阵：
$$
A=\begin{bmatrix}
3-i&2+2i\\5&-i
\end{bmatrix}
$$

酉性是对量子门的唯一限制，每一个酉矩阵都定义一个有效的量子门。和只有一种普通的不平凡单比特门（非门）不同，这里有很多不平凡的单比特量子门，例如常用的$Z$门：
$$
Z=\begin{bmatrix}1&0\\0&-1\end{bmatrix}
$$
$Z$门保持$|0\rangle$不变，反转$|1\rangle$的符号为$-|1\rangle$：
$$
\alpha|0\rangle+\beta|1\rangle→\alpha|0\rangle-\beta|1\rangle
$$
还有常用的$Haramard$门：
$$
H=\frac 1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}
$$
这个门将$|0\rangle$变为$|0\rangle$到$|1\rangle$的中间态$\frac{|0\rangle+|1\rangle}2$，将$|1\rangle$变为$|0\rangle$到$|1\rangle$的中间态$\frac{|0\rangle-|1\rangle}2$，且有$H^2=I$，将两次应用到一个状态等于啥也没做：
$$
\alpha|0\rangle+\beta|1\rangle→\alpha\frac{|0\rangle+|1\rangle}2+\beta\frac{|0\rangle-|1\rangle}2
$$
这里的$Hadamard$操作可以在Bloch球面上表示一下，$Hadamard$操作是先绕$y$轴旋转了$90°$，再绕$x$轴旋转了$180°$：

这里的旋转都是对着轴X出逆时针。

由于存在无穷多的$2\times2$酉矩阵，所以量子比特门的种类也是无限的。但是整个门集合的属性可以从一个小的集合得到，这里引出单量子比特矩阵分解：
$$
U=e^{i\alpha}\begin{bmatrix}
e^{-\frac{i\beta}2}&0\\0&e^{\frac{i\beta}2}
\end{bmatrix}
\begin{bmatrix}
\cos\frac \gamma 2&-\sin\frac\gamma2\\
\sin\frac\gamma2&\cos \frac \gamma 2
\end{bmatrix}
\begin{bmatrix}
e^{-\frac{i\delta}2}&0\\0&e^{\frac{i\delta}2}
\end{bmatrix}
$$
这里的$\alpha,\beta,\gamma,\delta$都是实数，第二个矩阵是普通的旋转，第一个和最后一个矩阵可以理解为在不同平面的旋转。任意的单量子比特门可以基于量子门的一个有限集合构造。

多量子比特门

对于比特上任意函数都可以仅用与非门复合来计算，称与非门为一个通用门。多量子比特门的原型是受控非门。

受控非门有两个输入比特，分别是控制量子比特和目标量子比特，可以和普通的逻辑门对照一下：

这里的矩阵表示对应的四维列向量是两个量子比特各自的状态通过张量积组合成一个四维向量：
$$
|{\phi\psi}\rangle=a|{00}\rangle+b|{01}\rangle+c|{10}\rangle+d|{11}\rangle
$$
得到列向量：
$$
v=\begin{bmatrix}
a\\b\\c\\d
\end{bmatrix}
$$

其他基态的测量

例如对于量子比特我们选择基态为$|+\rangle=\frac{|0\rangle+|1\rangle}{\sqrt 2}$和$|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt 2}$，对于状态$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$可以重新表示为：
$$
|\psi\rangle=\alpha|0\rangle+\beta|1\rangle=\frac{\alpha+\beta}{\sqrt2}
|+\rangle+\frac{\alpha-\beta}{\sqrt 2}|-\rangle
$$
一般地，对于任意基态$|a\rangle$和$|b\rangle$，可以把任意状态表示为线性组合$\alpha|a\rangle+\beta |b\rangle$，若这两个基态状态是正交的，那么可以相对基进行测量。以$|\alpha|^2$概率导致$a$，以$|\beta|^2$概率导致$b$，正交约束可以保证概率条件$|\alpha|^2+|\beta|^2=1$。

量子线路

量子线路的读法为从左到右，每条线代表量子线路的连线，连线不一定是物理上的接线，而是对应一段时间或一个从空间的一处移动到另一处的物理粒子（如光子）。

量子线路不允许出现回路，是无环的；且量子力学禁止量子比特的复制，就不存在扇入（连线汇合）和扇出（产生一比特的多个拷贝）操作。

定义受控$U$门，是作用在$n$量子比特的任意酉矩阵，原型是受控非门。受控$U$门具有单一的控制量子比特，用带黑点的线表示，还有$n$个目标量子比特，用标上$U$的盒子表示。规定控制量子比特置$0$时目标量子比特不受影响，置$1$时门$U$作用到目标量子比特上。

在量子线路上还有一个重要操作是测量，用一个仪表符号表示，将单量子比特的状态变成概率意义下的经典比特$M$（用双线表示）。

对于普通比特来说，我们可以使用经典受控非门得到两个相同状态的比特，那么量子比特是否也可以进行复制呢？

例：Bell态

对于一个$Hadamard$门后连接一个受控非门，给出四个计算基态：

首先$Hadamard$变换将输入的量子比特变换为叠加态，然后该状态作为受控非门的控制输入。当控制为$1$时，目标量子比特被反转输出，输出状态为$Bell$态，也叫$EPR$态或$EPR$对。

对于模拟的线路，有：
$$
|\beta_{00}\rangle = \frac{|00\rangle+|11\rangle}{\sqrt 2}
$$

$$
|\beta_{01}\rangle = \frac{|01\rangle+|10\rangle}{\sqrt 2}
$$

$$
|\beta_{10}\rangle = \frac{|00\rangle-|11\rangle}{\sqrt 2}
$$

$$
|\beta_{11}\rangle = \frac{|01\rangle-|10\rangle}{\sqrt 2}
$$

有公式（注意$\overline y$是$y$的非）：
$$
|\beta_{xy}\rangle=\frac{|0,y\rangle+(-1)^x|1,\overline{y}\rangle}{\sqrt2 }
$$

例：量子隐形传态

量子隐形传态是在发送方和接收方都没有量子通信信道连接的情况下移动量子状态的一项技术。

模拟一个环境，Alice和Bob之前相遇过，在一起时产生了一个$EPR$对，分开时每个人带走了$EPR$对的一个量子比特，许多年后Bob躲起来，Alice有一项使命要向Bob发送一个量子比特$|\psi\rangle$，她不知道这个量子比特的状态，且只能给Bob发送经典信息。

问题的困难在于：

①Alice不知道发给Bob的量子比特状态$|\psi\rangle$；

②根据量子力学，不能去拷贝这个状态；

③由于$|\psi\rangle$取值于连续的空间，描述它需要无穷多的经典信息，也需要无穷多的时间向Bob描述这个状态。

解决方法：Alice让$|\psi\rangle$和$EPR$对在她的那一半相互作用，测量这两个量子比特，得到四个可能结果中的一个（$00,01,10,11$），将这个测量结果发送给Bob，根据Alice的信息，Bob对另一半$EPR$对进行四个操作的一种，这样甚至就可以恢复原始$|\psi\rangle$。

注意，这里的$EPR$对生成时的输入是确定的，生成之后分离，对其中一个系统的测量也会立即影响到其他系统状态的统计性质。

接下来看看为什么这样可以成功。对于隐形传态的状态$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$，$\alpha,\beta$是未知的幅度，输入状态为$|\psi_{0}\rangle$。

$$
\begin{align}
|\psi_0\rangle&=|\psi\rangle|\beta_{00}\rangle\
\\
&=\frac1{\sqrt2}[\alpha|0\rangle(|00\rangle+|11\rangle)+\beta|1\rangle(|00\rangle+|11\rangle)]
\end{align}
$$
约定前两个量子比特属于Alice，第三个量子比特属于Bob，可知Alice的第二个量子比特和Bob的量子比特是从同一个$EPR$状态来的。Alice将她的量子比特送到受控非门（控制置$1$时目标取反），得到：
$$
|\psi_1\rangle=\frac1{\sqrt2}[\alpha|0\rangle(|00\rangle+|11\rangle)+\beta|1\rangle(|10\rangle+|01\rangle)]
$$
让第一量子比特通过$Hadamard$门，得到：
$$
|\psi_2\rangle=\frac1{2}[\alpha(|0\rangle+|1\rangle)(|00\rangle+|11\rangle)+\beta(|0\rangle-|1\rangle)(|10\rangle+|01\rangle)]
$$
变换得到：
$$
\begin{align}
|\psi_2\rangle=&\frac1{2}[|00\rangle(\alpha|0\rangle+\beta|1\rangle)+|01\rangle(\alpha|1\rangle+\beta|0\rangle)\\&+|10\rangle(\alpha|0\rangle-\beta|1\rangle)+|11\rangle(\alpha|1\rangle-\beta|0\rangle)]
\end{align}
$$
这个表达式分为四项，第一项状态$|00\rangle$中含有Alice的量子比特，状态$\alpha|0\rangle+\beta|1\rangle$包含Bob的量子比特（即状态$|\psi\rangle$），如果Alice测量得到了$|00\rangle$，那么Bob的系统处于状态$|\psi\rangle$，根据Alice测量的四种结果，可以得到Bob的四种测后状态。

当Bob知道了测量结果之后，就可以根据Alice的结果用适当的量子门恢复出$|\psi\rangle$。当为$00$时不需要做什么；当$01$时可以用$X$门；当$10$时可以用$Z$门；当$11$时可以先用$X$门再用$Z$门恢复。也就是Bob需要变换：
$$
Z^{M_1}X^{M_2}
$$

量子算法

Toffoli门

Toffoli门可以用来模拟经典的逻辑电路。

Toffoli门有三个输入比特和三个输出比特，两个控制比特和一个目标比特，当控制比特都置$1$时反转，否则不变。

Toffoli门是一种可逆门，当我们连续作用两次在一组比特上：
$$
(a,b,c)→(a,b,c\oplus ab)→(a,b,c)
$$

Toffoli门可以用来模拟与非门和扇出操作，通过这些基本的操作就可以模拟经典电路中所有的其他元件：

Toffoli门也可以作为量子逻辑门实现，Toffoli门的量子逻辑实现就是按照经典Toffoli门置换基态，例如状态$|110\rangle$会被反转进入状态$|111\rangle$。最终能得到一个变换的$8\times8$矩阵$U$，这个$U$也是酉矩阵。

对于经典计算机产生计算的随机比特的能力，量子计算机也可以轻松的模拟，只要制造一个处于状态$| 0\rangle$的量子比特，送进一个$Hadamard$门就可以产生$\frac{|0\rangle+|1\rangle}{\sqrt{2}}$，然后再测量即可。

量子并行性

量子并行性是使量子计算机可以同时计算函数$f(x)$在许多不同的$x$处的值。

设有函数：
$$
f(x):{0,1}→{0,1}
$$
在量子计算机上，计算这个函数的简便方法是考虑初态为$|{x,y}\rangle$的双量子比特量子计算机，通过变换得到$|{x,y\rangle\oplus f(x)}$，第一位为数据寄存器，第二位为目标寄存器。这个变换映射为$U_f$，它易证明是酉的。这里如果$y=0$，那么第二个量子比特的末状态就是$f(x)$的值。

在线路中，应用$U_f$得到的新状态是：
$$
\frac{|{0,f(0)}\rangle+|{1,f(1)}\rangle}{\sqrt 2}
$$

对于右图的变换，称$H^{\otimes2}$为两个$Hadamard$门的并行作用，$\otimes$为张量积。例如当$n=2$时就有：
$$
(\frac{|0\rangle+|1\rangle}{\sqrt2})(\frac{|0\rangle+|1\rangle}{\sqrt2})=
\frac{|{00}\rangle+|{01}\rangle+|{10}\rangle+|{11}\rangle}2
$$
对于$n$重量子比特上的$Hadamard$变换从全$|0\rangle$出发，得到：
$$
\frac{1}{\sqrt{2^n}}\sum_x|x\rangle
$$
所以，$Hadamard$变换产生了所有计算基态的平衡叠加，且效率极高，用$n$个门可以产生$2^n$个状态叠加。

表面上我们只进行了一次函数运算，但是由于量子并行性我们却能求出所有可能的值，但是由于测量状态只能测量到不同结果中的一种，量子计算还要求从叠加态得到一个$f(x)$值更高的信息抽取能力。

Deutsch算法

Deutsch算法把量子并行性和量子力学中称为干涉的性质结合了起来。

实现这个算法的线路在已有的图1.17上进行了修改，使用$Hadamard$门将第一量子比特变为叠加态$\frac{|0\rangle+|1\rangle}{\sqrt2}$，还使用$Hadamard$门将第二量子比特也变为叠加态$\frac{|0\rangle-|1\rangle}{\sqrt2}$。

现在输入状态$|\psi_0\rangle=|01\rangle$，都通过$Hadamard$门之后进入叠加态：
$$
|\psi_1\rangle=[\frac{|0\rangle+|1\rangle}{\sqrt2}][\frac{|0\rangle-|1\rangle}{\sqrt2}]
$$
当应用$U_f$时，状态$|x\rangle\frac{|0\rangle-|1\rangle}2$进行变换得到$(-1)^{f(x)}|x\rangle\frac{|0\rangle-|1\rangle}2$，会得到两种情况：
$$
|\psi_2\rangle=\begin{cases}
±[\frac{|0\rangle+|1\rangle}{\sqrt2}][\frac{|0\rangle-|1\rangle}{\sqrt2}],f(0)=f(1)\\
±[\frac{|0\rangle-|1\rangle}{\sqrt2}][\frac{|0\rangle-|1\rangle}{\sqrt2}],f(0)\not=f(1)
\end{cases}
$$
在作用一个$Hadamard$门得到：
$$
|\psi_3\rangle=\begin{cases}
±|0\rangle[\frac{|0\rangle-|1\rangle}{\sqrt2}],f(0)=f(1)\\
±|1\rangle[\frac{|0\rangle-|1\rangle}{\sqrt2}],f(0)\not=f(1)
\end{cases}
$$
根据异或的性质，可以直接简写为：
$$
|\psi_3\rangle=±|f(0)\oplus f(1)\rangle[\frac{|0\rangle-|1\rangle}{\sqrt2}]
$$
根据这个结果可以得到当我们测量第一量子比特的结果，就可以确定$f(0)\oplus f(1)$

，只计算这一次，就可以确定$f(x)$的全局性质，对于经典设备来说，这至少需要两次计算。

Deutsch-Jozsa算法

Deutsch算法是一般量子算法（Deutsch-Josza算法）的简单例子，一个典型应用就是Deutsch问题：

阿姆斯特丹的Alice从$0$到$2^{n-1}$选择一个数$x$发送给波士顿的Bob，Bob计算出一个函数值$f(x)$，且这个函数值不是$0$就是$1$，发送给Alice。

这里的Bob使用的函数分为两类：要么函数对所有可能的取值都为固定常数，要么函数就是平衡函数（可能取值中一半取$0$，一半取$1$）。

经典情形中，Alice一封信只能发送给Bob一个$x$值，简单计算可知最坏情况下需要询问$\frac{2^n}2+1$次才能确定函数是什么类型。但是如果Alice可以交换量子比特，且Bob统一使用酉变换计算$f(x)$，那么一次通信Alice即可达成目的。

量子计算（一）