简介与概述¶

研究对象：使用量子力学系统能够完成的信息处理任务

基本概念涉及领域：量子力学、计算机科学、信息论和密码体系

历史背景¶

物理学¶

危机：经典物理学做出荒谬的预言

解决：量子力学理论创立

量子力学

内容：数学框架或物理理论构建的规则集
特点：规则简单，违背直觉

量子计算与量子信息的目标之一是开发工具以增进对量子力学的直观把握、并使其预言对人们更加通俗易懂

发展：对单量子系统的完全操控的兴趣

初步成就：在几个量子比特上进行几十次操作的小型量子计算机

计算机科学¶

诞生：图灵机（可编程计算机）

图灵机

丘奇-图灵论题(Church-Turing thesis)：任何可以在硬件上执行的算法，在通用图灵机上都有等效算法来完成

发展：

冯诺依曼模型
发明晶体管
摩尔定律：计算机的能力将以恒定的速率增长，大约每两年增长一倍

困境：随着电子器件越来越小，其功能会受到量子效应的干扰（摩尔定律最终失效）

解决：采用不同的计算模式——量子计算机相比传统计算机在速度上有本质的超越

”有效“与”非有效“模拟

计算复杂性：有效算法解决问题所用的时间是关于问题规模的多项式量级
加强版丘奇-图灵论题：使用图灵机可以有效地模拟任何算法过程

强丘奇-图灵论题挑战

模拟计算：某些类型的模拟计算机可以有效解地解决在图灵机上没有有效解决方案的问题

在评估计算模型的效率时必须考虑现实噪声的影响（解决：量子纠错码、容错量子计算理论）

随机算法：Solovay-Strassen测试算法利用随机性给出素数合数的概率

解决：修改强丘奇-图灵论题：任何算法都可以用概率图灵机有效模拟

用物理学定律推导出更强的丘奇-图灵论题：定义一种能够有效模拟任意物理系统（基于量子力学原理）的计算设备

证明量子计算机比图灵机和概率图灵机更强大的证据：

Peter Shor质因数分解、离散对数
Lov Grover量子搜索

费曼：建议建立基于量子力学原理的计算机以克服模拟量子力学系统的困难

设计量子计算机算法的困难：(1)经典直觉阻碍，难以利用量子效应 (2)算法需优于经典算法

信息论¶

诞生：香农发表现代信息与通信理论奠基性论文

关键：在数学上定义信息的概念

信息论基本定理：

无噪声信道编码定理：定量给出用于存储从信源发出信息所需的物理资源
有噪声信道编码定理：定量给出有噪声的信道能可靠传输的信息量（纠错码保护上限）

量子信息理论

定义”量子比特“作为切实的物理资源
发展量子纠错码，允许量子计算机在有噪声的情况下能有效计算，允许在带噪声的量子信道进行可靠通信

研究方向

量子纠错码理论

思想基础：经典线性编码理论

经典的纠错码思想已被证明在研究和理解量子纠错码上非常重要

目的：保护量子态免受噪声干扰

传输效率

超密编码：通过只将一个量子比特从发送方发送到接受方，来传输两个经典的比特

分布式量子计算：量子计算机可以用比经典计算机指数少的通信量来求解某些问题

挑战：寻找现实中重要且分布式量子计算比经典计算有实质性优势的问题

网络化量子信息论：量子信道网络的信息承载能力

初步成果：两个噪声很大的零容量信道并行运行，在量子力学中，将其中一个零容量信道反向可以获得非零容量的信息传输

主要问题：更好地理解量子信道网路的信息承载特性

密码学¶

内容：涉及彼此不一定信任的两方或多方的通信或计算的问题（最著名的加密学问题：保密通信）

私钥密码系统

工作方式：通信双方共享一个只有他们知道的私钥，Alice利用私钥加密信息并将加密信息发送给Bob，Bob需知道私钥以消除Alice施加的变换
问题：密钥分配（恶意第三方窃听）
解决：量子密钥分发

基本思想：利用观测一般会破坏被观测系统的量子力学原理

操作：丢弃有窃听者出现时建立的密钥位，并重新确定密钥

公钥密码系统

工作方式：不需要预先共享一个密钥，Bob需公布一个公钥让所有人得到，Alice利用此公钥加密她发送给Bob的信息，而第三方仅根据公钥来解密非常困难，但Bob有一个与该公钥配对的私钥使得他很容易解密
安全性：仅利用公钥解密是困难的
量子计算机在破解密码系统的应用

量子计算和量子信息¶

量子纠缠

价值：基本的自然资源，与能量、信息、熵及任何其他基本资源相当

未来方向¶

教会我们以物理的方式对计算进行思考

值得探索的内容丰富的新模型

任何物理理论都可以作为信息处理和通信的基础

学会用计算的方式思考物理学

新的工具可以用来跨越微小和相对复杂的事物之间的鸿沟：计算与算法为构建和理解此类系统提供了系统化的手段

基本概念¶

量子比特¶

概念：具有某些特定属性的数学对象，用实际的物理系统来实现

状态：

计算基矢态：$\ket{0},\ket{1}$（正交基）
叠加态：$\ket{\psi}=\alpha\ket{0}+\beta\ket{1}\ (\alpha,\beta\in \mathbb C,|\alpha|^2+|\beta|^2=1)$
二维复向量空间中的单位向量（连续状态）

"$\ket{}$"：Dirac记号

测量：

无法通过检查量子比特来确定它的量子态，当量子比特被观测时，只能得到0或1的测量结果
$P(0)=|\alpha|^2,P(1)=|\beta|^2\ (\therefore|\alpha|^2+|\beta|^2=1$ 归一化长度为1$)$

例：$\ket{+}=\dfrac{1}{\sqrt2}\ket0+\dfrac{1}{\sqrt2}\ket1\overset{测量}{\longrightarrow}\left\{\begin{array}{ll}0,&P=50\%,\\1,&P=50\%.\end{array}\right.$

几何表示： $$\begin{array}{l} \ket{\psi}=e^{i\gamma}(\cos\dfrac{\theta}{2}\ket0+e^{i\varphi}\sin\dfrac{\theta}{2}\ket1)\ \ket\psi=\cos\dfrac{\theta}{2}\ket0+e^{i\varphi}\sin\dfrac{\theta}{2}\ket1\ (\theta\in[0,\pi],\varphi\in[0,2\pi])\end{array} $$

验证：

\[\begin{array}{l} \alpha=e^{i\gamma}\cos\dfrac{\theta}{2},\beta=e^{i\gamma}e^{i\varphi}\sin\dfrac{\theta}{2}\\ \because|e^{i\theta}|=|\cos\theta+i\sin\theta|=1\\ \therefore|\alpha|^2+|\beta|^2=|e^{i\gamma}|^2\cos^2\dfrac{\theta}{2}+|e^{i\gamma}e^{i\varphi}|^2\sin^2\dfrac{\theta}{2}\\ =|e^{i\gamma}|^2\cos^2\dfrac{\theta}{2}+|e^{i\gamma}|^2|e^{i\varphi}|^2\sin^2\dfrac{\theta}{2}\\ =\cos^2\dfrac{\theta}{2}+\sin^2\dfrac{\theta}{2}=1\\ \therefore|e^{i\gamma}\cos\dfrac{\theta}{2}|^2=\cos^2\dfrac{\theta}{2},|e^{i\gamma}e^{i\varphi}\sin\dfrac{\theta}{2}|^2=\sin^2\dfrac{\theta}{2}\end{array} \]

($e^{i\gamma}$可以看作整体相位)

其中$\theta,\varphi$定义了单位三维球（布洛赫球面）上的一个点，如图：

对布洛赫球面的理解^1^：

事实上，最初我们是将$\ket\psi$表为$\ket0,\ket1$的线性组合。考虑到$|\alpha|^2+|\beta|^2=1$的限制并去除整体相位，我们可将其表为 $$ \ket\psi=\cos\theta\ket0+e^{i\varphi}\sin\theta\ket1 (\theta\in[0,\dfrac{\pi}{2}],\varphi\in[0,2\pi])) $$ 这样可以看作是$\ket1$确定的复平面$x-O-y$与$\ket0$确定的$z$轴构成的半球，如左图。

但问题在于，由于我们去除了整体相位，所有落在半球大圆上的态与$\ket1$等价，这样不利于我们建立一一对应关系。为此，我们将其缩为一个点，类似于拉伸操作，将半球面拉成一个完整的球面。

受到拉伸的影响，原先用$\theta$确定的态将由$\dfrac{\theta}{2}$来确定。令$\theta'=2\theta\in[0,\pi]$，故最终几何表示为 $$ \ket\psi=\cos\dfrac{\theta'}{2}\ket0+e^{i\varphi}\sin\dfrac{\theta'}{2}\ket1 (\theta\in[0,\pi],\varphi\in[0,2\pi]) $$ 这样便不难理解$\ket0,\ket1$为一组正交基了。

多量子比特¶

双量子比特

基矢态：$\ket{00},\ket{01},\ket{10},\ket{11}$
态向量$\ket\psi=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}$（$\alpha_{00},\alpha_{01},\alpha_{10},\alpha_{11}$称为振幅，$\ket{00},\ket{01},\ket{10},\ket{11}$称为计算基矢态）
测量：

测量整体：$P(x(=00,01,10,11))=|\alpha_x|^2$，测量后量子比特变为$\ket x$（归一化：$\sum\limits_{x\in\{0,1\}^2}|\alpha_x|=1$）
测量子集（一个量子比特）：

以测量第一个量子比特为例，$P(0)=|\alpha_{00}|^2+|\alpha_{01}|^2$，测量后量子比特变为$\ket{\psi'}=\dfrac{\alpha_{00}\ket{00}+\alpha_{01}\ket{01}}{\sqrt{|\alpha_{00}|^2+|\alpha_{01}|^2}}$，其中$\sqrt{|\alpha_{00}|^2+|\alpha_{01}|^2}$为归一化因子（使之满足归一化条件）

贝尔态（EPR对）

概念：$\dfrac{\ket{00}+\ket{11}}{\sqrt2}$
性质：第二个量子比特的测量结果总与第一个相同（贝尔态测量的相关性比任何经典系统存在的相关性都强）

验证：$\dfrac{\ket{00}+\ket{11}}{\sqrt2}\overset{测量第一个量子比特}{\longrightarrow}\left\{\begin{array}{lll}0,&P=50\%&\to\ket{\psi'}=\ket{00},\\1,&P=50\%&\to\ket{\psi'}=\ket{11}.\end{array}\right.$

n量子比特系统

计算基矢态：$\ket{x_1x_2\cdots x_n}$
量子态用$2^n$个振幅来刻画

量子计算¶

概念：描述量子态的变换

量子计算机由量子电路（电路+基本量子门）构造（类似经典计算机连线【信息传送】+逻辑门【操控信息】）

单量子比特门¶

性质

线性性（非线性行为将导致悖论）
可由$2\times2$矩阵$U$给出（将$\ket0$态变成矩阵第一列对应的状态，将$\ket1$态变成矩阵第二列对应的状态）

验证：记$X=(x_{ij})_{2\times2},\ket\psi=a_0\ket0+a_1\ket1$

\[ \begin{bmatrix} x_{11}&x_{12}\\ x_{21}&x_{22} \end{bmatrix} \begin{bmatrix} a_0\\ a_1 \end{bmatrix}= \begin{bmatrix} a_0x_{11}+a_1x_{12}\\ a_0x_{21}+a_1x_{22} \end{bmatrix}= \begin{bmatrix} a_0x_{11}\\ a_0x_{21} \end{bmatrix}+ \begin{bmatrix} a_1x_{12}\\ a_1x_{22} \end{bmatrix} \]

可以看到，$\ket0$前的系数$a_0$与$X_{.1}=\begin{bmatrix}x_{11}\\x_{21}\end{bmatrix}$结合，而$\ket1$前的系数$a_1$与$X_{.2}=\begin{bmatrix}x_{12}\\x_{22}\end{bmatrix}$结合

矩阵$U$需满足酉性条件$U^\dagger U=I$（其中$U^\dagger$为$U$的共轭转置$\overline{U^T}$）（量子门作用后仍需满足归一化要求）

酉性限制是量子们的唯一限制，任何酉矩阵都可以定义一个有效的量子门

量子门种类无穷，但任意量子比特上的任何量子计算，都可以用一组通用的有限个门构成的集合生成

结论：任何单量子比特酉门都可以分解成一个旋转和一个可以理解为绕$\hat z$旋转的门再加上一个全局相移

可以证明任何$2\times2$酉矩阵可以分解为

\[ U=e^{i\alpha} \begin{bmatrix} e^{-i\beta/2}&0\\ 0&e^{i\beta/2} \end{bmatrix} \begin{bmatrix} \cos\frac{\gamma}{2}&-\sin\frac{\gamma}{2}\\ \sin\frac{\gamma}{2}&\cos\frac{\gamma}{2} \end{bmatrix} \begin{bmatrix} e^{-i\delta/2}&0\\ 0&e^{i\delta/2} \end{bmatrix}\ (\alpha,\beta,\gamma,\delta\in \mathbb R) \]

进一步分解，无需实现任意的$\alpha,\beta,\gamma$，只需用一些特定的$\alpha,\beta,\gamma$来无限逼近任意的门

量子非门

作用：$\alpha\ket0+\beta\ket1\to\alpha\ket1+\beta\ket0$
矩阵表示：$X\equiv\begin{bmatrix}0&1\\1&0\end{bmatrix}$
输出：$X\begin{bmatrix}\alpha\\\beta\end{bmatrix}=\begin{bmatrix}\beta\\\alpha\end{bmatrix}$
电路表示：

Z门

作用：保持$\ket0$不变，翻转$\ket1$的符号变为$-\ket1$
矩阵表示：$Z\equiv\begin{bmatrix}1&0\\0&-1\end{bmatrix}$
电路表示：

阿达玛门

作用：$\ket0\to\dfrac{\ket0+\ket1}{\sqrt2},\ket1\to\dfrac{\ket0-\ket1}{\sqrt2}$
矩阵表示：$H\equiv\dfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$
几何意义：（以$\ket\psi=\dfrac{\ket0+\ket1}{\sqrt2}$为例，$\because H^2=E\therefore H\ket\psi=H^2\ket0=\ket0$）

先绕$\hat y$轴旋转$90^\circ$，再绕$\hat x$旋转$180^\circ$；
或绕$\dfrac{\hat x+\hat z}{\sqrt2}$旋转$180^\circ$

电路表示：

多量子比特门¶

受控非门

概念：控制量子比特、目标量子比特
作用：

控制量子比特为0，则目标量子比特不变；控制量子比特为1，则目标量子比特翻转：

$\ket{00}\to\ket{00},\ket{01}\to\ket{01},\ket{10}\to\ket{11},\ket{11}\to\ket{10}$
或视作经典异或门的拓展：$\ket{A,B}\to\ket{A,B\oplus A}$（控制量子比特与目标量子比特做异或运算，并存储到目标量子比特上）

经典门无法被视作酉门：异或门、与非门本质上不可逆（由$A\oplus B$的输出无法确定输入$A,B$，存在信息的损失），而酉量子门总是可逆的

矩阵表示：$U_{CN}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$，易知$U_{CN}^\dagger U_{CN}=I$

对矩阵的理解：根据矩阵的定义（线性映射基上取值在到达空间基下的坐标），我们可以将矩阵视作一个“处理器”，如图：

其中矩阵的上方为输入段，左方为输出端。我们将出发空间的向量坐标排布在对应的基的上方，则每一个坐标与下方的列向量相乘得到的列向量为这个分量上的输出，将所有输出叠加起来即为矩阵作用后的结果。

按照这样的理解，我们完全可以将矩阵作用在向量上视作如下的“电路”：

回到量子门的矩阵表示上，我们便不难理解矩阵的每一列分别描述了对应的计算基矢态的变换，具体而言，第n列描述的是n的二进制分解对应的计算基矢态的变换。

电路表示：
结论：任何多量子比特逻辑门可以由受控非门和单量子门组成（与非门通用性的量子对应）

除计算基外的测量¶

条件：$\ket a,\ket b$正交（满足概率限制$|\alpha|^2+|\beta|^2=1$）

结果：$\ket\psi=\alpha\ket a+\beta\ket b\overset{在\{\ket a,\ket b\}下测量}{\longrightarrow}\left\{\begin{array}{lll}a,&P=|\alpha|^2&\to\ket{\psi'}=\ket a,\\b,&P=|\beta|^2&\to\ket{\psi'}=\ket b.\end{array}\right.$

应用：用于观测结果的描述

在$\{\ket+,\ket-\}$下测量

$\ket+\equiv\dfrac{\ket0+\ket1}{\sqrt2},\ket-\equiv\dfrac{\ket0-\ket1}{\sqrt2}$

推导：

\[ \ket\psi=\alpha\ket0+\beta\ket1=\alpha\dfrac{\ket++\ket-}{\sqrt2}+\beta\dfrac{\ket+-\ket-}{\sqrt2}\\ =\dfrac{\alpha+\beta}{\sqrt2}\ket++\dfrac{\alpha-\beta}{\sqrt2}\ket- \]

结果：

\[ \left\{\begin{array}{lll}+,&P=\dfrac{|\alpha+\beta|^2}{2}&\to\ket{\psi'}=\ket+, \\-,&P=\dfrac{|\alpha-\beta|^2}{2}&\to\ket{\psi'}=\ket-.\end{array}\right. \]

量子电路¶

元件与约定¶

读法

从左向右
电路中的每一条线代表连线（物理连线/时间段/空间上的移动）
默认输入态全部为基矢态且由$\ket0$组成

特征

不允许“环路”（量子电路的一部分反馈到另一部分）：非周期电路
不允许扇入操作（连线汇合，单线包含所有位的按位或）：为不可逆操作，不是酉操作
不允许扇出操作（产生一个比特的多个拷贝）：量子力学禁止量子比特的拷贝

受控U门

概念：单量子比特控制位，n量子比特目标位
作用：控制位为0时不变，控制位为1时门U作用在目标量子比特上
电路表示：
特例：U=X时为受控非门（原型）

测量

作用：将$\ket\psi=\alpha\ket0+\beta\ket1$转化为一个经典比特$M(P(M=0)=|\alpha|^2,P(M=1)=|\beta|^2)$（画双线区分）
电路符号：

实例¶

量子态交换¶

$\forall$计算基$\ket{a,b}$:

\[\begin{array}{l} \begin{array}{ll} \ket{a,b}&\to\ket{a,a\oplus b}\\ &\to\ket{a\oplus(a\oplus b),a\oplus b}=\ket{b,a\oplus b}\ (a\oplus a=0)\\ &\to\ket{b,(a\oplus b)\oplus b}=\ket{b,a} \end{array}\end{array} \]

对上式的理解：

相当于变量x,y位运算交换(x\^=y\^=x\^=y)的量子版本

设原先的两个量子比特$\ket{\psi_1}=\alpha_1\ket a+\beta_1\ket b,\ket{\psi_2}=\alpha_2\ket a+\beta_2\ket b$，则$\ket{\psi_1}\ket{\psi_2}=\alpha_1\alpha_2\ket{a,a}+\alpha_1\beta_2\ket{a,b}+\alpha_2\beta_1\ket{b,a}+\beta_1\beta_2\ket{b,b}$经过上述电路作用后，所有计算基交换，变为$\alpha_1\alpha_2\ket{a,a}+\alpha_1\beta_2\ket{b,a}+\alpha_2\beta_1\ket{a,b}+\beta_1\beta_2\ket{b,b}=(\alpha_2\ket a+\beta_2\ket b)(\alpha_1\ket a+\beta_1\ket b)=\ket{\psi_2}\ket{\psi_1}$，即实现了量子态的交换

量子比特复制电路（不可复制）¶

\[\begin{array}{l} \ket\psi\ket0=[a\ket0+b\ket1]\ket0=a\ket{00}+b\ket{10}\to a\ket{00}+b\ket{11}\\ \ket\psi\ket\psi=a^2\ket{00}+ab\ket{01}+ab\ket{10}+b^2\ket{11}\\ \ket\psi\ket0=\ket\psi\ket\psi\Rightarrow ab=0\end{array} \]

所以仅$\ket\psi=\ket0,\ket\psi=\ket1$（经典信息）能够复制，一般量子态不能被复制（不可克隆定理）。

从隐藏信息的角度理解：
graph LR;
A["a|00>+b|11>"]--测量任意量子比特-->B[丢失隐藏信息]
A--复制-->C[保留隐藏信息]
一旦一个量子比特被测量，量子态的另一个量子比特也被确定，隐藏信息丢失；但如果量子比特已被复制，测量后该量子态的另一个量子比特仍然包含着隐藏信息，矛盾。故量子态不能被复制

贝尔态制备¶

记$\ket{xy}\to\ket{\beta_{xy}}$:

\[ \begin{array}{ll} \ket{00}\to\dfrac{\ket0+\ket1}{\sqrt2}\ket0=\dfrac{\ket{00}+\ket{10}}{\sqrt2}\to\dfrac{\ket{00}+\ket{11}}{\sqrt2}&\ket{\beta_{00}}=\dfrac{\ket{00}+\ket{11}}{\sqrt2}\\ \ket{01}\to\dfrac{\ket0+\ket1}{\sqrt2}\ket1=\dfrac{\ket{01}+\ket{11}}{\sqrt2}\to\dfrac{\ket{01}+\ket{10}}{\sqrt2}&\ket{\beta_{01}}=\dfrac{\ket{01}+\ket{10}}{\sqrt2}\\ \ket{10}\to\dfrac{\ket0-\ket1}{\sqrt2}\ket0=\dfrac{\ket{00}-\ket{10}}{\sqrt2}\to\dfrac{\ket{00}-\ket{11}}{\sqrt2}&\ket{\beta_{10}}=\dfrac{\ket{00}-\ket{11}}{\sqrt2}\\ \ket{11}\to\dfrac{\ket0-\ket1}{\sqrt2}\ket1=\dfrac{\ket{01}-\ket{11}}{\sqrt2}\to\dfrac{\ket{01}-\ket{10}}{\sqrt2}&\ket{\beta_{11}}=\dfrac{\ket{01}-\ket{10}}{\sqrt2} \end{array} \]

其中$\ket{\beta_{xy}}$被称为贝尔态（EPR态/EPR对）.

记忆：$\ket{\beta_{x,y}}\equiv\dfrac{\ket{0,y}+(-1)^x\ket{1,\bar y}}{\sqrt2}$

量子隐形传态¶

概念：在发送方和接收方之间没有量子通信信道连接的情况下，进行量子态的传输

任务：利用双方各持有的EPR对中的一个量子比特，传递一个单量子比特$\ket\psi$

上方两条连线为Alice系统，持有EPR对中的一个以及待传输量子比特$\ket\psi$，下方连线为Bob系统，持有EPR对的另一个

传输对象：$\ket\psi=\alpha\ket0+\beta\ket1$（$\alpha,\beta$未知）

输入态$\ket{\psi_0}=\ket\psi\ket{\beta_{00}}=\dfrac{1}{\sqrt2}[\alpha\ket0(\ket{00}+\ket{11})+\beta\ket1(\ket{00}+\ket{11})]$

Alice将她的态传入受控非门，得$\ket{\psi_1}=\dfrac{1}{\sqrt2}[\alpha\ket0(\ket{00}+\ket{11})+\beta\ket1(\ket{10}+\ket{01})]$

她随即将第一个量子比特送入阿达玛门，得$\ket{\psi_2}=\dfrac{1}{2}[\alpha(\ket0+\ket1)(\ket{00}+\ket{11})+\beta(\ket0-\ket1)(\ket{10}+\ket{01})]$

整理得：（将Alice的两个量子比特提出，便于测量） $$ \ket{\psi_2}=\dfrac{1}{2}[\ket{00}(\alpha\ket0+\beta\ket1)+\ket{01}(\alpha\ket1+\beta\ket0)+\ket{10}(\alpha\ket0-\beta\ket1)+\ket{11}(\alpha\ket1-\beta\ket0)] $$ 随后得到测量结果，在给定测量结果$xy$的情况下，我们可以读出Bob在此次测量后的状态$\ket{\psi_3(xy)}$：

\[\begin{array}{l} 00\mapsto\ket{\psi_3(00)}\equiv\alpha\ket0+\beta\ket1\\ 01\mapsto\ket{\psi_3(01)}\equiv\alpha\ket1+\beta\ket0\\ 10\mapsto\ket{\psi_3(10)}\equiv\alpha\ket0-\beta\ket1\\ 11\mapsto\ket{\psi_3(11)}\equiv\alpha\ket1-\beta\ket0\end{array} \]

Bob根据Alice告知的测量结果对他的态进行修正（测量结果第二位为1时需交换$\ket0,\ket1$（X门），在此基础上，第一位为1时需改变$\ket1$符号（Z门））：$\ket{\psi_4}=Z^{M_1}X^{M_2}\ket{\psi_3}$

电路图代表时间顺序，而矩阵乘法顺序与之相反

特性：

不允许超光速传递量子态：没有经典通信，量子隐形传态无法传递任何信息；而经典信道受到光速的限制
无法拷贝量子态：过程完成后，仅目标量子比特处于状态$\ket\psi$，而第一个量子比特随测量消失于计算基中

意义：强调了量子力学中不同资源的互换性：一个共享EPR+2经典量子比特$\overset{构成}{\longrightarrow}$至少等于一个量子比特通信的资源

量子算法¶

经典计算¶

原理：任何经典电路都可以用等价的仅含可逆原件的，由可逆门Toffoli门构成的电路代替

量子电路不能直接用于模拟经典电路：酉量子逻辑门本质上是可逆的，而许多经典逻辑门本质上是不可逆的

Toffoli门

概念：控制比特、目标比特
作用：当两个控制比特都置为1时目标比特翻转，否则不变：$(a,b,c)\to(a,b,c\oplus ab)$
矩阵表示：$\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}$
电路表示：
性质： 1. 可逆门，逆为自身 2. 可用于模拟不可逆经典逻辑门，并且保证量子计算机可以进行任何经典（确定性）计算机能够完成的计算

NAND	扇出

上方两比特表示NAND门的输入，第3个比特设置为标准状态1，称为辅助态	第2个比特是输入（0/1），其它两个比特是标准辅助态，扇出的输出在第2个和第3个比特

有了这两个操作就可以模拟电路中的其它元件，所以任意经典电路都可以被等价的可逆电路模拟

非确定经典计算机

令$\ket 0$通过一个阿达玛门得到$\dfrac{\ket0+\ket1}{\sqrt2}$，再测量这个态，结果是$\ket0,\ket1$各$50\%$的概率。为量子计算机提供了有效模拟不确定的经典计算机的能力

量子并行性¶

内涵：量子并行性允许量子计算机同时计算在不同$x$值下的函数值$f(x)$

原理：设$f(x):\{0,1\}\to\{0,1\}$，定义$U_f:\ket{x,y}\to\ket{x,y\oplus f(x)}$

第一个寄存器被称为数据寄存器，第二个寄存器被称为目标寄存器
酉变换
y = 0时，第二个比特的终态是值$f(x)$
暂且将$U_f$看作一个黑盒

在数据寄存器中制备叠加态$\dfrac{\ket0+\ket1}{\sqrt2}$，然后作用$U_f$： $$ \dfrac{\ket0+\ket1}{\sqrt2}\ket0= \dfrac{1}{\sqrt2}\ket{00}+\dfrac{1}{\sqrt2}\ket{10}\to\dfrac{1}{\sqrt2}\ket{0,f(0)}+\dfrac{1}{\sqrt2}\ket{1,f(1)} $$ 得到态$\dfrac{\ket{0,f(0)}+\ket{1,f(1)}}{\sqrt2}$：同时计算了$f(0),f(1)$的值，与经典的并行性用多个电路同时计算$f(x)$不同，利用量子计算机处于不同状态的叠加态的能力，单个$f(x)$电路用来同时计算多个$x$的函数值

任意比特函数的推广

初态制备为$\ket0$，将2个阿达玛门同时作用在n比特上（记作$H^{\otimes2}$），输出为 $$ (\dfrac{\ket0+\ket1}{\sqrt2})(\dfrac{\ket0+\ket1}{\sqrt2})=\dfrac{\ket{00}+\ket{01}+\ket{10}+\ket{11}}{2} $$ 一般地，当初态均为$\ket0$时，$n$比特上均作用阿达玛门（记作$H^{\otimes n}$）后得到 $$ \dfrac{1}{\sqrt{2^n}}\sum\limits_x\ket x $$ n比特输入x和单比特输出$f(x)$函数的量子并行性计算：制备$n+1$比特的量子态$\ket0^{\otimes n}\ket0$，然后将阿达玛变换作用在前$n$个量子比特上，再通过量子电路$U_f$，得到态$\dfrac{1}{\sqrt{2^n}}\sum\limits_x\ket x\ket{f(x)}$（即$\ket0^{\otimes n}\ket0\overset{H^{\otimes n}}{\longrightarrow}\overset{U_f}{\longrightarrow}\dfrac{1}{\sqrt{2^n}}\sum\limits_x\ket x\ket{f(x)}$，计算f一次计算f的所有值）

局限性：测量$\sum_x\ket{x,f(x)}$只能得到一个$x$的函数值$f(x)$（需要更高的信息抽取能力）

Deutsch算法¶

原理：将量子并行性和量子力学中的重要性质相干性结合起来

输入态$\ket{\psi_0}=\ket{01}$

通过两个阿达玛门后得到$\ket{\psi_1}=\left[\dfrac{\ket0+\ket1}{\sqrt2}\right]\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]$

易知，

\[\begin{array}{l}\ket x(\ket0-\ket1)/\sqrt2\overset{U_f}{\longrightarrow}\ket x(\ket{0\oplus f(x)}-\ket{1\oplus f(x)})/\sqrt2=\left\{\begin{array}{ll}\ket x(\ket0-\ket1)/\sqrt2,&f(x)=0,\\-\ket x(\ket0-\ket1)/\sqrt2,&f(x)=1.\end{array}\right.=(-1)^{f(x)}\ket x(\ket0-\ket1)/\sqrt2\end{array}\]

所以

\[ \begin{array}{ll}\ket{\psi_2}&=U_f(\dfrac{\ket0}{\sqrt2}\dfrac{\ket0-\ket1}{\sqrt2}+\dfrac{\ket1}{\sqrt2}\dfrac{\ket0-\ket1}{\sqrt2})\\ &=\dfrac{1}{\sqrt2}U_f(\ket0\dfrac{\ket0-\ket1}{\sqrt2})+\dfrac{1}{\sqrt2}U_f(\ket1\dfrac{\ket0-\ket1}{\sqrt2})\\ &=\dfrac{1}{\sqrt2}(-1)^{f(0)}\ket0\dfrac{\ket0-\ket1}{\sqrt2}+\dfrac{1}{\sqrt2}(-1)^{f(1)}\ket1\dfrac{\ket0-\ket1}{\sqrt2}\\ &=\left[\dfrac{(-1)^{f(0)}\ket0+(-1)^{f(1)}\ket1}{\sqrt2}\right]\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]\\ &=\left\{ \begin{array}{ll} \pm\left[\dfrac{\ket0+\ket1}{\sqrt2}\right]\left[\dfrac{\ket0-\ket1}{\sqrt2}\right],&f(0)=f(1),\\ \pm\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]\left[\dfrac{\ket0-\ket1}{\sqrt2}\right],&f(0)\not=f(1). \end{array} \right. \end{array} \]

最后阿达玛门作用在第一个量子比特得

\[ \ket{\psi_3}=\left\{ \begin{array}{ll} \pm\ket0\left[\dfrac{\ket0-\ket1}{\sqrt2}\right],&f(0)=f(1),\\ \pm\ket1\left[\dfrac{\ket0-\ket1}{\sqrt2}\right],&f(0)\not=f(1). \end{array} \right. \]

又$\left\{\begin{array}{ll}f(0)\oplus f(1)=0,&f(0)=f(1),\\f(0)\oplus f(1)=1,&f(0)\not= f(1).\end{array}\right.$

故$\ket{\psi_3}=\pm\ket{f(0)\oplus f(1)}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]$

通过测量第一个量子比特，我们可以确定$f(0)\oplus f(1)$.

结论：量子电路有能力通过计算一次$f(x)$来确定$f(x)$的全局性质

众多量子算法其设计的本质都是在精心选择函数和最终变换，使得能高效地确定有用的全局信息

Deutsch-Jozsa算法¶

Deutsch问题：Alice从$0\sim2^n-1$中选择一个数$x$寄给Bob，Bob计算出$f(x)$的值寄回Alice.其中$f(x)$值非零即一，且$f(x)$要么对所有$x$均为常数，要么为平衡函数，即对于所有可能的$x$一半取$1$，另一半取$0$。问Alice最少通信多少次能成功？

确定性经典算法：$2^{n-1}+1$次

量子计算：交换量子比特，使用一个酉变换$U_f$计算$f(x)$，1次

前n个量子比特为查询寄存器，最后一个量子比特为答案寄存器。

输入态$\ket{\psi_0}=\ket0^{\otimes n}\ket1$

经过阿达玛门作用，有$\ket{\psi_1}=\sum\limits_{x\in\{0,1\}^n}\dfrac{\ket x}{\sqrt{2^n}}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]$

由上知，$\ket x(\ket0-\ket1)/\sqrt2\overset{U_f}{\longrightarrow}(-1)^{f(x)}\ket x(\ket0-\ket1)/\sqrt2$

故使用$U_f:\ket{x,y}\to\ket{x,y\oplus f(x)}$得

\[ \begin{array}{ll} \ket{\psi_2}&=U_f(\sum\limits_{x}\dfrac{\ket x}{\sqrt{2^n}}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right])\\ &=\sum\limits_{x}\dfrac{1}{\sqrt{2^n}}U_f(\ket x\left[\dfrac{\ket0-\ket1}{\sqrt2}\right])\\ &=\sum\limits_{x}\dfrac{(-1)^{f(x)}\ket x}{\sqrt{2^n}}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right] \end{array} \]

由

\[\begin{array}{l}H\ket0=(\ket0+\ket1)/\sqrt2=((-1)^{0*0}\ket0+(-1)^{0*1}\ket1)/\sqrt2,\\ H\ket1=(\ket0-\ket1)/\sqrt2=((-1)^{1*0}\ket0+(-1)^{1*1}\ket1)/\sqrt2\end{array}\]

所以$H\ket x=\sum_{z\in\{0,1\}}(-1)^{xz}\ket z/\sqrt2$

推广到多量子比特，有$H^{\otimes n}\ket{x_1,\cdots,x_n}=\prod\limits_{i=1}^n\sum\limits_{z_i\in\{0,1\}}\dfrac{(-1)^{x_iz_i}\ket{z_i}}{\sqrt2}=\dfrac{\sum\limits_{z_1,\cdots,z_n}(-1)^{x_1z_1+\cdots+x_nz_n}\ket{z_1,\cdots,z_n}}{\sqrt{2^n}}$

记$x\cdot z$为$x,z$二进制表示下按位内积，则$H^{\otimes n}\ket x=\dfrac{\sum_z(-1)^{x\cdot z}\ket z}{\sqrt{2^n}}$

利用该结果计算$\ket{\psi_3}$得

\[ \begin{array}{ll} \ket{\psi_3}&=H^{\otimes n}\ket{\psi_2}\\ &=\sum\limits_x\dfrac{(-1)^{f(x)}}{\sqrt{2^n}}H^{\otimes n}\ket x\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]\\ &=\sum\limits_x\dfrac{(-1)^{f(x)}}{\sqrt{2^n}}\sum\limits_z\dfrac{(-1)^{x\cdot z}\ket z}{\sqrt{2^n}}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]\\ &=\sum\limits_x\sum\limits_z\dfrac{(-1)^{x\cdot z+f(x)}\ket z}{2^n}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right]\\ &=\sum\limits_z\sum\limits_x\dfrac{(-1)^{x\cdot z+f(x)}\ket z}{2^n}\left[\dfrac{\ket0-\ket1}{\sqrt2}\right] \end{array} \]

现对查询寄存器进行观察：

当$f(x)$为常函数时，态$\ket0^{\otimes n}$对应的振幅为$\sum_x(-1)^{x\cdot \overline{00\cdots0}+f(x)}/2^n=\sum_x(-1)^{f(x)}/2^n=(-1)^{f(x)}=\pm1$

由于$\ket{\psi_3}$为单位长度，所以其它振幅均为0，观测会使得查询寄存器中所有量子比特均为0；

当$f(x)$为平衡函数时，态$\ket0^{\otimes n}$的振幅为$\sum_x(-1)^{f(x)}/2^n=0$，测量会使得查询寄存器至少有一个量子比特不是0.

局限性：

尚未找到应用场景
与经典算法可比性差，计算函数的方式很不同
概率经典计算机同样可以优于确定性模型

量子算法总结¶

基于傅里叶变换的量子算法¶

离散傅里叶变换：$N$元复数集$x_0,\cdots,x_{N-1}$到复数集$y_0,\cdots,y_{N-1}$的变换，其中 $$ y_k\equiv\dfrac{1}{\sqrt N}\sum\limits_{j=0}^{N-1}e^{2\pi ijk/N}x_j $$ 量子力学形式：在计算基$\ket j$上定义$n$量子比特的线性变换$U(0\leqslant j\leqslant 2^n-1)$： $$ \ket j\to\dfrac{1}{\sqrt{2^n}}\sum\limits_{k=0}^{2^n-1}e^{2\pi ijk/2^n}\ket k $$ 易验证其为酉变换。

作用于叠加态： $$ \sum\limits_{j=0}^{2^n-1}x_j\ket j\to\dfrac{1}{\sqrt{2^n}}\sum\limits_{k=0}^{2^n-1}\left[\sum\limits_{j=0}^{2^n-1}e^{2\pi ijk/2^n}x_j\right]\ket k=\sum\limits_{k=0}^{2^n-1}y_k\ket k $$ 效率：经典$O(N\log N)=n2^n$，量子$O(\log^2N)=n^2$

局限：无法直接得到变换后的结果$y_k$

实例：Deutsch-Jozsa算法、Shor算法

量子搜索算法¶

问题：给定一个大小为$N$的状态空间，没有关于其结构的先验知识，我们想要在搜索空间中找到一个满足已知性质的元素

效率：经典$O(N)$，量子$O(\sqrt N)$

量子模拟¶

概念：模拟自然发生的量子系统（$kn$个量子比特）

局限：有效模拟并不意味着得到量子系统中所期望得到的信息（在测量后，一个$kn$个量子比特的模拟将会坍缩到一个确定的态，只留下$kn$比特的信息；在波函数中$c^n$比特的“隐藏信息”不能全部访问）

问题：研究能够有效抽取期望得到的答案的方法

作用：获取其它量子算法灵感的一般途径

摩尔定律的量子推论：如果能够每两年向量子计算机增加一个量子比特，量子计算机将保持与经典计算机相同的步伐

量子计算的能力¶

计算复杂性理论

复杂性类：一系列计算问题的集合，所有这些问题在求解所需的计算资源上具有相同的性质

复杂性类	说明
P	在经典计算机中能够快速求解
NP	在经典计算机中能够快速验证解
NP-complete	一个算法如果能够求解一个特殊的NP完全问题，那么稍微增加一点计算资源就可以被用于求解其它NP问题
PSPACE	能用有限空间资源求解的问题
BPP	如果允许有界的错误概率，能够用随机算法在多项式时间内求解
BQP	能够被量子计算机有效求解的计算问题（允许有界的错误概率）

经典与量子复杂性类的关系：

现有结论：

尽管量子计算机可以求解素因子分解问题（普遍相信在NP中），但由于不确定该问题是否为NP完全问题，无法知道量子计算机是否可以求解所有NP问题；且基于搜索的方法并不能有效的给出所有NP问题的解
量子计算机能有效地求解P类问题，但PSPACE以外的问题不能被有效求解
量子计算机计算能力严格强于经典计算机这一命题的证明很可能是不平凡的

实验量子信息处理¶

Stern-Gerlach实验¶

目的：表明量子比特结构是两能级量子系统

原理：氢原子具有一个质子和一个环绕的电子，可以看作质子周围的一点“电流”，该电流使原子具有磁场，每个原子都有“磁偶极矩”，使得每个原子表现得像一块小的条形磁铁，其轴线对应于电子旋转的轴。把小磁铁扔过一个磁场会导致磁铁被磁场偏转，我们期望在实验中看到类似的原子偏转。

注：受当时技术水平限制，最初的实验是用Ag完成的实验，Ag具有复杂的结构，解释复杂效应的难度更大

内容：热原子从烤箱中“射出”，通过一个导致原子偏转的磁场，然后记录每个原子的位置。

原子如何偏转取决于原子的磁偶极矩（即电子旋转的轴）以及Stern-Gerlach装置产生的磁场。通过适当地构造Stern-Gerlach器件，我们可以使原子偏转一定量，而该量取决于原子磁偶极矩的$z$分量，其中$z$是一些固定的外轴

现象与解释：

离开炉子的热原子从一组离散的角度出现：磁偶极矩是量子化的
氢原子具有零磁矩，但观测到了两个光束，一个被磁场向上$(\ket{+Z})$偏转，另一个则向下$(\ket{-Z})$偏转：氢原子中的电子有一个叫做自旋的量，电子的自旋对氢原子的磁偶极矩产生额外的贡献

进一步实验以描述电子自旋：

将两个Stern-Gerlach设备级联在一起，将第二个设备侧向倾斜，使得磁场沿$\hat x$偏转原子；阻止第一台设备的$\ket{-Z}$输出，而将$\ket{+Z}$输出发送至沿着$\hat x$轴的第二设备，将检测器放置在最终处以测量沿$\hat x$轴的原子分布

现象与解释：

指向$+\hat z$方向的经典磁偶极子在$x$方向没有净磁矩，但实验上观察到两个强度相等的峰值：通过第二个设备的每个原子可以被描述成$\ket{+Z}\ket{+X}$或$\ket{+Z}\ket{-X}$，来指代可能被观测到的自旋的两个值

通过发送之前的输出使之通过第二个$\hat z$导向的Stern-Gerlach设备

现象与解释：

在最终输出处再次观察到两个强度相等的光束：一个$\ket{+Z}$态由相等比例的$\ket{+X}$和$\ket{-X}$态组成，一个$\ket{+X}$态由相等比例的$\ket{+Z}$和$\ket{-Z}$态组成

量子比特模型解释：

用$\ket0,\ket1$表示量子比特的状态，并分配$\ket{+Z}\leftarrow\ket0,\ket{-Z}\leftarrow\ket1,\ket{+X}\leftarrow(\ket0+\ket1)/\sqrt2,\ket{-X}\leftarrow(\ket0-\ket1)/\sqrt2$，假设$\hat z$Stern-Gerlach装置在计算基$\ket0,\ket1$下测量自旋（即量子比特），$\hat x$Stern-Gerlach实验装置在基$(\ket0+\ket1)/\sqrt2,(\ket0-\ket1)/\sqrt2$下测量自旋。

在级联$\hat z-\hat x-\hat z$实验中，从第一个实验射出的自旋处于状态$\ket{+Z}=\ket0=(\ket{+X}+\ket{-X})/\sqrt2$，那么第二个装置得到$\ket{+X}$的概率是$\dfrac{1}{2}$；相似地，第三个装置得到$\ket{+Z}$的概率是$\dfrac{1}{2}$.因此，量子比特模型正确预言了级联Stern-Gerlach实验的结果。

问题：没有证明量子比特是毫无疑问的理解电子自旋的正确方式（由于此类实验很多，现在相信量子比特是描述电子自旋的最好模型）

更进一步，我们相信量子比特模型以及它向更高维度的推广（量子力学）能够描述每个物理系统

实用量子信息处理的前景¶

问题：是否存在某种原理禁止我们进行一种或多种形式的量子信息处理？

噪声可能对有用的量子信息处理构成根本性障碍

量子纠错码理论：量子噪声需要解决，但不是根本性的原理问题

量子计算的阈值定理：如果量子计算机中的噪声水平可以降低到某个常数“阈值”以下，那么就可以使用量子纠错码来进一步地降低噪声，只需要很小的计算复杂性开销，基本上可以降低到任意小

量子力学可能是不正确的

应用：既然构建量子信息处理设备没有根本性的障碍，为什么我们要投入大量的时间和金钱这样做？

【小规模】量子态层析：确定系统的量子状态方法，通过重复制备同一个量子态，然后以不同的方式测量，以建立量子态的完整描述

量子过程层析成像：完全表征量子系统的动态学

小规模通信原语：分发少量需要高度安全的关键材料
【中等规模】量子系统模拟：确定材料的基本性质；实验室设计和测试新分子性质的工具（狭义第一性原理计算）
【大规模】大整数素因子分解，计算离散对数，量子搜索

实现：

光学技术（电磁辐射）
囚禁不同原子（离子阱，中性原子阱，电磁辐射）——精湛的状态制备和量子测量
核磁共振NMR——极好的动态演化

量子信息处理不仅仅是另一种信息处理技术：量子计算是信息处理的一个抽象范式，可能在技术上有许多不同的实现。人们可以比较量子计算的两个不同方案的技术优点，即使量子计算机的一个非常糟糕的方案，它与精湛设计的经典计算机也具有定性的本质不同

量子信息¶

内涵

广义：与使用量子力学的信息处理相关的所有操作
具体：对基本量子信息处理任务的研究（量子信息理论）

基本目标

确定量子力学中的基本静态资源类：例如量子比特、经典比特、贝尔态
确定量子力学中动力学过程的基本类：例如内存（在一段时间内存储量子态的能力）、量子信息传输、复制（或试图复制）量子态、保护量子信息处理免受噪声影响
量化执行基本动态过程所需的资源折衷

核心问题

是什么使量子信息处理成为可能？
是什么分离了量子世界与经典世界？
量子计算中正在利用哪些经典世界中无法获得的资源？

量子信息理论问题¶

使用量子信道传输经典信息¶

基本结果：香农无噪声信道编码定理，有噪声信道编码定理

信息源：由一组概率$p_j,j=1,2,\cdots,d$描述，信源每次随机地以概率$p_j$产生“字母”$j$，信源每次使用都相互独立

香农无噪声信道编码定理

香农熵：由概率$p_j$描述的经典信源可以被压缩，以使得平均每次使用信源可用$H(p_j)$位信息来表示，其中$H(p_j)=-\sum_jp_j\log(p_j)$是信源概率分布的函数，即香农熵（如果尝试比这更少的比特来对信源进行压缩时会导致在信息解压缩时出错的概率很高）
基本目标的实现：

目标	结果
目标1	确定了两个静态资源：比特和信息源
目标2	确定了两阶段动态过程：压缩信息源，解压缩以恢复信息源
目标3	找到最优数据压缩方案确定消耗资源的量化标准

香农有噪声信道编码定理

量化了可以通过有噪声信道可靠传输的信息量（空间/时间（存在噪声时信息的存储问题））
纠错码：在信道发送的信息中引入足够多的冗余，这样即使在某些信息被破坏之后，仍然可以恢复原始消息（提供了计算任意噪声信道容量的通用过程）
基本目标的实现：

目标	结果
目标1	确定了两个静态资源：比特和信息源
目标2	确定了三个动态过程：信道中的噪声，使用纠错码对状态执行编码和解码
目标3	对于固定噪声模型，香农定理告诉我们如果要实现可靠的信息传输，最佳纠错方案必须引入多少冗余

量子信息理论问题

问题1：使用量子态作为介质传输经典信息会发生什么？

结论：在无噪声信道中传输信息时，量子比特不会导致所需的通信量有任何显著的节省

问题2：通过带有噪声的量子信道传输经典信息会发生什么？

HSW定理：提供带有噪声的量子信道容量的下界

问题3：是否可以使用纠缠态编码来提高容量？

迄今为止的所有证据表明，使用纠缠态编码无助于提高容量。但证明或证否仍悬而未决

通过量子信道传输量子信息¶

量子信息源：由一组概率$p_j$和相应的量子态$\ket{\psi_j}$描述，信源的每次使用都有概率$p_j$产生状态$\ket{\psi_j}$，信源每次使用相互独立

压缩信源输出

经典数据压缩标准技术：考虑单比特量子信源，以概率$p$输出状态$\ket0$，以概率$1-p$输出状态$\ket1$，与发射单比特的经典源相同，使用与经典类似的技术来压缩信息源，只需要$H(p,1-p)$量子比特来存储压缩信息；若信源以概率$p$输出状态$\ket0$，以概率$1-p$输出状态$(\ket0+\ket1)/\sqrt2$将不再适用，由于一般来说无法区分状态$\ket0,(\ket0+\ket1)/\sqrt2$
Schumacher无噪声信道编码定理：
保真度：信源产生的量子态可能会因为压缩——解压缩过程略微失真，为了量化失真，为压缩方案引入保真度，度量由压缩方案引入的平均失真
Schumacher无噪声信道编码定理量化了在接近1的保真度恢复信息源的限制下，进行量子数据压缩所需的资源

信源产生正交量子态：定理退化为信源可以被压缩但不超过经典极限$H(p_j)$

信源产生非正交量子态：量子信源可以被压缩到冯·诺依曼熵，当且仅当状态$\ket{\psi_j}$彼此正交时，冯·诺依曼熵与香农熵一致；否则信源$(p_j,\ket{\psi_j})$的冯·诺依曼熵通常严格小于香农熵$H(p_j)$
实例：对以概率$p$输出状态$\ket0$，以概率$1-p$输出状态$(\ket0+\ket1)/\sqrt2$的信源进行压缩

信源使用$n$次（$n$为很大的数），由大数定理，信源以高概率发送$np$份$\ket0$和$n(1-p)$份$(\ket0+\ket1)/\sqrt2$，在重新将系统排序的意义下，有 $$ \ket0^{\otimes np}\left(\dfrac{\ket0+\ket1}{\sqrt2}\right)^{\otimes n(1-p)} $$ 假设将右侧的$\ket0+\ket1$展开，由于$n(1-p)$很大，由大数定理推断乘积项中大约一半是0，一半是1，可以用如下形式的状态的叠加来近似： $$ \ket0^{\otimes n(1-p)/2}\ket1^{\otimes n(1-p)/2} $$ 因此信源发送的态可由以下形式的叠加态来估计 $$ \ket0^{\otimes n(1+p)/2}\ket1^{\otimes n(1-p)/2} (*) $$ 这种形式的态一共有$C_n^{n(1+p)/2}$，由斯特林公式近似为$N\equiv C_n^{n(1+p)/2}=2^{nH[(1+p)/2,(1-p)/2]}$

压缩方法：将$(*)$的所有态标记为$\ket{c_1}\sim\ket{c_N}$

压缩：$\forall 1\leqslant j\leqslant N$，$j$表示$nH[(1+p)/2,(1-p)/2]$位二进制数。在信源发出的$n$量子比特上执行酉变换$U:\ket{c_j}\mapsto\ket j\ket0^{n-nH[(1+p)/2,(1-p)/2]}$，然后将最后$n-nH[(1+p)/2,(1-p)/2]$个量子比特丢弃，剩下$nH[(1+p)/2,(1-p)/2]$量子比特的压缩态$\ket j$

解压缩：在压缩态的末尾添上$\ket0^{n-nH[(1+p)/2,(1-p)/2]}$，然后执行$U^{-1}$
理解：利用状态不正交的事实，导致它们比正交状态有更多的物理相似性，利用冗余可以实现数据压缩

量子可区分性¶

量子力学并不总是可以区分任何状态：例如，量子力学不允许任何过程可靠地区分状态$\ket0,(\ket0+\ket1)/\sqrt2$.假设试图通过计算基上测量来区分时，虽然测量结果为1意味着状态必须是$(\ket0+\ket1)/\sqrt2$，但我们无法从测量结果为0推断出有关量子态身份的任何信息

非正交量子态的不可区分性：量子态包含无法通过测量获得的隐藏信息（量子信息理论的核心之一是发展度量来量化非正交量子态的可区分度）

若我们可以区分任意量子态，则使用纠缠能够比光速更快地进行通信（Bob能判断出与之共享量子比特的Alice在哪组基下进行了测量）
量子货币（在钞票中嵌入量子序列，由于伪造者无法确定的得到其中的量子比特状态而不破坏它们；通过在$(\ket0,\ket1)$或$(\ket+,\ket-)$上测量来验证真伪）

简介与概述¶

历史背景¶

物理学¶

计算机科学¶

信息论¶

密码学¶

量子计算和量子信息¶

未来方向¶

基本概念¶

量子比特¶

多量子比特¶

量子计算¶

单量子比特门¶

多量子比特门¶

除计算基外的测量¶

量子电路¶

元件与约定¶

实例¶

量子态交换¶

量子比特复制电路（不可复制）¶

贝尔态制备¶

量子隐形传态¶

量子算法¶

经典计算¶

量子并行性¶

Deutsch算法¶

Deutsch-Jozsa算法¶

量子算法总结¶

基于傅里叶变换的量子算法¶

量子搜索算法¶

量子模拟¶

量子计算的能力¶

实验量子信息处理¶

Stern-Gerlach实验¶

实用量子信息处理的前景¶

量子信息¶

量子信息理论问题¶

使用量子信道传输经典信息¶

通过量子信道传输量子信息¶

量子可区分性¶

纠缠的产生与转化¶