しきい値定理

量子情報入門　第2章 §2.10

部品が揃った。仕上げは「フォールトトレラント化で誤りが本当に減るのか」の勘定である。

誤りの勘定:$p\to cp^2$

フォールトトレラントCNOT+症候測定+回復、という1サイクルを考える。設計により、1個の故障は各ブロック高々1個の誤りしか生まず、それは次の誤り訂正で消される。出力ブロックに2個以上の誤り(=訂正不能)が残るには2個以上の独立な故障が必要であり、その確率は

$$\Pr[\text{論理誤り}] \le cp^2$$

と押さえられる。定数 $c$ は「故障ペアが起こりうる場所の数」で、Steane符号の構成を数え上げると、症候測定(生成元6個×各10箇所程度)+回復(7箇所)で1ステージ約70箇所、そのペアの組合せなどを合算して $c\approx10^4$ 程度と見積もられる。$p<1/c\approx10^{-4}$ なら $cp^2<p$——符号化する方が素の物理ビットより確実になる損益分岐点である。

連結符号としきい値定理

$p\to cp^2$ の改善は再帰的に適用できる。物理ビットを符号化し、その論理ビットをさらに符号化し……と $k$ 階層連結(concatenate)すると、最上位の実効故障確率は

$$cp^2\ \to\ c(cp^2)^2\ \to\ \cdots\ \to\ \frac{(cp)^{2^k}}{c}$$

と二重指数的に潰れていく。一方、回路サイズは1階層あたり定数倍 $d$ なので $d^k$ 倍にしかならない。サイズ $p(n)$ の回路を最終精度 $\epsilon$ で走らせるには各ゲートを $\epsilon/p(n)$ の精度にすればよく、$(cp)^{2^k}/c\le\epsilon/p(n)$ を解くと必要階層数から

$$d^k = O\Bigl(\mathrm{poly}\bigl(\log(p(n)/\epsilon)\bigr)\Bigr)$$

——オーバーヘッドは多項式対数にとどまる。まとめると:

粗い勘定では $p_{\mathrm{th}}\approx10^{-4}$、より精密な解析では $10^{-5}$–$10^{-6}$ 程度とされる(しきい値は雑音モデルと構成の仮定に強く依存し、より新しい符号・解析では大幅に改善されている)。「適切な仮定」も明示しておく価値がある:(i) 並列性——誤り訂正を全ブロックで同時に回せなければ、誤りの蓄積に追い抜かれる;(ii) 古典計算・通信——症候の処理と回復の指示は古典側の仕事で、誤りの時間スケールより速く済ませる必要がある;(iii) 新鮮な補助ビットの定常供給——猫状態や魔法状態の材料となる低エントロピーな $\ket0$ を絶えず補給できること(エントロピーを系外へ汲み出すポンプの役割)。

この定理の意義は、どれほど強調してもしすぎることはない。雑音は量子計算に対する原理的障害ではない。ハードウェアの精度がしきい値を超えさえすれば、物理法則のいかなる原理も、任意に大規模で長時間の量子計算の実現を妨げない——量子誤り訂正の理論が到達した、最も力強い結論である。