CSS 符号とハイパーグラフ積

$H_{X} H_{Z}^{T} = 0$ を満たす古典符号の検査行列から CSS 符号を作り、 $k = n - rank H_{X} - rank H_{Z}$ と符号距離 $d = min (d_{X}, d_{Z})$ を（mod 2 の階数計算で）求められる

前提

スタビライザー符号（大学院物理量子情報・量子計算）

この技能までの道筋（110 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
内積空間とグラム・シュミットの直交化（大学数学線形代数）
対称行列の直交対角化（大学数学線形代数）
2 次形式の標準形と符号（大学数学線形代数）
エルミート行列とエルミート形式の符号（大学数学線形代数）
音の伝わり方と大きさ・高さ（中学理科物理分野の用語と知識）
音の振動数と波形（中学理科光と音）
比例・反比例の式とグラフ（中学数学関数）
光子のエネルギーと運動量（高校物理原子）
根号の乗除と加減（中学数学数と式）
分母の有理化（中学数学数と式）
乗法公式・分配法則を使う根号の式の展開（中学数学数と式）
根号を含む式の計算と分母の有理化（数学I 数と式）
重力と力の大きさ（中学理科力のはたらき）
2 力のつり合いと作用・反作用（中学理科力のはたらき）
力の種類とはたらき（中学理科物理分野の用語と知識）
重力・垂直抗力・張力の性質（高校物理力と運動（知識））
慣性の法則と力のつり合い（高校物理力と運動（知識））
力の分解と質点のつり合い（高校物理力と運動）
静止摩擦力・最大摩擦力・動摩擦力（高校物理力と運動（知識））
静止摩擦力と動摩擦力（高校物理力と運動）
仕事（高校物理仕事・エネルギーと運動量）
運動エネルギーと仕事の関係（高校物理仕事・エネルギーと運動量）
物質波（ド・ブロイ波）（高校物理原子）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
$sin x / x$ の極限（数学III 極限）
三角関数の導関数（数学III 微分法）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
広義積分（大学数学微分積分）
波動関数の規格化と確率解釈（大学物理量子力学（1 次元の問題））
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
演算子と期待値（大学物理量子力学（1 次元の問題））
スピン 1/2 とパウリ行列（大学物理量子力学（角運動量・近似法））
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
合同式（数学A 整数の性質）
線形符号と生成行列（大学数学情報理論・符号理論）
検査行列と最小距離（大学数学情報理論・符号理論）
スタビライザー符号（大学院物理量子情報・量子計算）

説明

CSS 符号は、スタビライザーを「 $X$ だけでできたもの」と「 $Z$ だけでできたもの」に分けて作る量子符号で、2 つの古典符号の検査行列 $H_{X}, H_{Z}$ から組み立てられます。この技能を身につけると、 $H_{X} H_{Z}^{T} = 0 (mod 2)$ を確かめて CSS 符号を作り、論理量子ビット数 $k = n - rank H_{X} - rank H_{Z}$ と符号距離 $d = min (d_{X}, d_{Z})$ を mod 2 の行列計算だけで求められるようになります。さらに、任意の 2 つの古典符号から必ず CSS 符号を作るハイパーグラフ積を使うと、表面符号のような符号を系統的に作り、そのパラメータを古典符号のパラメータから読み取れます。

なぜそうしてよいのか

$n$ 量子ビットのパウリ演算子のうち、各量子ビットに $X$ か $1$ だけを並べたものを、 $X$ を置いた位置を 1 とする長さ $n$ の 0/1 ベクトル $u$ で表して $X (u)$ と書き、同様に $Z (v)$ を定めます。1 つの量子ビットの上では $X$ と $Z$ は反可換なので、 $X (u)$ と $Z (v)$ は「両方が置かれた位置の数 $u \cdot v$ 」が偶数なら可換、奇数なら反可換です。そこで $m_{X} \times n$ 行列 $H_{X}$ の各行 $u$ に対して $X (u)$ 、 $m_{Z} \times n$ 行列 $H_{Z}$ の各行 $v$ に対して $Z (v)$ をスタビライザー生成元にとります。 $X$ 型どうし・ $Z$ 型どうしは常に可換なので、全体が可換になる条件は「どの行どうしの内積も偶数」、つまり $H_{X} H_{Z}^{T} = 0 (mod 2)$ です。これが CSS 符号の条件です（以下、行列の計算はすべて mod 2）。

独立な生成元の数は、 $X$ 型の中で独立なもの $rank H_{X}$ 個と $Z$ 型の中で独立なもの $rank H_{Z}$ 個の和です（ $X$ 型の積は $X$ 型にしかならないので、型をまたいだ従属関係はありません）。スタビライザー符号の $k = n - (独立な生成元の数)$ から $k = n - rank H_{X} - rank H_{Z}$ が出ます。符号距離については、 $X (u)$ が全スタビライザーと可換である条件は $Z$ 型生成元との可換性だけで決まり $H_{Z} u = 0$ 、それがスタビライザー自身（ $X$ 型スタビライザーの積）でない条件は $u$ が $H_{X}$ の行空間 $row H_{X}$ に入らないことです。よって $X$ 型の論理演算子の最小重みは $d_{X} = min {∣ u ∣ : u \in ker H_{Z}, u \in / row H_{X}}$ 、同様に $d_{Z} = min {∣ v ∣ : v \in ker H_{X}, v \in / row H_{Z}}$ です（ $∣ u ∣$ は 1 の個数）。 $X$ と $Z$ が混ざった論理演算子の重みは、その $X$ 部分か $Z$ 部分のどちらかが自明でないので $min (d_{X}, d_{Z})$ 以上になり、 $d = min (d_{X}, d_{Z})$ となります。

ハイパーグラフ積は、条件 $H_{X} H_{Z}^{T} = 0$ を自動的に満たす作り方です。2 つの行列の「クロネッカー積」 $A \otimes B$ を、 $A$ の各成分 $a_{ij}$ をブロック $a_{ij} B$ に置き換えた行列と定めます。古典符号の検査行列 $H_{1}$ （ $m_{1} \times n_{1}$ ）、 $H_{2}$ （ $m_{2} \times n_{2}$ ）に対し $H_{X} = (H_{1} \otimes I_{n_{2}} I_{m_{1}} \otimes H_{2}^{T}), H_{Z} = (I_{n_{1}} \otimes H_{2} H_{1}^{T} \otimes I_{m_{2}})$ とおくと、 $(A \otimes B) (C \otimes D) = A C \otimes B D$ により $H_{X} H_{Z}^{T} = H_{1} \otimes H_{2}^{T} + H_{1} \otimes H_{2}^{T} = 2 (H_{1} \otimes H_{2}^{T}) = 0 (mod 2)$ です。量子ビット数は $n = n_{1} n_{2} + m_{1} m_{2}$ 、論理量子ビット数は $k = k_{1} k_{2} + k_{1}^{T} k_{2}^{T}$ になることが知られています。ここで $k_{i} = n_{i} - rank H_{i}$ 、 $k_{i}^{T} = m_{i} - rank H_{i}$ （ $H_{i}^{T}$ を検査行列とみた「転置符号」の次元）です。距離は $d = min (d_{1}, d_{2}, d_{1}^{T}, d_{2}^{T})$ （ $d_{i}^{T}$ は転置符号の距離で、 $k_{i}^{T} = 0$ のときは除く）。たとえば長さ 3 の繰り返し符号 $H = (101101)$ どうしの積は $n = 9 + 4 = 13$ 、 $k = 1 \cdot 1 + 0 \cdot 0 = 1$ 、 $d = 3$ で、表面符号 $[[13, 1, 3]]$ になります。

手順

$H_{X}$ （ $X$ 型スタビライザー）と $H_{Z}$ （ $Z$ 型スタビライザー）を用意し、 $H_{X} H_{Z}^{T} = 0 (mod 2)$ 、つまり $H_{X}$ のどの行と $H_{Z}$ のどの行も 1 の重なりが偶数個であることを確かめる（ハイパーグラフ積なら $H_{X} = (H_{1} \otimes I_{n_{2}} ∣ I_{m_{1}} \otimes H_{2}^{T})$ , $H_{Z} = (I_{n_{1}} \otimes H_{2} ∣ H_{1}^{T} \otimes I_{m_{2}})$ で自動的に成り立つ）
$rank H_{X}$ と $rank H_{Z}$ を mod 2 の掃き出し法で求める（ $1 + 1 = 0$ として行を足し引きする）
$k = n - rank H_{X} - rank H_{Z}$ を計算する（ハイパーグラフ積なら $n = n_{1} n_{2} + m_{1} m_{2}$ , $k = k_{1} k_{2} + k_{1}^{T} k_{2}^{T}$ ）
$d_{X}$ を求める： $H_{Z} u = 0$ を満たし、 $H_{X}$ の行の和（行空間）では書けない $u$ のうち、1 の個数が最小のものの重み
$d_{Z}$ を求める： $H_{X} v = 0$ を満たし、 $H_{Z}$ の行空間に入らない $v$ のうち最小の重み
$d = min (d_{X}, d_{Z})$ として $[[n, k, d]]$ をまとめる

例題

6 量子ビットの CSS 符号を、 $X$ 型スタビライザーの検査行列 $H_{X} = (101011110101)$ と $Z$ 型スタビライザーの検査行列 $H_{Z} = 100100010010001001$ で定める（ $H_{X}$ の行 $u$ に $X (u)$ 、 $H_{Z}$ の行 $v$ に $Z (v)$ を対応させる）。この符号の論理量子ビット数 $k$ と符号距離 $d$ を、 $(k, d)$ の組として順に求めよ。

例題の解答

【手順 1】 $H_{X}$ の 1 行目 $111100$ と $H_{Z}$ の各行の重なりは $2, 2, 0$ 個、2 行目 $001111$ とは $0, 2, 2$ 個で、すべて偶数。よって $H_{X} H_{Z}^{T} = 0 (mod 2)$ で、CSS 符号になっている。

【手順 2】 $H_{X}$ の 2 行は異なり、どちらも 0 でないので $rank H_{X} = 2$ 。 $H_{Z}$ の 3 行は 1 の位置が互いに重ならないので独立で $rank H_{Z} = 3$ 。

【手順 3】 $k = 6 - 2 - 3 = 1$ 。

【手順 4】 $ker H_{Z}$ は $u_{1} = u_{2}, u_{3} = u_{4}, u_{5} = u_{6}$ を満たす $u$ で、 $110000, 001100, 000011$ の和で書けるものすべて（8 個）。 $row H_{X} = {000000, 111100, 001111, 110011}$ 。 $ker H_{Z}$ から $row H_{X}$ を除くと $110000, 001100, 000011, 111111$ が残り、最小の重みは $2$ 。よって $d_{X} = 2$ （例： $X_{1} X_{2}$ は論理演算子）。

【手順 5】 $ker H_{X}$ は $u_{1} + u_{2} + u_{3} + u_{4} = 0$ , $u_{3} + u_{4} + u_{5} + u_{6} = 0$ を満たす $v$ 。 ${1, 2}, {3, 4}, {5, 6}$ に含まれる 1 の個数を $a, b, c$ とすると $a + b$ と $b + c$ が偶数、つまり $a, b, c$ の偶奇がそろう。重み 1 では偶奇がそろわない。重み 2 では $a, b, c$ がすべて偶数で、 $110000, 001100, 000011$ のどれかになるが、これらは $H_{Z}$ の行そのもので $row H_{Z}$ に入る。重み 3 では $a = b = c = 1$ 、たとえば $101010$ が $ker H_{X}$ に入り、 $row H_{Z}$ の元は $a, b, c$ がすべて偶数なのでこれは $row H_{Z}$ に入らない。よって $d_{Z} = 3$ 。

【手順 6】 $d = min (2, 3) = 2$ 。この符号は $[[6, 1, 2]]$ で、答えは $(k, d) = (1, 2)$ 。

答え: $(1, 2)$

よくある誤り

階数を実数の行列として計算してしまう誤り。正しくは mod 2 で計算する。たとえば行 $110, 011, 101$ は実数では行列式が $2 \neq = 0$ で階数 3 だが、mod 2 では 3 行の和が $000$ になり階数は 2。 $k$ が 1 ずれる
$d_{X}$ を $ker H_{X}$ から探してしまう誤り。 $X (u)$ が可換であるべき相手は $Z$ 型スタビライザーなので、正しくは $d_{X}$ は $ker H_{Z} ∖ row H_{X}$ 、 $d_{Z}$ は $ker H_{X} ∖ row H_{Z}$ の最小重みである
行空間に入るベクトル（スタビライザーそのもの）を除かずに最小重みをとる誤り。例題で $ker H_{X}$ の最小重みは $2$ （ $110000$ など）だが、これは $Z$ 型スタビライザー $Z_{1} Z_{2}$ で符号状態に何もしない。除いて調べると正しくは $d_{Z} = 3$
ハイパーグラフ積の量子ビット数や論理量子ビット数で項を落とす誤り。正しくは $n = n_{1} n_{2} + m_{1} m_{2}$ 、 $k = k_{1} k_{2} + k_{1}^{T} k_{2}^{T}$ （ $k_{i}^{T} = m_{i} - rank H_{i}$ ）。長さ 3 の繰り返し符号どうしで $n = 9$ としてしまうのは誤りで $n = 13$ 。巡回的な繰り返し符号 $3 \times 3$ （ $k^{T} = 1$ ）どうしなら $k = 1 + 1 = 2$ で、 $k = 1$ ではない

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$n = 6$ 量子ビットの CSS 符号を、 $F_{2}$ 上の 2 つの検査行列
$H_{X} = (111111), H_{Z} = 100110010101010100100010$
で定める。 $H_{X}$ の各行は $X$ 型のスタビライザー生成元（1 の位置の量子ビットに $X$ をかける）、 $H_{Z}$ の各行は $Z$ 型のスタビライザー生成元を表す。
この符号が $H_{X} H_{Z}^{T} = 0$ （mod 2）を満たすことを用いて、符号化される論理量子ビットの数 $k$ を求めよ。

この技能を使う問題

難易度 3（大学院入試の専門科目の標準レベル）
$F_{2} = {0, 1}$ 上の 2 つのパリティ検査行列
$H_{1} = 001010011100101110111 (3 \times 7), H_{2} = 101110011 (3 \times 3)$
を考える（ $H_{1}$ は長さ 7 のハミング符号、 $H_{2}$ は長さ 3 の巡回的な繰り返し符号の検査行列である）。これらから、ハイパーグラフ積と呼ばれる CSS 符号を次のように作る。 $\otimes$ をクロネッカー積、 $I_{m}$ を $m$ 次単位行列とし、演算はすべて mod 2 で行う。
$H_{X} = (H_{1} \otimes I_{3} I_{3} \otimes H_{2}^{T}), H_{Z} = (I_{7} \otimes H_{2} H_{1}^{T} \otimes I_{3})$
$H_{X}$ の各行を $X$ 型スタビライザー生成元、 $H_{Z}$ の各行を $Z$ 型スタビライザー生成元（行ベクトルの成分 1 の位置の量子ビットに $X$ または $Z$ を作用させるパウリ演算子）とする。列の数が物理量子ビット数 $n$ である。
この符号の物理量子ビット数 $n$ 、論理量子ビット数 $k$ 、符号距離 $d$ （スタビライザー群の元ではないが全スタビライザーと可換なパウリ演算子の重みの最小値）を求め、組 $(n, k, d)$ の形で答えよ。