Posted at

量子誤り訂正の初歩 with python


量子誤り訂正の初歩 with python

$$

\def\bra#1{\mathinner{\left\langle{#1}\right|}}

\def\ket#1{\mathinner{\left|{#1}\right\rangle}}

\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}\\

$$


1.はじめに


1.0その他リンク

量子計算とpython$\to$「量子コンピュータと量子計算まとめ」


1.1この記事の目的

量子誤り訂正とは何かをpythonを通じて知る。


1.2前書き

量子計算の基礎の記事では、入門と言うことで数学的に基礎を扱ったあと、量子コンピュータをqiskitで実際動かして見ました。今回は、qiskitからは離れて量子誤り訂正の原理と典型的な符号について取り扱って行きます。


1.3お願い

まだ勉強して日が浅いので、色々間違っているかもしれませんがどうか寛大な心で見守ってください...


1.4前提とする知識

線形代数学を中心とした大学初年度程度の知識

量子コンピュータに関する初歩的な知識


2.量子誤り訂正の背景:量子ビットへの誤りは避けられない。

量子ビットは、時間がたつに連れて、以下のシュレーディンガー方程式にしたがって状態が変化してしまいます。

$$i\frac{d}{dt}\ket{x_t}=H\ket{x_t}$$

ここで$H$は量子系のエネルギーに相当する量であるハミルトニアンを表している。ここで、tはある時間を表します。

この式をとくと、初期状態$\ket{x_0}$に対して、$\ket{x_t}$は以下で表されます。

$$\ket{x_t}=U_t\ket{x_0}$$

ここで、$U_t$は時刻$t$に依存するユニタリ演算子で

$$U_t=exp(-iHt):=I+(iHt)+\frac{(-iHt)^2}{2}+\frac{(-iHt)^3}{6}+\cdots+\frac{(-iHt)^n}{n!}$$

である。したがって時間がたつと、系のエネルギー$H$に応じて、あるユニタリ演算子$U_t$が作用される。

エネルギーが$H=O$なら、$U_t=I$となるので誤りは発生しないけども、系のエネルギーが0になることは(多分)ない(詳しくないので鵜呑みにしないでください)。

仮に$H\neq O$ならば、時間が経つに連れて原理的に誤りを避けることはできない。


3.量子誤り訂正符号

誤り訂正符号にはいくつか方式があるようですが、典型的な量子誤り訂正符号の一つであるスタビライザ符号について今回は取り扱います。


3.1 量子誤り訂正符号とは

量子ビットに冗長な情報(量子ビット、変換)を付け加えて数学的構造を持たせ、誤りが発生しても訂正できるような仕組みを備えた量子ビット列のこと。

例えば、情報$\alpha\ket{0}+\beta\ket{1}$を

$$\alpha\ket{0}+\beta\ket{1}\to \alpha\ket{000}+\beta\ket{111}$$

のように符号化すると、ある誤りに対して幾分か耐性をもつようになる。しかしながら、耐性を持たせたのと引き換えに、本当に伝えたい情報以上の量子ビットを送る必要がある。


3.2 スタビライザー符号

一般に、スタビライザー符号は以下の数式で定まります。$S$は固定部分群と呼ばれる任意の要素が全て可換な部分群です。

$$C(S)=\{\ket{\psi}|g\ket{\psi}=\ket{\psi},\forall g\in S\}$$

$$S\subset \{I,X,Y,Z\}^{\otimes n}$$

式が難しいですが、$S$によって定まる部分ベクトル空間が$C(S)$だと思ってもらえれば結構です。


3.3 符号化から復号化までの流れ

$n$量子ビット系を用意し、そのうち情報には$k$量子ビット系を用いるとします。

初期状態として

$$\ket{\phi}\otimes \overbrace{\ket{0\cdots 0}}^{n-k}$$

を用意します。次に符号器である「あるユニタリ演算子」

$$U_{en}:(\mathbb{C}^2)^{\otimes k}\otimes \ket{0\cdots 0}\to C(S)\subset (\mathbb{C}^2)^{\otimes n}$$

によって、符号化し

$$\ket{\psi}\in C(S)$$

を得ます。その後、通信路を通り、誤りであるユニタリ演算子$E$が発生し受信語

$$E\ket{\psi}$$

を得ます。その後、復号を行い、推定符号語$\ket{\hat{\psi}}$を得ます。


3.4 符号語のまま計算できる。

符号器もまたユニタリ演算子$U_{en}$で行いましたから、元の情報$\ket{\phi}$に対して演算$V$

を行いたいときは、

符号語に対して、$$U_{en}(V\otimes \overbrace{I\otimes \cdots\otimes I}^{n-k})U^{\dagger}_{en}$$

というユニタリ演算子を作用させれば、行うことができるので、符号語のまま計算することができます(実際は後述する論理演算子がこちらに相当する)。


3.5 復号のシチュエーション

復号では、様々なシチュエーションが考えられますが、ここでは典型的なものとして、まず「通信路に発生する誤りの分布は知らない」場合について考えます。次に「通信路に発生する誤りの分布を知っている」場合について考えます。

「通信路に発生する誤りの分布を知っている」の具体例は量子コンピュータでどのような誤りがどんだけ発生しているかわかる場合です。確かIBM-Qも分布がわかっていたような。


3.6 復号(「通信路に発生する誤りの分布は知らない」)

ここでは復号のための数学的知識を書いていきます。

固定部分群$S$の任意の要素が$S_1,...,S_{n-k}$の積で書けるとき$S_1,...,S_{n-k}$を$S$の生成元と呼びます。シンドローム$\beta$を受信語$E\ket{\psi}$に対する$S_1,...,S_{n-k}$による測定によって得られる測定値とします。測定値は固有値で与えられることと、実は$S_i$の固有値は全て$1$か$-1$なので、測定値$\beta$は

$$\beta\in \{1,-1\}^{n-k}$$

です。この測定時に誤り$E$は、測定操作によって$\{I,X,Y,Z\}^{\otimes n}$のどれかの誤りに収縮します。

したがって、$E\in \{I,X,Y,Z\}^{\otimes n}$とみなしても問題ありません。

シンドロームは$E$に対して変化します。つまり$E$に対応して$\beta$が定まります。シンドローム測定を

$$\mathcal{M}(E):\{I,X,Y,Z\}^{\otimes n} \to \{1,-1\}^{n-k}$$

です。ここで、$\mathcal{M}(E)$は全単射ではありません。つまり、ある誤り$E,E'\in \{I,X,Y,Z\}^{\otimes n}$に対して

$$\beta=\mathcal{M}(E)=\mathcal{M}(E')$$

となることがあります。しかしこのようなエラー$E,E'$は実は問題ではなく、符号語に$E'$が発生して受信語が$E'\ket{\psi}$でも同じシンドロームを得られる$E$を作用させれば復号できることが知られています。実際

$$\beta=\mathcal{M}(E)=\mathcal{M}(E')\iff EE'\in S\iff EE'\ket{\psi}=\ket{\psi}$$

であるからです。したがって、受信者は、$\beta=\mathcal{M}(E)$となるような誤り$E$をあらかじめ把握しておけば$\beta$が得られたら$E$をかければ、$E'$だろうが復号することができます。


3.7 復号(「通信路に発生する誤りの分布を知っている」)

3.6で述べた、ある$\beta$に対して

$$\beta=\mathcal{M}(E)$$を満たすような誤り$E$を今後

$$T(\beta)=E$$

とします。このとき、誤り$E$は正規化群

$$N(S)=\{n\in G_n|ng=gn,\forall g\in S\}$$

$$G_n:=\{I,X,Y,Z\}^{\otimes n}$$

このとき、誤り$E$は以下のように分解できます。ここで$L\in N(S)$であり

$$E=LT(\beta)S$$

したがって、

$$T(\beta)LE\in S$$

と書けるので、

$$T(\beta)LE\in S\iff \ket{\psi}=T(\beta)LE\ket{\psi}$$

となります。$T(\beta)$は$\beta$から求まるので、決定的です。したがって、わからないのは$L\in N(S)$

$\beta$が得られた元での論理演算子$L$の確率分布$P(L|\beta)$は、

$$P(L|\beta)=\sum_{S}P(E=LT(\beta)S)$$

である。ここで推定論理演算子$\hat{L}$を

$$\hat{L}={\rm argmax}_{L}P(L|\beta)$$

とする。このような復号法は最尤復号と呼ばれている。


4.最尤復号によってSTEANE符号を復号してみる。


4.1実装のための準備

STEANE符号は1量子ビットを7量子ビットに符号化するスタビライザー符号です。固定部分群Sの生成元は以下で与えられます。

$$\begin{array}{c}S_1:I\otimes I \otimes I \otimes X \otimes X \otimes X\otimes X\\

S_2:I\otimes X \otimes X \otimes I \otimes I \otimes X\otimes X\\

S_3:X\otimes I \otimes X\otimes I \otimes X \otimes I\otimes X\\

S_4:I\otimes I \otimes I \otimes Z \otimes Z \otimes Z\otimes Z\\

S_5:I\otimes Z \otimes Z \otimes I \otimes I \otimes Z\otimes Z\\

S_6:Z\otimes I \otimes Z \otimes I \otimes Z \otimes I\otimes Z\\

\end{array}$$

さらに、$$X \otimes I \otimes Z$$

を左に$X$を表す1を、右の方に$Z$を表す1をとるように二元のベクトル表現をすると

$$(\begin{array}{c}

100\ 001

\end{array})$$

とかけます。同様に生成元を上から$S_1,..,S_6$と表す行列$H$は

$$H=\left(\begin{array}{c}

0001111\ 0000000\\

0110011\ 0000000\\

1010101\ 0000000\\

0000000\ 0001111\\

0000000\ 0110011\\

0000000\ 1010101\\

\end{array}\right)$$

とかけます。さらに測定の性質から、誤り$E$のベクトル表現$e$とシンドロームのベクトル表現$b$に対して、

$$H\Lambda e^T=b^T$$

が成り立ちます。ここで、

$$\Lambda=\left(\begin{array}{cc}

O & I_{n=7}\\

I_{n=7} & O

\end{array}\right)$$

とします。こうすると、誤り$F$に対して、シンドロームが得られるので、シンドロームを測定で得るのと等価な操作が簡単に実装できます。

また、$S_i$に対して$T(\beta_i)$を以下のように定めます。

$$\begin{array}{c}T(\beta_1):I\otimes I \otimes I \otimes Z \otimes I \otimes I\otimes I\\

T(\beta_2):I\otimes Z \otimes I \otimes I \otimes I \otimes I\otimes I\\

T(\beta_3):Z\otimes I \otimes I\otimes I \otimes I \otimes I\otimes X\\

T(\beta_4):I\otimes I \otimes I \otimes X \otimes I \otimes I\otimes I\\

T(\beta_5):I\otimes X \otimes I \otimes I \otimes I \otimes I\otimes I\\

T(\beta_6):X\otimes I \otimes I \otimes I \otimes I \otimes I\otimes I\\

\end{array}$$

ここで、$\beta_i$は$S_i$に対する測定の時のみ-1が得られるようなシンドロームとします。すなわち、

$$\beta_i=(1,1,1,...1,-1,1,1,1,1,1)$$

のように$i$ばんめだけ、-1であるようなシンドロームです。この時、$T(\beta_i)$のベクトル表現$t(\beta_i)$は

$$\begin{array}{c}

t(\beta_1)=0000000\ 0001000\\

t(\beta_2)=0000000\ 0100000\\

t(\beta_3)=0000000\ 1000000\\

t(\beta_4)=0001000\ 0000000\\

t(\beta_5)=0100000\ 0000000\\

t(\beta_6)=1000000\ 0000000\\

\end{array}$$

$X,Z$などの演算子の積

$$XZ$$

は、ベクトル表現では、ビット列の足し算で書けるため、

$$E=SLT(\beta)$$

という条件は

$$e=s+l+t(\beta)$$

ここまでくると、復号のためのプログラムを記述することができるようになります。


4.2実装

今回通信路はdepolarizing通信路と呼ばれる1-量子ビットに対して

$$\begin{array}{c}

P(I)=1-p\\

P(X)=p/3\\

P(Y)=p/3\\

P(Z)=p/3\\

\end{array}$$

で発生するような通信路でやってみました。

とりあえず、誤り確率0.01から0.20まで計算してみます。

import numpy as np

import random
import matplotlib.pyplot as plt

##################
#エラー生成
##################
def generateError(qBit,deporalizingProb):
error = np.zeros(qBit*2,dtype='object')
for i in range(qBit):
prob=np.random.rand()
if prob<deporalizingProb/3:
error[i]=1
elif prob<2 * deporalizingProb/3:
error[i+qBit]=1
elif prob<3 * deporalizingProb/3:
error[i]=1
error[i+qBit]=1
return error

####################
#固定部分群のベクトル表現
####################
def getH():
H=np.array([[0,0,0,1,1,1,1,0,0,0,0,0,0,0],[0,1,1,0,0,1,1,0,0,0,0,0,0,0],[1,0,1,0,1,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,1,1,1,1],[0,0,0,0,0,0,0,0,1,1,0,0,1,1],[0,0,0,0,0,0,0,1,0,1,0,1,0,1]])
return H

#######################
#固定部分群の元を返す。
#######################
def getS(v):
H=getH()
return ((v>>5)&1*H[0])^((v>>4)&1*H[1])^((v>>3)&1*H[2])^((v>>2)&1*H[3])^((v>>1)&1*H[4])^((v>>0)&1*H[5])

################
#Tを返す。
################
def getT(v):
t=np.array([[0,0,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0,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,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,0,0]])
return (v[0]*t[0])^(v[1]*t[1])^(v[2]*t[2])^(v[3]*t[3])^(v[4]*t[4])^(v[5]*t[5])

#######################
#Lを返す
####################
def getL(v):
L=np.array([[1,1,1,1,1,1,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,1,1,1,1]])
return ((v>>1)&1*L[0])^((v>>0)&1*L[1])

####################
#シンドローム測定
###################
def getSyndrome(H,e):
Lambda=np.kron(np.array([[0,1],[1,0]]),np.identity(len(e)//2))
return np.mod(np.dot(H,np.mod(np.dot(Lambda,e),2)),2).astype("int64")

####################
#確率分布を作る
####################
def getProb(prob,bit):
p=np.array([1-prob,prob/3,prob/3,prob/3])
return np.kron(np.kron(np.kron(np.kron(np.kron(np.kron(p.reshape(2,2),p.reshape(2,2)),p.reshape(2,2)),p.reshape(2,2)),p.reshape(2,2)),p.reshape(2,2)),p.reshape(2,2)).reshape(4 ** bit)

####################
#Lを推定
###################
def estimateL(prob,b):
t=getT(b)
probOut=np.zeros(4)
for ss in range(2 ** 6):
s=getS(ss)
for ll in range(4):
ee=0
l=getL(ll)
e=s+t+l
for c in range(len(e)//2):
ee+=(e[c]<<(len(e)//2-c-1))
probOut[ll]+=prob[ee]
return getL(probOut.argmax())

###############
#計算
###############
def calc(p):
prob=p
BIT=7
e=generateError(BIT,prob)
b=getSyndrome(getH(),e)
hatL=estimateL(getProb(prob,BIT),b)
for ss in range(2 ** 6):
#もし、L+T+EがSに含まれてたら復号成功
if(np.linalg.norm(np.mod(hatL+getT(b)+e+getS(ss),2))==0):
return True
return False

def drawGraph():
COUNT=2000
plt.yscale("log")
x = np.array([0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.10,0.11,0.12,0.13,0.14,0.15,0.16,0.17,0.18,0.19,0.20])
sum=np.zeros(len(x))
for xx in range(len(x)):
for count in range(COUNT):
if calc(x[xx])==True:
sum[xx]+=1

result=sum/COUNT
plt.plot(x, result, marker = 'x', label = '1')
plt.xlim(0.005, 0.21)
plt.ylim(0.01, 1)
plt.xlabel('Depolarizing Probability', fontsize = 16)
plt.ylabel('Decording Error Probability', fontsize = 16)
plt.tick_params(labelsize=14)
plt.grid(True)
plt.legend(loc = 'upper right')
plt.show()

drawGraph()


4.3 結果

Figure_1.png

なんだかんだ最尤復号で初めて測ったよSTEANE符号!!


4.4 コード

github


6. まとめ

今回は、量子誤り訂正の初歩を扱いました。もう少しわかりやすくなるよう加筆します...


7. 参考文献

・M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information