スタビライザー形式のダイナミクス

量子情報入門　第2章 §2.7

スタビライザー形式の真価は、静的な空間の記述にとどまらず、ゲートと測定のダイナミクスまで演算子の言葉で追えることにある。

ユニタリ発展は生成元の共役

$V_S$ の任意の元 $\ket\psi$ にユニタリ $U$ を施すと、任意の $g\in S$ に対して

$$U\ket\psi = Ug\ket\psi = UgU^\dagger\, U\ket\psi$$

——すなわち $U\ket\psi$ は $UgU^\dagger$ に固定される。よって

これは「状態を止めて演算子を動かす」Heisenberg描像の思想そのものである。$2^n$ 個の振幅を追う代わりに $n$ 個程度の生成元を追えばよい——ただし、共役 $UgU^\dagger$ が再びPauli群に落ちる場合に限り、この圧縮が閉じて機能する。

主要なゲートによるPauli演算子の共役は次の表にまとまる(すべて行列計算で数値検証済み)。

$Y=iXZ$ は $X,Z$ の共役から自動的に決まり($UYU^\dagger = iUXU^\dagger UZU^\dagger$)、積 $g g'$ の共役も因子ごとの共役の積でよいから、この表だけで任意のClifford回路のPauli追跡ができる。CNOTの行は物理的にも雄弁である:「$X$(ビット値)は制御から標的へ伝播し、$Z$(位相)は標的から制御へ逆流する」。前者はCNOTの定義通りだが、後者は見落としやすく、フォールトトレラント設計(次章)で誤り伝播を数える際の急所になる。

例:SWAP回路

CNOTを3つ互い違いに並べた回路がSWAPを実装することは、状態を追わずとも生成元追跡で見える:$Z_1$ は3つのCNOTを通って $Z_1\to Z_1\to Z_1Z_2\to Z_2$、同様に $Z_2\to Z_1$、$X_1\to X_2$、$X_2\to X_1$。$Z_1,Z_2,X_1,X_2$ の行き先が決まれば2量子ビットユニタリは(全体位相を除き)一意に決まるので、これはSWAPである。

例:$\ket0^{\otimes n}$ へのHadamard

$\ket0^{\otimes n}$ のスタビライザーは $\langle Z_1,\ldots,Z_n\rangle$。全ビットに $H$ をかけると生成元は $\langle X_1,\ldots,X_n\rangle$ になり、これは一様重ね合わせ $\frac{1}{2^{n/2}}\sum_x\ket x$ のスタビライザーである。状態ベクトルなら $2^n$ 個の振幅が要るところ、生成元表示は $n$ 個で済む——線形 vs 指数の圧縮である。

Clifford群と、その外側

$UG_nU^\dagger=G_n$ を満たす $U$ の全体を $G_n$ の正規化群 $N(G_n)$ と呼ぶ(Clifford群とも)。上の表が示すとおり $H,S,\mathrm{CNOT}$ は $N(G_n)$ の元であり、実は逆も成り立つ:

すなわち「スタビライザー形式で追えるゲート」の全体が、ちょうど $\{H,S,\mathrm{CNOT}\}$ の生成する群である。第2章で「$\{H,S,\mathrm{CNOT}\}$ は普遍にならない」と述べた理由がここで正体を現す:この集合はPauli群という離散的な骨組みを保つ変換しか作れないのである。

では骨組みを壊すゲートはどうなるか。$T$($\pi/8$ ゲート)とToffoliの共役を計算すると

$$TZT^\dagger = Z,\qquad TXT^\dagger = \frac{X+Y}{\sqrt2},$$

$$\mathrm{Toffoli}:\ X_1 \mapsto X_1\otimes\frac{I+Z_2+X_3-Z_2X_3}{2}\quad\text{など}$$

(いずれも数値検証済み)。出力がPauli演算子の線形結合になってしまい、$G_n$ の中に収まらない。生成元追跡の圧縮はここで破綻し、追うべき項の数が指数的に増殖しうる。「$T$ ゲート1個の追加が、古典で追える世界から追えない世界への相転移を引き起こす」——この構図は次小節のGottesman–Knill定理、そしてフォールトトレラント計算における $T$ ゲートの特別扱い(魔法状態)の伏線である。

Pauli測定のスタビライザー記述

計算基底での測定を含む、Pauli群の元 $g$(係数 $\pm1,\pm i$ なしとする;$g$ はHermiteなので観測量)の測定もスタビライザーで追える。状態のスタビライザーを $\langle g_1,\ldots,g_n\rangle$ とすると、場合は2つに分かれる。

ケース1:$g$ が全生成元と可換。このとき $g\ket\psi$ も $V_S$ に属するので $\ket\psi$ の定数倍であり、$g^2=I$ から $g\ket\psi=\pm\ket\psi$、すなわち $g$ か $-g$ が既に $S$ に入っている。測定結果は対応する符号で確定し、状態もスタビライザーも変化しない。

ケース2:$g$ がある生成元と反可換。生成元を組み替えて($g_1$ と反可換、$g_2,\ldots,g_n$ とは可換、としてよい:もし $g_2$ とも反可換なら $g_2$ を $g_1g_2$ で置き換えれば可換になる)、測定確率を計算する。結果 $\pm1$ の射影子は $(I\pm g)/2$ で、

$$p(+1) = \mathrm{tr}\Bigl(\frac{I+g}{2}\ket{\psi}\!\bra{\psi}\Bigr) = \mathrm{tr}\Bigl(\frac{I+g}{2}\,g_1\ket{\psi}\!\bra{\psi}\Bigr) = \mathrm{tr}\Bigl(g_1\frac{I-g}{2}\ket{\psi}\!\bra{\psi}\Bigr) = p(-1)$$

($g_1\ket\psi=\ket\psi$ を挿入し、$gg_1=-g_1g$ で $g_1$ を通過させ、トレースの巡回性と $g_1^\dagger=g_1$ で吸収した)。よって

状態ベクトルの射影と規格化という煩雑な計算が、「生成元リストの1行書き換え」に置き換わった。症候測定(スタビライザー生成元の測定)はケース1・2の使い分けそのものであり、誤りが起きていなければケース1(結果 $+1$ 確定・状態不変)、誤りが生成元と反可換ならケース2的に符号が反転して検出される——第10章の3量子ビット符号の議論が、この一般論の特別な場合であったことがわかる。

Gottesman–Knill定理

以上を総合すると、驚くべき定理がすでに証明されていることに気づく。

シミュレーションの方法は本章で構築した機構そのものである:古典計算機は $n$ 個の生成元(各 $2n$ ビット+符号)を保持し、ゲートごとに共役表で生成元を更新し($O(n)$ 程度)、測定は可換性判定と生成元の置き換えで処理する(検査行列を使えば $O(n^2)$)。$m$ 個の演算からなる回路全体で $O(n^2m)$——多項式時間である。

この定理の含意は深い。テレポーテーションも超高密度符号化も、高度にもつれた状態を作るスタビライザー回路も、すべて古典で効率的に真似できる。もつれの存在それ自体は量子計算の優位性の説明にならないのである。量子的優位性には、Pauli群の骨組みを壊すゲート($T$、Toffoli)が本質的に必要になる。幸いにも、量子誤り訂正符号の符号化・症候測定・回復はすべてClifford演算だけで書ける——スタビライザー形式が誤り訂正の解析にこれほど適している理由である。