量子计算基础（二）

1. 量子测量 - 测量公设的量子信息学描述

---

       对于一个由状态 $|\psi ⟩$ 描述的量子系统，可以由一组测量算符 {Mm}\{M_m\}{Mm​} 描述，这些算符作用在被测量系统的态空间上，可能的测量结果 $m$ 发生的概率为：
$$p(m)=⟨\psi |M_m^H{M}_m|\psi ⟩$$

测量后系统的状态为：
$$\frac{M_m|\psi ⟩}{\sqrt{⟨\psi |M_m^H{M}_m|\psi ⟩}}$$

测量算子需要满足完备性方程
$$\sum _m{M}_m^H{M}_m=I$$

完备性方程描述了概率之和为 1 的事实，即
$$\sum _{m}p(m)=\sum _m⟨\psi |M_m^H{M}_m|\psi ⟩$$

例：用 {∣0⟩,∣1⟩}\{|0\rangle,|1\rangle\}{∣0⟩,∣1⟩} 测量量子态 $|\phi ⟩=\alpha |0⟩+\beta |1⟩$
解：$M_0=|0⟩⟨0|=\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right],M_1=|1⟩⟨1|=\left[\begin{array}{cc}0& 0\\ 0& 1\end{array}\right]$ ，显然 $M_0^2=M_0,M_1^2=M_1,I=M_0^H{M}_0+M_1^H{M}_1=M_0+M_1$，因此，对于$|\phi ⟩=\alpha |0⟩+\beta |1⟩$，有
$$p(0)=⟨\psi |M_0^H{M}_0|\psi ⟩=⟨\psi |M_0|\psi ⟩=|\alpha {|}^2$$

$$p(1)=⟨\psi |M_1^H{M}_1|\psi ⟩=⟨\psi |M_1|\psi ⟩=|\beta {|}^2$$

所以，将以概率 $|\alpha {|}^2$ 测得 $|0⟩$ ，以概率 $|\beta {|}^2$ 测得 $|1⟩$ 。

测量公设的进一步认识：

1. 测量共设是一个基本假设。测量系统和被测系统可以看做一个更大的封闭的量子系统的组成部分。而孤立的量子系统可以用幺正变换描述其演化过程。

2. 测量公设的重要作用——区分量子态

   1. 若一组态矢 $|{\Psi }_i⟩$ 是正交的，测量者可以 通过为每个态矢定义测量算子 $M_i=|{\Psi }_i⟩⟨{\Psi }_i|$ ，从而可以确定性的确定测得每个状态的概率 $p(i)=⟨{\psi }_i|M_i|{\psi }_i⟩=1$ 。
   2. 若一组态矢 $|{\Psi }_i⟩$ 不是正交的，则可以证明没有量子测量可以精确的区分这些状态。因为非正交态的量子态 ${\Psi }_1$ 和 ${\Psi }_2$ ，$|{\Psi }_2⟩$ 总可以分解成一个平行于 $|{\Psi }_1⟩$ 的分量和一个与 $|{\Psi }_1⟩$ 正交的分量，这是导致两个分量不能被严格区分的核心原因。

• 测量是量子信息中提取信息的重要手段。
• 与经典环境中测量物体的位置、速度等类似，对量子系统的观测实际也是对某个力学量的测量。

2. 密度算符（密度矩阵）

---

       密度算符是对量子的状态的一种不同的描述方法。前面我们一直了解到的是用状态向量表示一个量子系统的状态，我们也可以用密度算符对量子系统的状态进行描述。密度算符在描述 未知量子系统 和 复合系统子系统 方面更加有优越性。

       系综：设量子系统以概率 $p_i$ 处于状态 ${\varphi }_i$ ，称 {pi,∣ϕi⟩}\{p_i,|\phi_i\rangle\}{pi​,∣ϕi​⟩} 为一个系综，其中 $p_i\ge 0$ ，且 ${\sum }_i{p}_i=1$ ，系统的 密度算子 为：
$$\rho =\sum _i{p}_i|{\varphi }_i⟩⟨{\varphi }_i|$$

它是一个迹为 1 的半正定厄米算子。观察可以发现，这是外积和概率乘积的累加和，因此密度算子为一个矩阵。

       纯态 ：在密度算子的定义中若系统以概率 1 处于某个态 $|\varphi ⟩$ ，即系统的状态可以由一个态矢表示，则该系统是一个纯态。其密度算子为 $|\varphi ⟩⟨\varphi |$。

       混合态：若量子系统整体的状态不能用一个单独的态矢表示，它整体的状态可能是若干个状态中的一个，系统成为以不同的概率成为不同的态，即系统只能由若干不同的态矢描述，整个系统以概率 $p_i$ 为 $|{\varphi }_i⟩$ ($i\ge 1$)，这样的系统称为混合态。

纯态与混合态的区别：纯态和混合态的最大区别是 $tr({\rho }_{{}_{纯}}^2)=1$ ，而 $tr({\rho }_{{}_{混}}^2)<1$ 。

考察一个力学量 $F$ 在纯态与混合态上的区别，假设算符 $\hat{F}$满足：
$$\hat{F}|{\varphi }_i⟩=f_i|{\varphi }_i⟩$$

1. 对于纯态 $|\Psi ⟩=c_1|{\Psi }_1⟩+c_2|{\Psi }_2⟩$，取 $f_i$ 的概率为
   $$p(f_i)=|⟨{\phi }_i|\Psi ⟩{|}^2=|c_1⟨{\phi }_i|{\Psi }_1⟩+c_2⟨{\phi }_i|{\Psi }_2⟩{|}^2$$
2. 对于混合态， 取 $f_i$ 的概率为
   $$p(f_i)=|⟨{\phi }_i|{\Psi }_1⟩{|}^2{p}_1+⟨{\phi }_i|{\Psi }_2⟩p_2{|}^2{p}_2$$

具体到坐标表象：

1. 在纯态上 $\Psi (x)=c_1{\Psi }_1(x)+c_2{\Psi }_2(x)$
   坐标取 $x_0$ 的概率密度为
   $$p(x_0)=|\Psi (x_0){|}^2=|c_1{\Psi }_1(x_0)+c_2{\Psi }_2(x_0){|}^2$$
2. 在混合态上
   $$p(x_0)=|{\Psi }_1(x_0){|}^2{p}_1+|{\Psi }_2(x_0){|}^2{p}_2$$

       可以看出，在纯态下，两个态之间发生干涉，而在混合态下，无干涉现象发生。纯态为 概率幅的叠加，称为 相干叠加 ，叠加的结果形成一个新的状态，混合态为 概率的叠加，称为 不相干叠加。

密度算符的性质

1. 对于密度算符 $\rho$ ，有
   $$tr({\rho }^2)\{\begin{array}{llc}=1& ⟶& 纯态\\ <1& ⟶& 混合态\end{array}$$

2. 密度算符是 厄米算符
   $${\rho }^H=(\sum _i{p}_i|{\varphi }_i⟩⟨{\varphi }_i|{)}^H=\sum _i{p}_i|{\varphi }_i⟩⟨{\varphi }_i|=\rho$$

          若混合态是由一系列相互正交的态构成的，则密度算符的本征态就是参与混合态的这些态 $|{\varphi }_i⟩$，而每个本征态对应的本征值就是每个态出现的概率 $p_i$ ，即
   $$\rho |{\varphi }_i⟩=p_i|{\varphi }_i⟩$$

3. 密度算符是 半正定 的
   $$\begin{array}{rl}⟨\varphi |\rho |\varphi ⟩& =⟨\varphi |(\sum _i{p}_i|{\varphi }_i⟩⟨{\varphi }_i|)|\varphi ⟩\\ & =\sum _i{p}_i⟨\varphi |{\varphi }_i⟩⟨{\varphi }_i|\varphi ⟩\\ & =\sum _i{p}_i|⟨\varphi |{\varphi }_i⟩{|}^2\ge 0\end{array}$$

4. 密度算符可以进行谱分解

约化密度算子

       对于一个有若干子系统组成的大的量子体系，如果我们只对其中的子系统感兴趣，那么我们可以使用 约化密度算子 对复合量子系统进行分析。

约化密度算子：假设有物理系统 $A$ 和 $B$ ，其整体状态由密度算子 ${\rho }^{AB}$ 描述，那么，针对系统 $A$ 和 $B$ 的约化密度算子分别定义为：

目的	定义	含义
得到系统A状态	${\rho }^A=t{r}_{{}_B}({\rho }^{AB})$	对B系统进行约化
得到系统B状态	${\rho }^B=t{r}_{{}_A}({\rho }^{AB})$	对A系统进行约化

$t{r}_B$ 是一个算子映射，称为在系统 $B$ 上的 偏迹 ，偏迹就是将该系统的分量求内积，变换为一个数，而对其他系统的分量不做变换，即 对谁求偏迹，将谁求内积，其定义为：
$$t{r}_{{}_A}(|a_1⟩⟨a_2|\otimes |b_1⟩⟨b_2|)=|b_1⟩⟨b_2|t{r}_{{}_A}(|a_1⟩⟨a_2|)=|b_1⟩⟨b_2|⟨a_2|a_1⟩$$

$$t{r}_{{}_B}(|a_1⟩⟨a_2|\otimes |b_1⟩⟨b_2|)=|a_1⟩⟨a_2|t{r}_{{}_B}(|b_1⟩⟨b_2|)=|a_1⟩⟨a_2|⟨b_2|b_1⟩$$

       一般来说，复合得到的整体的系统处于纯态，其子系统也有可能为混合态。如 Bell 态是一个两比特系统的纯态
$$|{\Psi }^{+}⟩=\frac{1}{\sqrt{2}}(|0^{(1)}⟩|1^{(2)}⟩+|1^{(0)}⟩|0^{(2)}⟩)$$

因为它就表示该系统的状态，所以其密度算子为
$$\begin{array}{rl}\rho =|{\Psi }^{+}⟩⟨{\Psi }^{+}|& =\frac{1}{2}(|0^{(1)}⟩|1^{(2)}⟩⟨1^{(2)}|⟨0^{(1)}|+|0^{(1)}⟩|1^{(2)}⟩⟨0^{(2)}|⟨1^{(1)}|\\ & +|1^{(1)}⟩|0^{(2)}⟩⟨1^{(2)}|⟨0^{(1)}|+|1^{(1)}⟩|0^{(2)}⟩⟨0^{(2)}|⟨1^{(1)}|)\end{array}$$

对第一个量子比特的约化密度算子就是对第二个量子比特求偏迹，将第二个量子比特约化：
$$\begin{array}{rlr}{\rho }^{(1)}& =t{r}_{(2)}\rho & \\ & =t{r}_{(2)}\frac{1}{2}(|0^{(1)}⟩|1^{(2)}⟩⟨1^{(2)}|⟨0^{(1)}|+|0^{(1)}⟩|1^{(2)}⟩⟨0^{(2)}|⟨1^{(1)}|& \\ & +|1^{(1)}⟩|0^{(2)}⟩⟨1^{(2)}|⟨0^{(2)}|+|1^{(1)}⟩|0^{(2)}⟩⟨0^{(2)}|⟨1^{(1)}|)& \\ & =\frac{1}{2}(|0^{(1)}⟩⟨0^{(1)}|⟨1^{(2)}|1^{(2)}⟩+|0^{(1)}⟩⟨1^{(1)}|⟨0^{(2)}|1^{(2)}⟩& \\ & +|1^{(1)}⟩⟨0^{(1)}|⟨1^{(2)}|0^{(2)}|⟩+|1^{(1)}⟩⟨1^{(1)}|⟨0^{(2)}|0^{(2)}⟩)& \\ & =\frac{1}{2}(|0^{(1)}⟨0^{(1)}|+|1^{(1)}⟩⟨1^{(1)}|)& \end{array}$$

可以算出，该密度算子的平方的迹小于 1 ，且它表示的状态不能用一个态矢表示，是一个混合态。

3. 常用的量子算法

---

        这里简单介绍几个典型的量子算法和基本的原理。

Shor 算法

• RSA公钥密码体系
         现有最普遍的加密算法是 RSA 公钥密码体系，其基本原理就是用两个大素数的合数进行加密，想要解密必须求出该合数对应的两个素数，在现有计算中的能力下，对于过大合数是无法在短时间内求出对应的两个素数的。Shor 设计了一种算法可以在极短的时间内利用量子计算机解决这个求素数的问题，这里我们先来了解一下 RSA 密码体系的基本原理。

  1. 首先找到两个两个大素数 $p$ 和 $q$ ，并计算 $n=p\times q，\phi (n)=(p-1)(q-1)$。
  2. 然后随机选择一个小于 $\phi (n)$ 但与 $\phi (n)$ 互素的整数 $e$，即 $e$ 满足条件 $gcd(\phi (n),e)=1$ 。
  3. 计算 $d$ 使其满足 $ed=1\mathrm{m}\mathrm{o}\mathrm{d}\phi (n)$
  4. 宣布公钥 $(e,n)$ ，自己保存私钥 $(p,q,d)$
  5. 需要和自己通信的人用加密密钥 $e$ 将明文 $m$ 加密，即 $y=m^e\mathrm{m}\mathrm{o}\mathrm{d}n$。
  6. 当接收方收到密文后用解密密钥 $d$ 对 $y$ 进行解密，求出 $m$ 。
     $$y^d=m^{ed}\mathrm{m}\mathrm{o}\mathrm{d}m=m$$

• Shor算法的描述

         Shor算法最关键之处是利用量子傅立叶变换求函数的周期，所以只要求得函数的周期，就可以对合数进行分解。 其主要步骤为：

  1. 设 $N$ 为要分解的大整数, 选择 $m$ 使之满足 $N^2<2^m<2N^2$.

  2. 随机选一正整数 $a$ ，使得 $a<N$，且 $a$ 与 $N$ 互质，即 $gcd(a,N)=1$。

  3. 定义 $f(x)=a^x\mathrm{m}\mathrm{o}\mathrm{d}N，x=1,2,3,\cdots ,n$ ，显然 $f(x)$ 所取的值属于正整数集合 {1,2…,N－1}\{1,2…,N－1\}{1,2…,N－1} ，它是一个周期函数。

  4. 我们通过量子傅里叶变换 QFT 来求取 $f(x)$ 的周期 T ，基本步骤为：
            首先，对两组有m个量子比特的存储器进行幺正变换得到纠缠状态
     $$\sum _{r=0}^{2^m-1}|x_i⟩\otimes |f(x_i)⟩$$

            对存储器 $x$ 进行傅里叶变换：
     $$|x⟩=2^{-m/2}\sum _{k=0}^{2^m-1}{e}^{\frac{2\pi ikx}{2^m}}|k⟩$$

            量子QFT就是将态前面的叠加系数变为原叠加系数的离散傅立叶变换，并且可以证明, 上述变换大约可以在 $m^2$ 步骤内完成。通过合并相消，最后可以得出只有 $k$ 取下列值时系数明显不为 0 ：
     $$k=\left[n\frac{2^m}{T}\right]，（n=0,1,\cdots ,T-1）$$

            化简可得：
     $$\frac{2^m}{k}=\frac{T}{n}，（n=0,1,\cdots ,T-1）$$

            之后可以通过对 $k$ 存储器进行测量，得到 $k$ 的本征值，得到本征值后就可以通过上式算出周期 $T$ 。

  5. 之后利用 $gcd(a^{\frac{T}{2}}-1,N)$ 和 $gcd(a^{\frac{T}{2}}+1,N)$ 求出两个质因数 $n_1,n_2$ 。

Grover 量子搜索算法

       该算法指的是从 n 个未分类的元质中寻找出某个特定的元质。其 基本原理 为：

       假设在 N 个元质的空间中搜索，为方便起见，假定 N=2n，且搜索问题恰好有 M 个解，这个问题的特例可以方便地表示为一个输入 $x$ 的函数 $f(x)$，$x$ 是从 $0$ 到 $N－1$ 的整数，$f$ 的定义是：

       若 $x$ 是搜索问题的一个解，则 $f(x)=1$， 而若 $x$ 不是解， 则 $f(x)=0$。
       搜索问题都可归结为在判决函数：
$$f:\Omega \to 0,1$$

对每个输入都可计算出来的条件下，从 $N$ 元的可能解集合 $\Omega$ 中找出一个满足
$$f(x)＝1$$

的点 $x$ 的问题。函数 $f$ 称为一个 Oracle(黑匣子、数据库、神谕、预言)。

其 过程 为：

1. 初始化：产生一个等幅度的状态叠合：
   $$|0^n,0⟩\stackrel{对前n个分量并行执行量子傅里叶变换}{\to }\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x,0⟩$$

2. 完成对判决函数的并行计算
   $$\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x,0⟩\underset{将第一分量的变换结果\oplus 到第二分量}{\overset{F:|x,b⟩\to |x,b\oplus f(x)⟩}{\to }}\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x,f(x)⟩$$

3. 对最后分量做 Z 操作 变换, 标出真解
   $$\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}|x,f(x)⟩\stackrel{对第二分量做“Z操作”变换}{\to }\frac{1}{\sqrt{2^n}}\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}|x,f(x)⟩$$

   该步达到的效果是只有真解的幅度才是负值。

4. 对 $|x,f(x)⟩$的第一分量执行 D 变换——增大真解 $b$ 对应的状态 $|b,1⟩$的出现概率。其中 D 变换的变换矩阵 $D=(d_{ij}{)}_{2^n\otimes 2^n}$，其中
   $$d_{ij}=\{\begin{array}{llc}& 2^{1-n}-1& ,i\ne j\\ & 2^{1-n}& ,i=j\end{array}$$

   即幅度的变化规律 $(a_0,a_1,\cdots ,a_{2^n-1})\to (a_0^{{}^{\prime }},a_1^{{}^{\prime }},,\cdots ,a_{2^n-1}^{{}^{\prime }})$ ($a_i$ 是 $|i⟩$ 的幅度) 为：
   $$a_i^{{}^{\prime }}=\sum _{j=0}^{2^n-1}{d}_{ij}{a}_j=d_{ii}{a}_i=(2^{1-n}-1)a_i+2^{1-n}\sum _{j:j\ne i}{a}_j=2^{1-n}\sum _{j=0}^{2^n-1}{a}_j-a_i$$

   该步是为了使达到的效果是真解的出现概率变大。

5. 重复执行第三步至第四步 k 次后进行观察, 得到观察结果 | x,1并将 x 作为真解输出。

注意：

• 迭代的次数 $k$ 的值必须预先设定：
  $$k\approx \frac{\pi }{4}\sqrt{\frac{2^n}{M}}-\frac{1}{2}$$

• 整个算法只计算 $f(x)$ 一次。