量子誤り訂正(quantum error correction)とは、量子ビットの状態を多数の量子ビットの部分空間(量子符号)に符号化し、雑音による誤りを符号化した状態を壊さずに取り除く方法である。符号の射影 $P$ が誤りの集合 $\{E_a\}$ を訂正できるのは、$PE_a^\dagger E_bP=c_{ab}P$ が成り立つとき、かつそのときに限る(Knill–Laflamme の条件)。訂正できる誤りの 1 次結合も訂正できるので、1 量子ビットの $X,Y,Z$ を直せば任意の 1 量子ビットの誤りが直る。可換な Pauli 演算子の群で固定される空間として作る安定化符号が標準的な枠組みで、Shor の 9 量子ビット符号、5 量子ビット符号、Steane 符号がその例である。
量子誤り訂正(quantum error correction)は、量子ビットの状態を多数の量子ビットに符号化し、雑音で生じた誤りを、符号化した状態を壊さずに取り除く方法である。量子計算機の量子ビットは周囲との相互作用で状態が崩れやすいので、長い計算には誤り訂正が欠かせない。
古典の 誤り訂正符号 と比べて、3 つの困難がある。量子状態は複製できない(複製不可能定理)、状態を測ると壊れる、誤りは連続的な値をとりうる。1995 年に Shor は 9 量子ビットの符号でこれらを乗り越えられることを示した(Got09 §2.1、pp. 2–3)。
この記事では量子符号と回復操作を定義し、符号が誤りの集合を訂正できるための必要十分条件(Knill–Laflamme の条件、主定理)を、回復操作を具体的に作って証明する。次に、誤り訂正の標準的な枠組みである安定化符号の次元と訂正の条件、非縮退な符号の量子 Hamming 限界を証明する。しきい値定理などは述べるだけにする。
$n$ 量子ビットの状態は $\mathcal{H}=(\mathbb{C}^2)^{\otimes n}$(次元 $2^n$)の単位ベクトルで、定数倍の位相を除いて考える(量子計算)。
Pauli 群:$X=\begin{pmatrix}0&1\\1&0\end{pmatrix}$、$Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$、$Y=iXZ=\begin{pmatrix}0&-i\\i&0\end{pmatrix}$ とする(Pauli行列 の $\sigma_1,\sigma_3,\sigma_2$)。$i^c\,\sigma_1\otimes\dots\otimes\sigma_n$($c\in\{0,1,2,3\}$、$\sigma_j\in\{I,X,Y,Z\}$)の全体 $\mathcal{P}_n$ は積について群をなし、Pauli 群 という。$I$ でない因子の個数を 重み という。$X_j$ は $j$ 番目の量子ビットに $X$、他に $I$ を作用させる演算子を表す。
$X,Y,Z$ のどの 2 つも反可換なので、$\mathcal{P}_n$ の 2 つの元は可換か反可換のどちらかである。また $\{I,X,Y,Z\}^{\otimes n}$ の $4^n$ 個の元は $\mathcal{H}$ 上の線形演算子全体の基底である(Pauli行列 の定理と テンソル積)。
$\psi\in C$ に誤り $E_a$ が起きた状態 $E_a\psi$ に回復操作を施すと、$\sum_rR_rE_a\psi\psi^\dagger E_a^\dagger R_r^\dagger=\bigl(\sum_r\lvert\lambda_{ra}\rvert^2\bigr)\psi\psi^\dagger$ となり、元の状態が定数倍を除いて戻る。定数は、誤りの起こり方の確率の重みを表す。KL97 は回復後の状態との距離で訂正を定義し、それがこの条件と同値であることを示している(KL97 Theorem 3.1、p. 12)。
$C$ の 距離 $d$ は、$PEP$ が $P$ の定数倍にならない $E\in\mathcal{P}_n$ の重みの最小値である。$n$ 量子ビットで $k$ 量子ビットを符号化する距離 $d$ の符号を $[\![n,k,d]\!]$ 符号という。
この記事の主張が使える条件をまとめる。
| 主張 | 条件 | 結論 | 根拠 |
|---|---|---|---|
| Knill–Laflamme の条件 | なし | $C$ が $\mathcal{E}$ を訂正できる $\iff$ $PE_a^\dagger E_bP=c_{ab}P$ | thm-qec-kl |
| 線形結合 | $C$ が $\{E_a\}$ を訂正 | $\{E_a\}$ の 1 次結合もすべて同じ回復操作で訂正 | cor-qec-linear |
| 距離と訂正 | 距離 $d$ | 重み $\lfloor(d-1)/2\rfloor$ 以下の任意の誤りを訂正 | cor-qec-linear |
| 安定化符号の次元 | $S$ は可換、$-I\notin S$、独立な生成元 $a$ 個 | $\dim T(S)=2^{n-a}$ | prop-qec-stab |
| 安定化符号の訂正 | $E_a^\dagger E_b$ が $S$ の元の定数倍か、$S$ のある元と反可換 | $T(S)$ は $\{E_a\}$ を訂正 | prop-qec-stab |
| 量子 Hamming 限界 | 非縮退、重み $t$ 以下を訂正 | $2^k\sum_{j=0}^t\binom nj3^j\le2^n$ | prop-qec-hamming |
| 量子 Singleton 限界 | $[\![n,k,d]\!]$ 符号 | $n-k\ge2d-2$ | 証明しない:Got09 (38)(p. 8) |
| 反転符号の失敗確率 | 各量子ビットが独立に確率 $p$ で反転 | $3p^2-2p^3$ | ex-qec-bitflip |
| 複製不可能定理 | なし | すべての $\psi$ で $\psi\mapsto\psi\otimes\psi$ となる量子操作はない | 証明しない:Got09 Theorem 1(p. 2) |
| しきい値定理 | 誤り率がしきい値未満 | 任意の精度の計算が多重対数倍の資源でできる | 証明しない:Got09 Theorem 10(p. 41) |
符号 $C$(射影 $P$)と誤りの有限集合 $\mathcal{E}=\{E_1,\dots,E_N\}$ について、次は同値である。
条件 2 は、$C$ の正規直交基底 $\{\psi_i\}$ で書くと、$\langle\psi_i,E_a^\dagger E_b\psi_j\rangle=c_{ab}\delta_{ij}$ である。誤りは符号語を区別できない形でしか符号語に触れてはならず($i$ によらない)、異なる符号語を移した先は直交しなければならない($i\ne j$ で $0$)。KL97 Theorem 3.2(p. 13)の (19)、(20) はこの形である。
1 ⇒ 2. 回復操作 $\{R_r\}$ で $R_rE_a\psi=\lambda_{ra}\psi$($\psi\in C$)とする。$\psi,\varphi\in C$ について、$\sum_rR_r^\dagger R_r=I$ から
$$
\langle\psi,E_a^\dagger E_b\varphi\rangle=\sum_r\langle R_rE_a\psi,R_rE_b\varphi\rangle=\Bigl(\sum_r\overline{\lambda_{ra}}\lambda_{rb}\Bigr)\langle\psi,\varphi\rangle
$$
である。$c_{ab}=\sum_r\overline{\lambda_{ra}}\lambda_{rb}$ とおけば、これは $PE_a^\dagger E_bP=c_{ab}P$ を意味する。
2 ⇒ 1. $c$ は $\overline{c_{ab}}=c_{ba}$($PE_a^\dagger E_bP$ の随伴をとる)をみたす Hermite 行列で、$\sum_a\alpha_aE_a=F$ について $c$ の 2 次形式は $\langle\psi,F^\dagger F\psi\rangle=\|F\psi\|^2\ge0$($\psi\in C$ は単位ベクトル)なので半正定値である。ユニタリ行列 $U=(u_{ak})$ で $U^\dagger cU=\mathrm{diag}(d_1,\dots,d_N)$($d_k\ge0$)と対角化し(スペクトル定理)、
$$
F_k=\sum_au_{ak}E_a
$$
とおく。すると
$$
PF_k^\dagger F_lP=\sum_{a,b}\overline{u_{ak}}u_{bl}\,c_{ab}P=d_k\delta_{kl}P
$$
である。$d_k=0$ なら $\|F_k\psi\|^2=0$ で $F_kP=0$ である。$d_k>0$ の $k$ について $\Pi_k=d_k^{-1}F_kPF_k^\dagger$ とおくと、上の式から $\Pi_k$ は直交射影で、$k\ne l$ なら $\Pi_k\Pi_l=0$ である(像 $F_kC$ と $F_lC$ が直交する)。そこで
$$
R_k=d_k^{-1/2}PF_k^\dagger\quad(d_k>0),\qquad R_0=I-\sum_{d_k>0}\Pi_k
$$
とおく。$R_k^\dagger R_k=d_k^{-1}F_kPF_k^\dagger=\Pi_k$ で、$R_0$ は射影なので $R_0^\dagger R_0=R_0$、よって $\sum R^\dagger R=I$ である。
$E=FU^\dagger$ と書き直すと $E_a=\sum_k\overline{u_{ak}}F_k$ である。$\psi\in C$ について $F_k\psi$ は $d_k>0$ の項だけが残り、$E_a\psi\in\bigoplus_kF_kC$ なので $R_0E_a\psi=0$ である。また
$$
R_kE_a\psi=d_k^{-1/2}\sum_l\overline{u_{al}}\,PF_k^\dagger F_l\psi=d_k^{-1/2}\,\overline{u_{ak}}\,d_k\psi=\sqrt{d_k}\,\overline{u_{ak}}\,\psi
$$
で、$\lambda_{ka}=\sqrt{d_k}\,\overline{u_{ak}}$、$\lambda_{0a}=0$ とおけば訂正の条件が成り立つ。$\square$
証明の回復操作は「$F_kC$ のどれにいるかを測り($\Pi_k$)、$F_k$ の作用を戻す」ことを表す。$F_k$ は誤り $E_a$ の 1 次結合で、互いに直交する部分空間へ符号を移す。
1. $R_rE\psi=\sum_a\alpha_aR_rE_a\psi=\bigl(\sum_a\alpha_a\lambda_{ra}\bigr)\psi$。
2. 重み $t$ 以下の $E_a,E_b\in\mathcal{P}_n$ について、$E_a^\dagger E_b$ は重み $2t\le d-1$ 以下の Pauli 演算子なので、距離の定義から $PE_a^\dagger E_bP$ は $P$ の定数倍で、thm-qec-kl により訂正できる。$t$ 個の量子ビットに作用する演算子は、その量子ビットの上の $\{I,X,Y,Z\}^{\otimes t}$ の 1 次結合なので、1 により同じ回復操作で訂正される。$\square$
1 量子ビットの誤りは連続的な値をとるが、$X_j,Y_j,Z_j$ の 3 つ(と $I$)を訂正すれば全部訂正できる(Got09 Theorem 2、p. 4)。これが「誤りの離散化」で、古典の符号の考え方を量子の誤りに使えるようになる理由である。
$\mathcal{P}_n$ の可換な部分群 $S$ で $-I\notin S$ をみたすものを 安定化群 という。$S$ のすべての元で固定される状態の空間
$$
T(S)=\{\psi\in\mathcal{H}:g\psi=\psi\ (g\in S)\}
$$
を 安定化符号 という。$S$ の生成元 $g_1,\dots,g_a$ で、どの $g_j$ も他の生成元の積でないものを 独立な生成元 という。
$S$ を独立な生成元 $g_1,\dots,g_a$ をもつ安定化群とする。
1. $g\in\mathcal{P}_n$ は $g=i^c\sigma$($\sigma\in\{I,X,Y,Z\}^{\otimes n}$)と書け、$\sigma^2=I$ から $g^2=(-1)^cI$ である。$g\in S$ なら $g^2\in S$ で $-I\notin S$ なので $g^2=I$、つまり $c$ は偶数で $g=\pm\sigma$ は Hermite である。$S$ は可換で各元の位数は $2$ 以下なので、$S$ の元は $g_1^{e_1}\cdots g_a^{e_a}$($e_j\in\{0,1\}$)と書ける。2 つの書き方が同じ元を与えると、ある $g_j$ が他の生成元の積になり独立性に反するので、$\lvert S\rvert=2^a$ である。$\frac{I+g_j}2$ は $g_j$ の $+1$ 固有空間への射影で、互いに可換なので積 $P$ は共通の $+1$ 固有空間 $T(S)$ への射影である。展開すると $P=2^{-a}\sum_{g\in S}g$ である。$S$ の元のうち $I$ の定数倍は $I$ だけで($-I\notin S$、$\pm iI$ は $g^2=-I$)、$I$ 以外の $g=\pm\sigma$ は少なくとも 1 つの因子が $X,Y,Z$ なのでトレースが $0$ である。よって
$$
\dim T(S)=\operatorname{tr}P=2^{-a}\operatorname{tr}I=2^{n-a}.
$$
2. $Eg=-gE$($g\in S$)とする。$\psi,\varphi\in T(S)$ について、$g$ は Hermite で $g\psi=\psi$ なので
$$
\langle\psi,E\varphi\rangle=\langle\psi,Eg\varphi\rangle=-\langle\psi,gE\varphi\rangle=-\langle g\psi,E\varphi\rangle=-\langle\psi,E\varphi\rangle
$$
で、$\langle\psi,E\varphi\rangle=0$、つまり $PEP=0$ である。$E=\alpha g$($g\in S$)なら $PEP=\alpha PgP=\alpha P$ である。
3. 2 により $PE_a^\dagger E_bP$ はどれも $P$ の定数倍で、thm-qec-kl による。
4. 重みが上の最小値より小さい $E\in\mathcal{P}_n$ は、$S$ のある元と反可換か、$S$ の元の定数倍である。どちらでも 2 により $PEP$ は $P$ の定数倍である。$\square$
4 の不等号は等号である(Got09 Theorem 5、p. 10。$S$ のすべての元と可換で $S$ の元の定数倍でない演算子が、符号の上で恒等の定数倍でないことを使う。この記事では証明しない)。この形の符号を $[\![n,n-a,d]\!]$ 符号と書く。
$C$ を $n$ 量子ビットの $2^k$ 次元の符号とし、重み $t$ 以下の $\{I,X,Y,Z\}^{\otimes n}$ の元 $E_a$ の全体を $\mathcal{E}$ とする。$C$ が 非縮退、すなわち $a\ne b$ なら $PE_a^\dagger E_bP=0$ であるとき
$$
2^k\sum_{j=0}^t\binom nj3^j\le2^n
$$
である。
$E_a$ はユニタリなので $E_aC$ は $2^k$ 次元である。$a\ne b$ なら $\langle E_a\psi,E_b\varphi\rangle=\langle\psi,PE_a^\dagger E_bP\varphi\rangle=0$($\psi,\varphi\in C$)で、$E_aC$ と $E_bC$ は直交する。重み $j$ の元は、位置の選び方 $\binom nj$ と各位置の $X,Y,Z$ の選び方 $3^j$ で $\binom nj3^j$ 個ある。互いに直交する $\sum_{j\le t}\binom nj3^j$ 個の $2^k$ 次元の部分空間が $2^n$ 次元の $\mathcal{H}$ に入るので、次元を比べればよい。$\square$
$k=1$、$t=1$ では $2(1+3n)\le2^n$ で、$n\ge5$ が必要である。等号の $n=5$ をみたす符号がある(ex-qec-five)。縮退した符号にはこの証明は使えないが、量子 Singleton 限界 $n-k\ge2d-2$ は縮退した符号にも成り立つ(Got09 (38)、p. 8)。
安定化符号の誤り訂正は次の手順で行う。
$\lvert0_L\rangle=\lvert000\rangle$、$\lvert1_L\rangle=\lvert111\rangle$ の張る $C$ は $S=\langle Z_1Z_2,Z_2Z_3\rangle$ の安定化符号である($n=3$、$a=2$、$\dim=2$)。使う公式:prop-qec-stab、thm-qec-kl。答え:$\{I,X_1,X_2,X_3\}$ を訂正でき、シンドロームは次の表のとおり。各量子ビットが独立に確率 $p$ で反転するとき、訂正の後に論理量子ビットが誤る確率は $3p^2-2p^3$ で、$p=0.1$ なら $0.028$ である。
| 誤り | $Z_1Z_2$ | $Z_2Z_3$ | 戻す操作 |
|---|---|---|---|
| $I$ | $+1$ | $+1$ | なし |
| $X_1$ | $-1$ | $+1$ | $X_1$ |
| $X_2$ | $-1$ | $-1$ | $X_2$ |
| $X_3$ | $+1$ | $-1$ | $X_3$ |
$X_a^\dagger X_b$($a\ne b$)は $X_1X_2$、$X_2X_3$、$X_1X_3$ のどれかで、$Z_1Z_2$ か $Z_2Z_3$ と反可換なので、prop-qec-stab の 3 が使える。失敗するのは 2 個以上が反転するときで、確率は $3p^2(1-p)+p^3=3p^2-2p^3$。$3p^2-2p^3< p$ は $p(2p-1)(p-1)>0$、すなわち $0< p<\frac12$ と同値である。
図: 1 量子ビットが反転する確率 p を横軸に、論理量子ビットが誤る確率を縦軸にとったグラフ。破線は符号なしの p、実線は 3 量子ビットの反転符号の 3p²−2p³。2 つは p=1/2 で交わり、p が 1/2 より小さいと符号を使うほうが誤りにくい。p=0.1 では 0.028 になる。
$\lvert0_L\rangle=\frac1{2\sqrt2}(\lvert000\rangle+\lvert111\rangle)^{\otimes3}$、$\lvert1_L\rangle=\frac1{2\sqrt2}(\lvert000\rangle-\lvert111\rangle)^{\otimes3}$ とする。使う公式:prop-qec-stab。答え:生成元 8 個の安定化符号で $\dim=2^{9-8}=2$、1 量子ビットの任意の誤りを訂正する $[\![9,1,3]\!]$ 符号である。縮退符号で、$Z_1$ と $Z_2$ は符号の上で同じ作用をもつ。
生成元は $Z_1Z_2$、$Z_2Z_3$、$Z_4Z_5$、$Z_5Z_6$、$Z_7Z_8$、$Z_8Z_9$、$X_1\cdots X_6$、$X_4\cdots X_9$(Got09 Table 2、p. 9)。$Z_1Z_2\in S$ なので $PZ_1^\dagger Z_2P=P$。$I$ と 1 量子ビットの誤り 27 個のシンドロームは 22 通りで、同じシンドロームの組は同じブロックの $Z$ どうしである。重み 2 以下で全生成元と可換な Pauli 演算子は $S$ の元の定数倍だけで、重み 3 の $X_1X_2X_3$ は可換だが $S$ にない。
生成元 $X_1Z_2Z_3X_4$、$X_2Z_3Z_4X_5$、$X_1X_3Z_4Z_5$、$Z_1X_2X_4Z_5$ の安定化符号(Got09 Table 4、p. 12)。使う公式:prop-qec-stab、prop-qec-hamming。答え:$\dim=2^{5-4}=2$、距離 $3$ の $[\![5,1,3]\!]$ 符号で、$I$ と 1 量子ビットの誤り 15 個のシンドロームは $2^4=16$ 通りすべて異なる(非縮退)。量子 Hamming 限界 $2(1+3\cdot5)=32=2^5$ は等号である。
| 主張 | 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|---|
| thm-qec-kl の 2 ⇒ 1 | $PE_a^\dagger E_bP=c_{ab}P$ | 反転符号と $\mathcal{E}=\{I,Z_1\}$ | $PZ_1P=P Z_1Z_2Z_3P$ は $\lvert0_L\rangle\pm\lvert1_L\rangle$ を入れ替え、$P$ の定数倍でない。1 ⇒ 2 により回復操作が存在しない |
| ex-qec-bitflip の訂正 | 誤りの集合を重み 1 以下に | $\mathcal{E}$ に $X_1X_2$ を加える | $X_1X_2$ のシンドロームは $X_3$ と同じで、$X_3$ を戻すと $X_1X_2X_3$(論理の反転)が残る |
| prop-qec-stab の 1 | $-I\notin S$ | $n=1$、$S=\{\pm I,\pm Z\}$ | $T(S)=\{0\}$ で、$2^{n-a}$ の式が成り立たない |
| 失敗確率が減る | $p<\frac12$ | $p=0.6$ | $3p^2-2p^3=0.648>0.6$ で、符号化で誤りやすくなる |
1 行目:$Z_1\lvert000\rangle=\lvert000\rangle$、$Z_1\lvert111\rangle=-\lvert111\rangle$ なので $Z_1$ は符号の上で $Z_1Z_2Z_3$(論理の $Z$)と同じで、$PZ_1P$ の固有値は $\pm1$。2 行目:$X_1X_2$ は $Z_1Z_2$ と可換、$Z_2Z_3$ と反可換で、シンドロームは $(+1,-1)$。3 行目:$g\psi=\psi$ と $-g\psi=\psi$ から $\psi=0$。$S$ は 4 元で、独立な生成元 $Z$、$-Z$ から $2^{1-2}$ という意味のない値になる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 状態を複製して多数決をとればよい | 量子状態は複製できない | 複製不可能定理(Got09 Theorem 1) |
| 誤りは連続的なので有限個の手順では直せない | $X_j,Y_j,Z_j$ を直せば 1 次結合も直る | cor-qec-linear |
| 誤りを調べるには状態を測る | 測るのはシンドロームだけで、符号語は壊さない | 計算の手順の 1 |
| シンドロームから誤りが決まらなければ訂正できない | 縮退符号では区別できない誤りが同じ作用をもつ | ex-qec-shor |
| 3 量子ビットの反転符号は 1 量子ビットの誤りを全部直す | 直せるのは反転 $X_j$ だけで、$Z_j$ は直せない | 反例の表の 1 行目 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する