量子计算笔记(编码)

2016-01-08

经典编码理论

一个线性编码C是将k比特信息加密到n比特的编码空间,记作\(n\times k\)生成元G,叫做[n,k]码,码字由\(G\cdot x\)生成

另外一种定义线性编码的方法是通过奇偶检验矩阵 \[ Hx = 0 \] 这里H是一个\((n-k)\times n\)的奇偶检验矩阵,x是一个n元的向量,码字就是矩阵H的核

H和G的关系

  • \(H\rightarrow G\) 选取kernel中k个线性独立向量构成G的列
  • \(G\rightarrow G\) 选取n-k个线性独立的向量\(y\_1,y\_2,\dots,y\_{n-k}\)与G的每一列正交,H的行就是\(y\_1^T,y\_2^T,\dots,y\_{n-k}^T\)

error syndrome 如果y是x的码字,存在一个错误e使得\(y'=y+e\),那么error syndrome就是\(Hy'=He\),不同的错误\(e\_j\)有不同的\(He\_j\)

Hamming距离 两个码字x和y之间bit不同的数量称为Hamming距离,记作\(d(x,y)\)

Hamming权 x的Hamming权是到0的距离,也就是x中1的个数

编码的距离 是指 \[ \begin{align} d(C)&\equiv \min\_{x,y\in C,x\neq y}{d(x,y)}= \min\_{x\in C,x\neq 0}{wt(x)} \end{align} \]

如果一个编码满足\(d(C)\geq 2t+1\),那么它就能够对t个bit进行纠错,所以不能使用的编码\(y'\)就满足\(d(y,y')\leq t\)

CSS码

\(C\_1\)\(C\_2\)是[\(n,k\_1\)]和[\(n,k\_2\)]的线性编码,并且有\(C\_2\in C\_1\),并且\(C\_1,C\_2\)都能够改正t bit错误。我们定义[\(n,k\_1-k\_2\)]的量子编码,能够改正t bit错误。假设\(x\in C\_1\)是一个\(C\_1\)的码字,那么量子态\(|x+C\_2\rangle\)可以定义为

\[ |x+C\_2\rangle \equiv \frac{1}{|C\_2|}\sum\_{y\in C\_2}|x+y\rangle \]

  • 当有\(x'-x\in C\_2\)就有\(\|x+C\_2\rangle = |x'+C\_2\rangle\),所以它是\(C\_1/C\_2\)的陪集
  • 对于\(C\_2\)两个不同的陪集,所对应的态\(|x+C\_2\rangle\)\(|x'+C\_2\rangle\)是正交的
  • CSS码的维数是\(|C\_1|/|C\_2|=2^{k\_1-k\_2}\),所以CSS码是一个\([n,k\_1-k\_2]\)的量子编码

CSS码能够纠正t比特的相位翻转和比特翻转错误。假设发生了一比特翻转错误记为\(e\_1\),比特翻转发生在\(e\_1\)的第一个,相位翻转发生在\(e\_2\)的第一个

\[ \frac{1}{\sqrt{|C\_2|}}\sum\_{y\in C\_2} (-1)^{(x+y)\cdot e\_2} |x+y+e\_1\rangle \]

为了纠正并且发现比特翻转错误 - 引入一个初始化为0的ancilla态,并保证有足够的位数来存储\(C\_1\)编码的syndrome - 通过可逆计算来将\(C\_1\)的奇偶检验矩阵\(H\_1\)作用在引入的态上 \[ |x+y+e\_1\rangle|0\rangle \rightarrow |x+y+e\_1\rangle |H\_1(x+y+e\_1)\rangle = |x+y+e\_1\rangle |H\_1(e\_1)\rangle \]

就得到了态 \[ \frac{1}{\sqrt{C\_2}}sum\_{y\in C\_2} (-1)^{(x+y)\cdot e\_2}|x+y+e\_1\rangle |H\_1(e\_1)\rangle \]

  • 测量这个ancilla态就获得了\(He\_1\)然后丢弃ancilla态,得到 \[ \frac{1}{\sqrt{C\_2}}\sum\_{y\in C\_2} (-1)^{(x+y)\cdot e\_2}|x+y+e\_1\rangle \]

  • 由于\(C\_1\)能够纠正t个错误,所以可以通过\(He\_1\)推测出错误\(e\_1\)
  • 对出现\(e\_1\)错误的qubit做非门,就有 \[ \frac{1}{\sqrt{|C\_2|}} \sum\_{y\in C\_2} (-1)^{(x+y)\cdot e\_2}|x+y\rangle \]

  • 为了找到并纠正相位翻转错误
  • 对每一个bit使用Hadamard门,就有 \[ \frac{1}{\sqrt{|C\_2|}2^n}\sum\_z \sum\_{y\in C\_2} (-1)^{(x+y)\cdot (e\_2+z)}|z\rangle\\ = \frac{1}{\sqrt{|C\_2|w^n}}\sum\_{z'}\sum\_{y\in C\_2}(-1)^{(x+y)\cdot z'}|z'+e\_2\rangle,\quad z'\equiv z+e\_2 \]
  • 假设\(z'\in C\_2^{\perp}\),那么这个态就可以被写成 \[ \frac{1}{\sqrt{|C\_2|2^n}} \sum\_{z'\in C\_2^{\perp}} (-1)^{x\cdot z'}|z'+e\_2\rangle \]