量子情報理論の基本：量子誤り訂正（スタビライザー符号：１） #量子コンピュータ

$$
\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}}
$$

はじめに

これまで、量子誤り訂正と題したいくつかの記事において、歴史上はじめて考え出された符号化手法である「Shorの符号」や古典線形符号をベースに構築された「CSS符号」とその一実施例である「Steane符号」を取り上げ、説明してきました。今回は、それらを包含する、より広範囲な量子誤り訂正のクラスである「スタビライザー符号(stabilizer code)」について説明します。1回の記事ではとても説明しきれない分量になりそうなので、刻みます。今回は、スタビライザーとはそもそも何なのかという基礎知識と、スタビライザーというものが有意味であるためには、どんな条件が成り立っているべきなのかについて、理解することを目的とします。なので、すみませんが、符号化の話まで到達しません。次回以降の数回の記事で、スタビライザーを使ったゲート演算や測定、スタビライザー符号の構成、動作のシミュレーションというステップで説明を進めていこうと思います（予定です）。

参考にさせていただいたのは、以下の文献です。

ニールセン、チャン「量子コンピュータと量子通信（３）」オーム社（2005年）

スタビライザーとは？

量子誤り訂正を行うために、まず最初に必要なのは、もとの情報を冗長化して符号化するという手続きでした。が、これをテキトーに俺様手法で実施してもダメで、誤りを検出して復元できるようにするためには、ある工夫が必要でした。どんな工夫かというと、大きなヒルベルト空間の部分空間の要素として符号化された状態ベクトルを規定するのですが、何らかのきちんと定義された演算によって不変になる部分空間を符号空間とすることが必要でした。そうすることで、雑音が加わりその部分空間からもとの状態がはみだしたとしても、はみ出した方向を検知して、ちゃんと元に戻すことができるように上手な手法を構築することができます。

ここで大事なのは、ある演算を施しても不変になる部分空間というものであり、そしてそれを実現するための演算子です。各手法によっていろんな考え方がありました。例えば、Shorの符号の場合、量子ビット数が9（$2^9$次元）の大きなヒルベルト空間を考え、それに対して、

\begin{align}
\ket{0_L} &= \ket{000000000} \\
\ket{1_L} &= \ket{111111111} \tag{1}
\end{align}

という2つの基底で張られる部分空間が符号空間でした。このとき、$\alpha \ket{0} + \beta \ket{1}$に対する符号は$\alpha \ket{0_L} + \beta \ket{1_L}$になります。これは、

\begin{align}
P &= \ket{000000000}\bra{000000000} + \ket{111111111}\bra{111111111} \\
&= \ket{0_L}\bra{0_L} + \ket{1_L}\bra{1_L} \tag{2}
\end{align}

という射影演算子によって不変になる部分空間です。いま、「不変になる」という語を使いましたが、「安定化される」と言っても同じことなので、以後、「不変」の代わりに「安定化」または「スタビライズ」という語を使います。「スタビライザー符号」の文脈では、こっちの語の方が多く使われているようなので、それに従います。

Steane符号の場合はどうだったかというと、7量子ビットの大きなヒルベルト空間を考え、それに対して、

\begin{align}
\ket{0_L} &= \frac{1}{\sqrt{8}} (\ket{0000000} + \ket{1101001} + \ket{1011010} + \ket{0110011} + \ket{0111100} + \ket{1010101} + \ket{1100110} + \ket{0001111}) \\
\ket{1_L} &= \frac{1}{\sqrt{8}} (\ket{1111111} + \ket{0010110} + \ket{0100101} + \ket{1001100} + \ket{1000011} + \ket{0101010} + \ket{0011001} + \ket{1110000}) \tag{3}
\end{align}

という2つの基底で張られる部分空間が符号空間でした¹。これは、

\begin{align}
P = \ket{0_L}\bra{0_L} + \ket{1_L}\bra{1_L} \tag{4}
\end{align}

という射影演算子によって安定化（スタビライズ）される部分空間です。

この具体例からわかるように、

P \ket{\psi} = \ket{\psi}  \tag{5}

という等式を成り立たせる演算子$P$と、この$\ket{\psi}$を要素とする部分空間を考えることで、何らかの量子符号を構築することができます、と言えます。だとすると、上で示した演算子以外にもいろいろありそうです。例えば、1量子ビット状態に対するパウリ演算子$Z$を$P$としてみると、

Z \ket{\psi} = \ket{\psi}  \tag{6}

を満たす$\ket{\psi}$は$\ket{0}$ですし、パウリ演算子$X$を$P$としてみると、

X \ket{\psi} = \ket{\psi}  \tag{7}

を満たす$\ket{\psi}$は$\ket{+}=(\ket{0}+\ket{1})/\sqrt{2}$です。1量子ビット状態を考えるとパウリ演算子によってスタビライズされるのは、部分空間というより、ばっちり1つの状態になってしいまい、あまり面白くないです。が、ここで認識していただきたいのは、パウリ演算子の固有値は$+1$と$-1$であり、固有値$+1$に対応した固有状態を選ぶと、それはこのパウリ演算子によってスタイライズされる部分空間になるということです。複数量子ビット状態に対するパウリ演算子（のテンソル積）を考えると、もっと面白くなります。例えば、2量子ビット状態に対して演算子$P=Z_1 \otimes Z_2$を考えてみます（簡単のため、以後テンソル積の記号$\otimes$を省略して、$P=Z_1 Z_2$のように記載することにします）。ここで、$Z_1$は1番目の量子ビットに働くパウリ$Z$で、$Z_2$は2番目の量子ビットに働くパウリ$Z$です。とすると、

\begin{align}
Z_1 Z_2 \ket{00} &= \ket{00} \\
Z_1 Z_2 \ket{11} &= \ket{11} \\
Z_1 Z_2 \ket{01} &= -\ket{01} \\
Z_1 Z_2 \ket{10} &= -\ket{10} \tag{8}
\end{align}

が成り立つので、$Z_1 Z_2$によってスタビライズされるのは$\{ \ket{00}, \ket{11}\}$によって張られる部分空間であることがわかります。また、$P=X_1 X_2$としてみると、

\begin{align}
X_1 X_2 \ket{++} &= \ket{++} \\
X_1 X_2 \ket{--} &= \ket{--} \\
X_1 X_2 \ket{+-} &= -\ket{+-} \\
X_1 X_2 \ket{-+} &= -\ket{-+} \tag{9}
\end{align}

が成り立つので、$X_1 X_2$によってスタビライズされるのは$\{ \ket{++}, \ket{--}\}$によって張られる部分空間です。この例からわかるように、2量子ビット（4次元）の大きなヒルベルト空間に対して、スタビライズされた部分空間は2次元（半分）になります。3量子ビット以上を考えても同じことです。すなわち、$n$量子ビット（$2^n$次元）のヒルベルト空間を考えると、パウリ演算子の1個の組（テンソル積）によってスタビライズされる部分空間は$2^{n-1}$次元になります。パウリ演算子の組を1個ではなく複数個用意すると、その各々は別々の部分空間をスタビライズするので、その部分空間たちの共通集合をとることで、様々な次元の部分空間を定義できるということになります。このように規定された演算子の集まりのことを「スタビライザー」と言います。「スタビライザー符号」というのは、このスタビライザーをうまく利用して構築する量子誤り訂正符号のクラスです。実は、Shorの符号もCSS符号も、このスタビライザー符号の一つの形態と言えます。

さて、パウリ演算子を使ったスタビライザーについて、ざっくりイメージできたところで、もう少し理論的に精密な言い方をしてみたいと思います。その前に、まず「パウリ群」について触れておかないといけません。スタビライザーはパウリ群のある種の部分群と位置づけられますので。それから、群をより少ない要素から生成する「生成元」という概念についても述べます。

パウリ群とスタビライザー群と生成元

1量子ビット状態に対するパウリ群$G_1$は、以下のように単位演算子を含んだすべてのパウリ演算子からなる集合と定義されます。

G_1 = \{ \pm I, \pm iI, \pm X, \pm iX, \pm Y, \pm iY, \pm Z, \pm iZ \} \tag{10}

ここで、$\pm 1$や$\pm i$という係数が各々の演算子にかけられていますが、乗算のもとで「群」²をなすようにするためです。これは、$n$量子ビット状態に対しても定義できます。式(10)の集合のテンソル積集合として定義すれば良いです。すなわち、

G_n = \{ \pm I, \pm iI, \pm X, \pm iX, \pm Y, \pm iY, \pm Z, \pm iZ \}^{\otimes n} \tag{11}

です。例えば、$n=3$の場合、$X_1 Z_2 I_3$とか$-X_1 Z_2 Y_3$とか$i Z_1 Z_2 Z_3$とかその他もろもろが、パウリ群$G_3$の要素になります³。が、$X_1 + Z_2$とか$-X_1 + Z_2 Y_3$とかはパウリ群の要素ではありません。パウリ演算子の積の形で書けるものであればパウリ群の要素になります。

先程説明したスタビライザーは、このように定義されたパウリ群の部分集合です。このスタビライザーの各要素によってスタビライズされる$n$量子ビット状態の部分集合を$V_s$とします。このとき、$V_s$の2つの要素の線形和は必ず$V_s$の要素になるので、$V_s$はこのスタビライザーによってスタビライズされる部分空間と言えます⁴。この意味でスタビライザーの集まりは群をなします。以後、この群のことを「スタビライザー群」と言い、各要素のことを「スタビライザー」と言うことにします。

$n=3$の場合のスタビライザー群の具体例として、

S = \{ I, Z_1 Z_2, Z_2 Z_3, Z_3 Z_1 \}  \tag{12}

というものを考えてみます⁵。パウリ演算子の性質として、$Z_i Z_i = I, Z_i Z_j = Z_j Z_i$が成り立っているので、群をなすことは容易にわかります⁶。また、この$S$がどんな部分空間をスタビライズするかは、各要素が、$2^{3}=8$パターンの計算基底$\ket{000},\ket{001},\ket{010}, \cdots , \ket{111}$のうち、どの基底をスタビライズするか調べてみればわかります。ということで、やってみます。

スタビライザー	スタビライズされる基底
$I$	全部
$Z_1 Z_2$	$\ket{000},\ket{001},\ket{110},\ket{111}$
$Z_2 Z_3$	$\ket{000},\ket{100},\ket{011},\ket{111}$
$Z_3 Z_1$	$\ket{000},\ket{010},\ket{101},\ket{111}$
共通する基底	$\ket{000},\ket{111}$

共通する基底は$\ket{000}$と$\ket{111}$となりましたので、この2つの基底によって張られる部分空間が、この場合の$V_s$です。

さて、今一度、式(12)のスタビライザー群$S$を見てください。4つの要素から成り立っていますが、実は無駄があります。$(Z_1 Z_2) (Z_2 Z_3) = Z_3 Z_1$となり、1つの要素を他の2つの要素の積で表すことができますし、$(Z_1 Z_2) (Z_1 Z_2) = I$です。つまり、$Z_1 Z_2$と$Z_2 Z_3$という2つの要素があれば、すべての4つの要素をその積によって生成することができます。このように、ある群$G$のすべての要素を、$g_1,g_2 \cdots ,g_l$の積によって生成することができるとき、集合$\{ g_1,g_2 \cdots ,g_l \}$を群$G$の「生成元(generator)」と呼び、$G = < g_1,g_2 \cdots ,g_l >$と書きます。今の例の場合、$S = < Z_1 Z_2, Z_2 Z_3 >$となります。先程、スタビライザー群$S$によってスタビライズされる部分空間を調べるのに4つの要素それぞれに対して、基底をチェックしましたが、少数の生成元がわかっていれば、そんな必要はありません。生成元についてだけチェックすればOKです。すなわち、

スタビライザー	スタビライズされる基底
$Z_1 Z_2$	$\ket{000},\ket{001},\ket{110},\ket{111}$
$Z_2 Z_3$	$\ket{000},\ket{100},\ket{011},\ket{111}$
共通する基底	$\ket{000},\ket{111}$

ということで、同じ結果が得られました⁷。

もう一つ。生成元が「独立である」ことについても触れておきます。$g_1, \cdots , g_l$からなる生成元があったとき、ここから任意の$g_i$を取り除いたときに、生成される群が小さくなる（つまりスタビライズされる部分空間が小さくなる）とき、生成元$g_1, \cdots , g_l$は独立である、と言います。例えば、3量子ビット状態に対する$\{ I, Z_1 Z_2, Z_2 Z_3, Z_3 Z_1 \}$は独立な生成元ではありません。$\{ Z_1 Z_2, Z_2 Z_3, Z_3 Z_1 \}$は生成元ですが独立ではありません。$\{ Z_1 Z_2, Z_2 Z_3 \}$は独立な生成元です。ということですね。独立というのは要するに無駄がないということ、だと思っておけば良いと思います。

実例（Steane符号の場合）

Steane符号の符号空間は、式(3)の基底によって張られるベクトル空間でした。同じことをスタビライザーの言葉で言い換えることができます。まずは、天下りますが、以下がSteane符号のスタビライザー（を生成する生成元）です。

名称	スタビライザー
$g_1$	$I_1 \space I_2 \space I_3 \space X_4 \space X_5 \space X_6 \space X_7$
$g_2$	$I_1 \space X_2 \space X_3 \space I_4 \space I_5 \space X_6 \space X_7$
$g_3$	$X_1 \space I_2 \space X_3 \space I_4 \space X_5 \space I_6 \space X_7$
$g_4$	$I_1 \space I_2 \space I_3 \space Z_4 \space Z_5 \space Z_6 \space Z_7$
$g_5$	$I_1 \space Z_2 \space Z_3 \space I_4 \space I_5 \space Z_6 \space Z_7$
$g_6$	$Z_1 \space I_2 \space Z_3 \space I_4 \space Z_5 \space I_6 \space Z_7$

果たしてこれが本当に式(3)の基底で定義されるベクトル空間をスタビライズするものになっているのでしょうか？いきなり天下ったので、ん？という感じですよね。$2^7=128$個の基底の各々に対して、$g_1$から$g_6$の演算を試みてみるのも良いですが、そんな不毛な作業は暇な人に任せて、ここはもっとスマートに理解するようにしましょう⁸。

前回の記事で説明した、CSS符号の定義を再掲します。

\ket{x+C_2} \equiv \frac{1}{\sqrt{|C_{2}|}} \sum_{y \in C_2} \ket{x+y}  \tag{13}

Steane符号の場合、$C_1 = C, \space C_2 = C^{\perp}$とおいてCをHamming符号としたものです。改めて上の6個の生成元を見てください。$g_1,g_2,g_3$の3行に注目すると、各行は7個のパウリ演算子から成り立っています。各演算子の配置の仕方はHamming符号のパリティ検査行列に対応しています。すなわち、パリティ検査行列の1の場所をパウリ$X$で置き換え、0の場所を$I$に置き換えたものになっていることがわかります。同様に$g_4,g_5,g_6$の3行に注目すると、パリティ検査行列の1の場所をパウリ$Z$で置き換え、0の場所を$I$に置き換えたものになっていることがわかります。

式(13)の$C_2$はC（Hamming符号）の双対なので、生成行列$G$はパリティ検査行列$H$の転置行列（$7 \times 3$行列）です。つまり、すべての3次元バイナリ・ベクトル（8個）をもってきて、生成行列$G = H^{T}$を適用してやれば、$C_2$を生成することができます。$H$の各行を$h_1,h_2,h_3$というバイナリ・ベクトルで表し（各ベクトルの次元は7）、すべての3次元バイナリ・ベクトルを$(a_1, a_2, a_3)$と表すことにすると、式(13)は、

\ket{x+C_2} = \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{x + a_1 h_1 + a_2 h_2 +a_3 h_3}  \tag{14}

と書けます。$x$として異なる剰余類に属する2つのバイナリ・ベクトル（7次元）を適当に決めれば、この式(14)によって、符号空間の2つの基底が求まることになります。前回の記事で見たように、$x$として$v_0=(0,0,0,0,0,0,0)$と$v_1=(1,1,1,1,1,1,1)$を選べば良かったです。とすると、$\ket{0_L}, \ket{1_L}$は、

\begin{align}
\ket{0_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_0 + a_1 h_1 + a_2 h_2 +a_3 h_3}  \\
\ket{1_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_1 + a_1 h_1 + a_2 h_2 +a_3 h_3}  \tag{15}
\end{align}

となります。

では、$g_1,g_2,g_3,g_4,g_5,g_6$によって、この基底が本当にスタビライズされていることを示します。まず、$g_1$を演算してみます。$g_1$は$h_1$の1に相当している部分が$X$になっている演算子列です。つまり、$X$が置かれている場所のビットに1を（2を法として）加算する演算に相当します。ということで、式(15)に$g_1$を適用するということは、ケットの中身に$h_1$を加算するということに等しいです。すなわち、

\begin{align}
g_1 \ket{0_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_0 + a_1 h_1 + a_2 h_2 +a_3 h_3 + h_1} \\
&= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_0 + (a_1 + 1) h_1 + a_2 h_2 +a_3 h_3} \\
&= \ket{0_L} \\
g_1 \ket{1_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_1 + a_1 h_1 + a_2 h_2 +a_3 h_3 + h_1} \\
&= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} \ket{v_1 + (a_1 + 1) h_1 + a_2 h_2 +a_3 h_3} \\
&= \ket{1_L} \tag{16}
\end{align}

となり、$g_1$に対してスタビライズされていることがわかります。$g_2,g_3$についても同様に右辺のケットの中身に各々$h_2,h_3$を加算してみれば簡単にわかります。

次に、$g_4,g_5,g_6$について見てみます。今度は$X$の代わりに$Z$が登場します。例えば、$g_4$を適用すると、ビット反転ではなく位相反転の効果が現れます。

\begin{align}
g_4 \ket{0_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} (-1)^{(v_0 + a_1 h_1 + a_2 h_2 +a_3 h_3) h_1} \ket{v_0 + a_1 h_1 + a_2 h_2 +a_3 h_3} \\
&= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} (-1)^{0} \ket{v_0 + a_1 h_1 + a_2 h_2 +a_3 h_3} \\
&= \ket{0_L} \\
g_4 \ket{1_L} &= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} (-1)^{(v_1 + a_1 h_1 + a_2 h_2 +a_3 h_3) h_1} \ket{v_1 + a_1 h_1 + a_2 h_2 +a_3 h_3} \\
&= \frac{1}{\sqrt{8}} \sum_{a_1,a_2,a_3=0,1} (-1)^{0} \ket{v_1 + a_1 h_1 + a_2 h_2 +a_3 h_3} \\
&= \ket{1_L} \tag{17}
\end{align}

となり、$g_1$に対してスタビライズされていることがわかります。ここで、パリティ検査行列の各行の内積はすべて$0$になり、$v_0,v_1$との内積も$0$になることを使いました。$g_5,g_6$についても同様な議論でスタビライズされていることがわかります。

検査行列

次に、生成元の性質をチェックする便利な記法として「検査行列」というものがあるので、その説明をしておきます。

検査行列は、$n$量子ビットのヒルベルト空間におけるスタビライザー群$S= < g_1, \cdots , g_l>$に対応した$l \times 2n$行列です。その第$i$行は生成元$g_i$に対応しており、$g_i$の$j$番目のビットに対応したパウリ演算子が$X$だった場合、第$j$列に1を置き、$Z$だった場合、第$n+j$列に1を置き、$Y$だった場合、第$j$列と第$n+j$列に1を置きます⁹。単位演算子$I$だった場合は0を置きます。これが、検査行列の定義です。

先程のSteane符号の生成元の場合、検査行列は、

\begin{pmatrix}
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
\end{pmatrix}  \tag{18}

となります。左半分は$X$の世界、右半分は$Z$の世界です。Steane符号の場合、左上と右下が全く同じで、かつ、右上と左下が全部ゼロという面白い対称をなしています。

さて、このように生成元を表現することで、なにがどう嬉しくなるのか、これだけではわからないですよね。

実は、「生成元が可換である」ということと、「生成元が独立である」ということが、この検査行列の記法にするとすぐに確認できます。パウリ演算子の積の集合を見せられて、これ可換ですか？独立ですか？と問われても、ぱっと見わからないですが、検査行列をつくってみれば、一目瞭然すぐに判定することができるというわけです。

生成元が可換である条件

以下のような命題として、表現することができます。

【命題１】

$n$量子ビットパウリ群$G_n$の要素$g$を検査行列の記法に従い$2n$次元の行ベクトル$r(g)$で表すことにします。また、$2n \times 2n$行列$\Lambda$を以下のように定義します。

\begin{pmatrix}
0 & I\\
I & 0
\end{pmatrix}  \tag{19}

ここで、$I$は$n \times n$の単位行列、$0$は$n \times n$のゼロ行列を表します。このとき、パウリ群の要素$g,g^{\prime}$が可換である必要十分条件は、

r(g) \Lambda r(g^{\prime})^{T} = 0  \tag{20}

が成り立つことです。

それでは、証明してみます¹⁰。

【証明】

$r(g),r(g^{\prime})$の成分を各々、

\begin{align}
r(g) &= (r_1, \cdots , r_n, r_{n+1}, \cdots , r_{2n}) \\
r(g^{\prime}) &= (r_{1}^{\prime}, \cdots , r_{n}^{\prime}, r_{n+1}^{\prime}, \cdots , r_{2n}^{\prime}) \tag{21}
\end{align}

と書くことにします。そうすると、$g,g^{\prime}$はパウリ演算子を使って、

\begin{align}
g &= a \prod_{i=1}^{n} X_{i}^{r_{i}} Z_{i}^{r_{n+i}} \\
g^{\prime} &= a^{\prime} \prod_{i=1}^{n} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} \tag{22}
\end{align}

のように書けます。ここで、係数$a,a^{\prime}$は、パウリ演算子$Y$が含まれていた場合に$X$と$Z$の積で表してしまうことに付随して発生したりしなかったりする$\pm 1$または$\pm i$です¹¹。

$g$と$g{\prime}$の積をとって、以下のように変形してみます。

\begin{align}
g g^{\prime} &= a a^{\prime} \prod_{i=1}^{n} X_{i}^{r_{i}} Z_{i}^{r_{n+i}} \prod_{i=1}^{n} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} \\
&= a a^{\prime} (X_{1}^{r_1} Z_{1}^{r_{n+1}} \cdots X_{n}^{r_n} Z_{n}^{r_{2n}}) (X_{1}^{r_{1}^{\prime}} Z_{1}^{r_{n+1}^{\prime}} \cdots X_{n}^{r_{n}^{\prime}} Z_{n}^{r_{2n}^{\prime}}) \\
&= a a^{\prime} (X_{1}^{r_1} Z_{1}^{r_{n+1}} \cdot X_{1}^{r_{1}^{\prime}} Z_{1}^{r_{n+1}^{\prime}}) \cdots (X_{n}^{r_{n}} Z_{n}^{r_{2n}} \cdot X_{n}^{r_{n}^{\prime}} Z_{n}^{r_{2n}^{\prime}}) \\
&= a a^{\prime} \prod_{i=1}^{n} X_{i}^{r_{i}} Z_{i}^{r_{n+i}} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} \\
&= a a^{\prime} \prod_{i=1}^{n} (-1)^{r_{n+i} r_{i}^{\prime}} X_{i}^{r_i} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}} Z_{i}^{r_{n+i}^{\prime}} \\
&= a a^{\prime} \prod_{i=1}^{n} (-1)^{r_{n+i} r_{i}^{\prime}} X_{i}^{r_{i}^{\prime}} X_{i}^{r_i} Z_{i}^{r_{n+i}^{\prime}} Z_{i}^{r_{n+i}} \\
&= a a^{\prime} \prod_{i=1}^{n} (-1)^{r_{n+i} r_{i}^{\prime}} (-1)^{r_i r_{n+i}^{\prime}} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} X_{i}^{r_i} Z_{i}^{r_{n+i}} \\
&= a a^{\prime} (-1)^{\sum_{i=1}^{n}{r_{n+i} r_{i}^{\prime} + r_i r_{n+i}^{\prime}}} \prod_{i=1}^{n} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} X_{i}^{r_i} Z_{i}^{r_{n+i}} \\
&= (-1)^{r(g) \Lambda r(g)^{T}} g^{\prime} g  \tag{23}
\end{align}

とできるので、$r(g) \Lambda r(g)^{T} = 0$と$g,g^{\prime}$が可換というのは同値ということになります。（証明終）

生成元が独立である条件

本題に入る前に、意味のある生成元であるための条件について知っておくべき補題がありますので、そっちをまず、やっつけておきます。

【補題１】

パウリ群の部分群（スタビライザー群）$S=< g_1, \cdots , g_l>$において、$-I \notin S$である必要十分条件は、すべての$j$に対して、$g_{j}^{2} = I$、かつ、$g_j \neq -I$が成り立つことです¹²。

ここで、「$-I \notin S$」であるという前提が唐突に出てきたように思われるかもしれませんが、これこそが、意味のある生成元であることを言い表している一つの条件です（後に示すようにこれが唯一の条件というわけではありません）。もし、$-I$が$S$の要素だとすると、これによってスタビライズされる部分空間は、$-I\ket{\psi} = \ket{\psi}$を満たしていないといけないですが、これは$\ket{\psi}=0$を意味しており、意味のある部分空間ではありません。というわけで、「$-I \notin S$」というのは、意味のあるスタビライザーであるための大事な条件（の一つ）です。

さて、それでは、証明してみます。

【証明】

まず、パウリ群の要素$g_i$は、パウリ演算子のテンソル積なので、$g_{i}^{2}$は$+I$か$-I$のどちらかです、ということをおさえておきましょう¹³。

その上で、対偶命題を証明します。$g_{i}^{2}=\pm I$なので、対偶命題は、次のようになります。すなわち、「$g_{i}^{2}=-I$または$g_{i}=-I$となる$i$が存在するということと、$-I \in S$ということは同値」です。

$S$の要素$g$は生成元$\{ g_j \}$を用いて、

g = \prod_{j} (g_j)^{a_j}  \tag{24}

と書けます（$a_j$は$0$以上の整数）。いま、この$g$が$-I$だったとします。$a_j$は2で割ったときの商$n_j=0,1,\cdots$と余り$m_j=\{ 0,1 \}$を用いて、

a_j = 2 n_j + m_j  \tag{25}

とできるので、

g = \prod_{j} (g_j)^{2n_j} (g_j)^{m_j} = -I  \tag{26}

となります。ここで、すべての$j$について、$g_j = I$、かつ、$g_{j}^{2}=I$とすると、式(26)は成り立ちません。$g_i = -I$、または、$g_{i}^{2}= -I$がとなる$i$が存在していないといけません。（証明終）

それでは、本題である「生成元が独立である条件」についてです。以下のような命題として表されますので、これを証明します。

【命題２】

$n$量子ビットパウリ群$G_n$の部分群$S= < g_1, \cdots , g_l>$として、$-I \notin S$であるとします。このとき、生成元$g_1, \cdots , g_l$が独立である必要十分条件は、対応する検査行列の行が線形独立であるということです。

【証明】

対偶命題、すなわち、検査行列の行が線形従属であることと、$g_1, \cdots , g_l$が独立でないことが同値であることを証明します。

$g,g^{\prime} \in S$として、対応する検査行列の行ベクトルを、

\begin{align}
r(g) &= (r_1, \cdots , r_{n}, r_{n+1}, \cdots , r_{2n}) \\
r(g^{\prime}) &= (r_{1}^{\prime}, \cdots , r_{n}^{\prime}, r_{n+1}^{\prime}, \cdots , r_{2n}^{\prime}) \tag{27}
\end{align}

とします。先程と同様に、$g,g^{\prime}$はパウリ演算子を使って、

\begin{align}
g &= a \prod_{i=1}^{n} X_{i}^{r_{i}} Z_{i}^{r_{n+1}} \\
g^{\prime} &= a^{\prime} \prod_{i=1}^{n} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+1}^{\prime}} \tag{28}
\end{align}

のように書けます。そうすると、

\begin{align}
g g^{\prime} &= a a^{\prime} \prod_{i=1}^{n} X_{i}^{r_{i}} Z_{i}^{r_{n+i}} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_{n+i}^{\prime}} \\
&= a a^{\prime} \prod_{i=1}^{n} (-1)^{r_{n+i} r_{i}^{\prime}} X_{i}^{r_i} X_{i}^{r_{i}^{\prime}} Z_{i}^{r_i} Z_{i}^{r_{i}^{\prime}} \\
&= a a^{\prime} (-1)^{\sum_{i=1}^{n} r_{n+i} r_{i}^{\prime}} \prod_{i=1}^{n} X_{i}^{r_{i} + r_{i}^{\prime}} Z_{i}^{r_{n+i} + r_{n+i}^{\prime}} \tag{29}
\end{align}

と変形できます。これを、検査行列の行ベクトル表現で書き直すと、

r(g g^{\prime}) = r(g) + r(g^{\prime}) \tag{30}

です。ここで、左辺と右辺の間には本当は符号（$+1$か$-1$か）があるのですが省略しています（どっちの符号であっても以下の議論は変わらず成り立つので）。

これを延長させると、

r(\prod_{i} (g_i)^{a_i}) = \sum_{i} a_i r(g_i)  \tag{31}

となることもすぐにわかると思います。ここで、$a_i=\{ 0,1 \}$です（先程の補題から）。

$\{ r(g_i) \}$が線形従属ということは、$\sum_{i} a_i r(g_i) = 0$となる$a_j \neq 0$が存在するということです。式(31)があるので、$r(\prod_{i} (g_i)^{a_i}) = 0$となる$a_j \neq 0$が存在すると言っても良いです（ここで、$a_j$は$0$でないとすると必然的に$1$になります）。これは、対応する検査行列の1つの行ベクトルがすべてゼロということですので、$\prod_{i} (g_i)^{a_i} = \pm I, \pm i I$ということと同じことです。が、$-I \notin S$という前提だったので、

\prod_{i} (g_i)^{a_i} = I  \tag{32}

が唯一の選択肢になります¹⁴。

いま、$a_j = 1$とすると、式(32)および先程の補題より$g_{j}^{2}=I$なので、

g_j = g_{j}^{-1} = \prod_{i \neq j} (g_j)^{a_i} \in S  \tag{33}

です。したがって、$g_1, \cdots , g_l$は独立ではありません。（証明終）

有意味なスタビライザー群の条件

ここまでの節で、スタビライザー群、あるいはそれを生成する生成元によって、誤り訂正符号に利用できそうな部分空間を定義できることがわかりました。それから、生成元が可換であることと、独立であることが、検査行列というものを使って理解できることがわかりました。

本記事の締めくくりとして、スタビライザー群が有意味であるための条件について説明します。パウリ群の部分群として、どんなスタビライザー群を持ってきても良いというわけではありません。$-I$という要素がスタビライザーに入っていると、それによってスタビライズされる部分空間は単なる$0$になってしまうのでした。それ以外にも大事な条件があります。それは、生成元が可換であるということです。命題としてまとめます。

【命題３】

スタビライザー群$S$によってスタビライズされる部分空間$V_s$が有意味（0でない）であるならば、
- (a) $S$の要素が可換である。
- (b) $-I$が$S$の要素ではない。
が成り立ちます。

それでは、証明してみます。

【証明】

まず、(a)についてです。

$M,N$をスタビライザー群$S$の任意の2つの要素とします。$M,N$はパウリ演算子のテンソル積なので、互いに可換か反可換です¹⁵。$M,N$が反可換だとします（背理法です）。そうすると、$-MN = NM$となり、

-\ket{\psi} = -MN \ket{\psi} = NM \ket{\psi} = \ket{\psi}  \tag{34}

となり、$\ket{\psi}$はゼロになってしまい、前提を否定することになります。したがって、$M,N$は可換でなければなりません。

次に、(b)についてです。

$-I$が$S$の要素だとします（再び背理法です）。そうすると、

-I \ket{\psi} = \ket{\psi} \tag{35}

となり、$\ket{\psi}$はゼロになってしまい、前提を否定することになります。したがって、$-I$は$S$の要素であってはなりません。（証明終）

これで、$V_s$が有意味であるための必要条件が示せましたので、次に十分条件を示したいのですが、その前に、以下の補題が必要になるので、その証明をしておきます。

【補題２】

$S = < g_1, \cdots , g_l>$は$l$個の独立な生成元により生成され、$-I \notin S$を満たすとします。$i$を$1,2, \cdots , l$のうちのどれかに固定したときに、$g g_{i} g^{\dagger} = -g_{i}$と、$i$以外のすべての$j$に対して$g g_{j} g^{\dagger} = g_{j}$を満たす$g \in G_n$が存在します。

というわけで、何でしょこれ、という感じかもしれません。一読してスッと頭に入ってこないので、ちょっと噛み砕いてみます。$g \in G_n$はユニタリなので、$g g_{i} g^{\dagger}$とか$g g_{j} g^{\dagger}$は各々$g_i,g_j$に対してユニタリ変換していることになります。その結果、元の生成元自身になったり、それにマイナス符号がついたりします。つまり、生成元をプラスの世界とマイナスの世界に分離できるような$g \in G_n$というものが存在している、ということを主張している命題と考えれば良いと思います。

それでは、証明してみます。

【証明】

$g_1, \cdots , g_l$に対応した検査行列を$G$とします（パウリ群ではありません、念の為）。前節で証明した命題により、$G$の行は線形独立なので、

G \Lambda x = e_i  \tag{36}

を満たす$2n$次元のバイナリ・ベクトル$x$が存在します。ここで、$e_i$は$i$番目の成分だけが$1$でそれ以外がすべて$0$である$l$次元のバイナリ・ベクトルです。この$x$を使って、$r(g) = x^{T}$となる$g$を作ります。そうすると、式(36)は、

\begin{align}
r(g_i) \Lambda r(g) &= 1 \\
r(g_j) \Lambda r(g) &= 0 \space (for \space j \neq i) \tag{37}
\end{align}

のように分解できます。前節の式(23)で示したように、2つのパウリ群の要素$g,g^{\prime}$に対して、

g g^{\prime} = (-1)^{r(g) \Lambda r(g)^{T}} g^{\prime} g  \tag{38}

が成り立つので、これに、式(37)を代入すると、

\begin{align}
g_{i} g &= - g g_{i} \\
g_{j} g &= g g_{j} \tag{39}
\end{align}

各々の両辺に右から$g^{\dagger}$を掛けて左右逆にすると、

\begin{align}
g g_{i} g^{\dagger} &= - g_{i} \\
g g_{j} g^{\dagger} &= g_{j} \tag{40}
\end{align}

となります。（証明終）

ちなみに、いまの証明で、式(36)の$e_i$の中に含まれる$1$は1個だけとしましたが、2個以上あるとしても同様の議論が成り立ちます。つまり、この命題で言っている、$g g_{i} g^{\dagger} = - g_{i}$を成り立たせる$i$は複数個あっても良いのだと思います。

さて、それではお待たせしました。有意味なスタビライザーに関する十分条件についてです。独立な生成元の個数と$V_s$の次元の関係も含めて記述している命題があるので、その証明をします。

【命題４】

$S=< g_1, \cdots , g_{n-k}>$は、$G_n$の$n-k$個の独立で可換な要素から生成され、$-I \notin S$とします。このとき、$S$によってスタビライズされる部分空間$V_s$は$2^k$次元のベクトル空間です（つまり有意味）。

【証明】

$x = (x_1, \cdots , x_{n-k})$を$n-k$次元のバイナリ・ベクトルとして、以下の演算子を定義します。

P_{s}^{x} \equiv \frac{\prod_{j=1}^{n-k} (I + (-1)^{x_j} g_j)}{2^{n-k}}  \tag{41}

$(I+g_j)/2$は$g_j$の$+1$の固有空間への射影演算子なので、$x$の成分を全部$0$と置いたものに対する$P_{s}^{x}$を$P_{s}^{00\cdots 0}$とすると、これは$V_s$への射影演算子となります。したがって、$P_{s}^{00\cdots 0}$の次元¹⁶は、$V_s$の次元と同じになります。

この$P_{s}^{x}$を$P_{s}^{00\cdots 0}$をパウリ群の要素$g_x$を使って、以下のように変換してみます。

\begin{align}
g_x P_{s}^{00\cdots 0} (g_x)^{\dagger} &= \frac{1}{2^{n-k}} g_x (\prod_{j=1}^{n-k} (I+g_j)) (g_x)^{\dagger} \\
&= \frac{1}{2^{n-k}} \prod_{j=1}^{n-k} (I + g_x g_j (g_x)^{\dagger}) \tag{42}
\end{align}

先程証明した補題２によると、$g_x$を適当に選ぶことで、ある$j$に対して$g_x g_j (g_x)^{\dagger}=-g_j$、それ以外に対して$g_x g_j (g_x)^{\dagger}=g_j$となるようにできます。これを一言で、

g_x g_j (g_x)^{\dagger} = (-1)^{x_j} g_j \tag{43}

と表現することにすると、式(42)は、

\begin{align}
g_x P_{s}^{00\cdots 0} (g_x)^{\dagger} &= \frac{1}{2^{n-k}} g_x (\prod_{j=1}^{n-k} (I+g_j)) (g_x)^{\dagger} \\
&= \frac{1}{2^{n-k}} \prod_{j=1}^{n-k} (I + (-1)^{x_j} g_j) \\
&= P_{s}^{x}  \tag{44}
\end{align}

となります。$P_{s}^{00\cdots 0}$を$g_x$でユニタリ変換したようなものなので、この$P_{s}^{x}$も$V_s$と同じ次元になります。

さらに、異なる$x$に対して$P_{s}^{x}$は直交しています。なぜなら、

\begin{align}
P_{s}^{x} P_{s}^{x^{\prime}} &= \frac{1}{2^{n-k}} \prod_{j=1}^{n-k} (I + (-1)^{x_j} g_j) (I + (-1)^{x_{j}^{\prime}} g_j) \\
&= \frac{1}{2^{n-k}} \prod_{j=1}^{n-k} (I + ((-1)^{x_j} + (-1)^{x_{j}^{\prime}}) g_{j} + (-1)^{x_{j} + x_{j}^{\prime}} g_{j}^{2}) \\
&= \frac{1}{2^{n-k}} \prod_{j=1}^{n-k} (I + (-1)^{x_{j} + x_{j}^{\prime}} + ((-1)^{x_j} + (-1)^{x_{j}^{\prime}}) g_{j}) \tag{45}
\end{align}

において、$x \neq x^{\prime}$ならば、$x$と$x^{\prime}$の各成分のうち少なくとも一つの成分が異なる値を持ちます。いま、$x_i \neq x_{i}^{\prime}$とします。$\prod$の中の$i$番目だけを前に出すと、

\begin{align}
P_{s}^{x} P_{s}^{x^{\prime}}
&= (I-I+(1-1)g_{i}) \frac{1}{2^{n-k}} \prod_{j=1,j \neq i}^{n-k} (I + (-1)^{x_{j} + x_{j}^{\prime}} + ((-1)^{x_j} + (-1)^{x_{j}^{\prime}}) g_{j}) \\
&= 0 \tag{46}
\end{align}

となるので、$P_{s}^{x}$と$P_{s}^{x^{\prime}}$は確かに直交しています。

また、$2^{n-k}$個のすべての$P_{s}^{x}$の和をとると$I$になります。すなわち、

\sum_{x} P_{s}^{x} = I \tag{47}

です。なぜなら、式(47)の左辺の$\sum$の中の各項は$(I+g_1)/2$か$(I+g_1)/2$どっちかを含んでおり、各項の残りの部分は全く同じなので、$(I+g_1)/2$か$(I+g_1)/2$の足し算、つまり$x_1$に関する足し算を先に実行しても良いです。すなわち、

\begin{align}
\sum_{x} P_{s}^{x} &= \sum_{x_{1}=0,1} \sum_{x_{2}=0,1} \sum_{x_{3}=0,1} \cdots \sum_{x_{n-k}=0,1} \prod_{j=1}^{n-k} \frac{I + (-1)^{x_j}g_j}{2} \\
&= (\frac{I+g_1}{2} + \frac{I-g_1}{2}) \sum_{x_{2}=0,1} \sum_{x_{3}=0,1} \cdots \sum_{x_{n-k}=0,1} \prod_{j=2}^{n-k} \frac{I + (-1)^{x_j}g_j}{2} \\
&= \sum_{x_{2}=0,1} \sum_{x_{3}=0,1} \cdots \sum_{x_{n-k}=0,1} \prod_{j=2}^{n-k} \frac{I + (-1)^{x_j}g_j}{2} \tag{48}
\end{align}

と変形できます。次に式(48)の最後の式で、$x_2$についての足し算を実行して、

\begin{align}
\sum_{x} P_{s}^{x} &= \sum_{x_{3}=0,1} \cdots \sum_{x_{n-k}=0,1} \prod_{j=3}^{n-k} \frac{I + (-1)^{x_j}g_j}{2} \tag{49}
\end{align}

とできます。同じように$x_3, x_4, \cdots$に関する足し算を順に実行すると、最終的に、

\begin{align}
\sum_{x} P_{s}^{x} &= \sum_{x_{n-k}=0,1} \frac{I + (-1)^{x_j}g_j}{2} \\
&= \frac{I+g_{n-k}}{2} + \frac{I-g_{n-k}}{2} \\
&= I  \tag{50}
\end{align}

となり、式(47)が確かに成り立っていることがわかります。

$P_{s}^{x}$が直交していて、式(47)が成り立つことから、$P_{s}^{x}$の次元が見えてきます。全体のヒルベルト空間の次元は$2^n$で、$P_{s}^{x}$の総数は$2^{n-k}$です。各々は直交していて、かつ、全部足すと単位行列になるので、$P_{s}^{x}$の次元は$2^{n}/2^{n-k}$という割り算をすれば良いです¹⁷。したがって、$V_s$の次元は、$2^{k}$です。（証明終）

おわりに

、、ですが、まだ「おわり」ません。スタビライザー「符号」と言っておきながら、まだ「符号化」の話ができていません。次回の記事でやります（あるいはその次かも、、）。それまで、しばらくお待ちください。そして、今回説明したイメージが大事なベースになると思うので、しっかり理解しておくようにしましょう。ポイントを一言で言うと、意味のある部分空間をスタビライズするスタビライザー群というのは、その要素に$-I$が含まれていないことに加え、生成元たちが可換であるということが必要十分な条件です。そして、独立な生成元の個数が$n-k$個だとすると、その部分空間は必然的に$2^k$次元になります、ということです。補題とか命題とか回りくどい説明になったので、あっちこっち振り回された感じがしたかもしれませんが、要するに、そういうことでした。

以上

前回の記事の式(40)を参照。 ↩
「群」の定義は大丈夫でしょうか。ある集合が乗算のもとで群をなすということを、ワンライナーで書くと、「集合が乗算によって閉じていて、結合法則が成り立ち、単位元と逆元がその集合の中に存在する」ということですね。また、群には有限個の要素からなる有限群と無限個の要素からなる無限群があります。式(10)の集合が群（有限群）をなしているということは、簡単にわかると思います。 ↩
いま$X_1 Z_2 I_3$という書き方をしましたが、単位演算子はあまり意味がない（状態に対して何らの作用を及ぼさない）ので、省略して、$X_1 Z_2$と書いたりもします。 ↩
「部分集合」と「部分空間」の違いにご注意。「部分集合」は単なる集合の一部分を取り出したものですが、「部分空間」と言った場合には、要素同士の何らかの演算に関して閉じていることを意味します。例えば、任意の2つの要素の線形和がその部分空間内に存在するということです。 ↩
パウリ$Z$を含む要素に入っている$I_1,I_2,I_3$は省略しています。$I$は$I_1 I_2 I_3$のことだと思ってください。 ↩
任意の2つの要素の積が4つの中のどれかに必ずなっていますし、結合法則もOK、単位元$I$はちゃんと入っていますし、任意の要素の逆元はそれ自身です。 ↩
1個のパウリ演算子の組によってスタビライズされる部分空間の次元は、もとのヒルベルト空間の次元の半分になるのでした。この例の場合、もとのヒルベルト空間は8次元で、2つのスタビライザーによって、半分の半分になるので2次元になります。ということで辻褄が合います。 ↩
ニールセン、チャンの「演習10.32」です。 ↩
$Y$の場合、なぜ2箇所に1を置くのか？$Y$は$X$と$Z$の積に（係数を除き）分解できるので、$Y$が来たらば、そこに$X$と$Z$が同時に存在すると考えます。でも、このように作ると、パウリ演算子の積にくっついている係数（$-1$とか$\pm i$）が反映されないのでは、という疑問もあるかもしれませんが、すぐ後で説明するように、こうしても十分に便利な使い道があるので、係数を無視して作るものだと思っておいてください。 ↩
ちなみに、ここではパウリ群の要素同士が可換であることを証明しますが、生成元はその部分群の要素なので、当然生成元に対しても成り立ちます。ニールセン、チャンの「演習10.33」です。 ↩
$Y=iXZ$にご注意。$Y$の個数分の虚数$i$が存在しているはずですので、その効果を$a,a^{\prime}$として表現しました。もう少し細かいことを言うと、本当はもとのパウリ演算子$g,g^{\prime}$に入っている$X$と$Z$の順番も気にしないといけません（$XZ=-ZX$なので）。が、そもそも検査行列をつくる段階で順番を無視していました。という諸々も含めて、その効果を係数$a,a^{\prime}$に押し込めていると思っていただいて良いです。 ↩
ニールセン、チャンの「演習10.34」です。 ↩
2つのパウリ演算子は、可換か反可換かのどちらかで、かつ、同じ演算子をかけたものは$I$なので、$g_{i}^{2}=\pm I$が言えます。 ↩
もし$-I \in S$だったとすると、スタビライズされる空間は$-I\ket{\psi}=\ket{\psi}$なので$\ket{\psi}=0$ということになります。同様に$\pm iI \in S$だったとしても$\ket{\psi}=0$です。つまり、$S$の中に$-I$が存在しているということと、$S$の中に$\pm i I$が存在しているということは、同じだと考えても良いです。逆に言うと、$-I \notin S$と$\pm i I \notin S$は同値です（ニールセン、チャンの「演習10.30」）。 ↩
異なる量子ビットに関するパウリ演算子同士は可換で、同じ量子ビットに関する異なるパウリ演算子同士は反可換です。また、同じ量子ビットに関する同じパウリ演算子は偶数個集まると$I$になり奇数個だとそれ自身になります。ということを考えてみると、わかると思います。 ↩
次元と言っていますが、これは正味の次元、すなわちランクのことだと思えば良いです。行列でイメージすると、$V_s$の次元と同じ数の$1$が対角成分に配置されていて、それ以外の対角成分や非対角成分すべてが$0$になっている行列です（例えば）。 ↩
このあたり、イメージできますでしょうか。$P_{s}^{x}$は対角成分のいくつかが$1$になっていて、それ以外が全部$0$の$2^{n} \times 2^{n}$行列です、と思うことにしましょう。$P_{s}^{x}$は直交しているので、異なる$x$をもつ$P_{s}^{x}$を2つ並べると、$1$がある場所は全く重なりません（直交とはそういうことです）。そんな行列たちが$2^{n-k}$個あって、全部足したら単位行列になると思ってください。このとき、各$P_{s}^{x}$の対角成分に並んでいる$1$の個数は何個でしょうか？という問題を考えれば良いです。 ↩