授業で習った形との対応：古典の誤り訂正と計算量

相対エントロピーから情報と物理を組み立てる　第6部 第5章 §6.5.6　★★ 古典の符号の失敗確率の式、von Neumann の多数決回路のしきい値、計算量のクラス BQP と並べ、量子のしきい値定理が何を新しく言っているかを確かめる

古典の符号の失敗確率

情報理論や符号理論の授業では、長さ $n$・最小距離 $d$ の符号が $t=\lfloor(d-1)/2\rfloor$ 個までの誤りを直し、各ビットが独立に確率 $\varepsilon$ で反転する通信路でのブロックの失敗確率が

$$P_{\mathrm{fail}}\le\sum_{j=t+1}^{n}\binom{n}{j}\varepsilon ^j(1-\varepsilon )^{n-j}\approx\binom{n}{t+1}\varepsilon ^{t+1}\tag{6.5.9}$$

となることを習う。表面符号の $\varepsilon _{\mathrm L}\propto\varepsilon ^{(d+1)/2}$ は $t+1=(d+1)/2$ の場合のこの式と同じ次数で、量子の符号でも、失敗の確率は「直せる個数を1つ超えた誤りが同時に起こる確率」で決まる。違いは2つある。1つは、量子の符号では $X$ と $Z$ の両方を直す必要があり、シンドロームが誤りそのものでなく誤りの類しか教えないこと（縮退）である。もう1つは、式 (6.5.9) が復号を誤りなく行えるという前提に立つのに対し、しきい値定理は復号の回路そのものが誤ることまで含めて勘定していることである。第1部第6章の Shannon の通信路符号化定理も、符号化と復号は誤らないとして、容量より小さい率なら失敗の確率をいくらでも下げられることを述べていた。

von Neumann の多数決回路

部品が誤る回路で正しく計算する問題は、量子の前に von Neumann が古典の論理回路で考えた¹1J. von Neumann (1956), in Automata Studies, ed. C. E. Shannon and J. McCarthy (Princeton University Press), 43–98。下の脚注へ閉じる。1本の信号線を3本に増やし、3本の多数決を取る素子で誤りを戻す。多数決の素子そのものが確率 $\eta$ で出力を反転させるとすると、多数決の前の各線の誤りの確率 $x$ は、多数決の後に

$$f(x)=\eta+(1-2\eta)(3x^2-2x^3)\tag{6.5.10}$$

に変わる（多数決の結果が誤る確率 $3x^2-2x^3$ に、素子の反転を合わせた）。これを繰り返したときの行き先は $f$ の不動点で決まる。$f(x)-x$ は

$$f(x)-x=-2(1-2\eta)\Bigl(x-\frac12\Bigr)\Bigl(x^2-x+\frac{\eta}{1-2\eta}\Bigr)\tag{6.5.11}$$

と因数分解でき、$x=1/2$ のほかの不動点 $x_\pm=\frac12\bigl(1\pm\sqrt{1-4\eta/(1-2\eta)}\bigr)$ は $\eta\le1/6$ のときだけ実数になる。$\eta<1/6$ なら $x_-$ が安定で、誤りの確率は $\eta$ と同じ程度の値 $x_-$ に留まり、$1/2$（情報が消えた状態）へは流れない。$\eta>1/6$ なら $x=1/2$ だけが安定で、何段重ねても情報は消える。この $\eta=1/6$ が3入力の多数決による回路のしきい値にあたる。

量子のしきい値定理との違いは、誤りが $\eta$ の程度に留まるだけで $0$ には行かないことである。素子1つの誤り $\eta$ は毎段の終わりに必ず加わるので、それ以下にはならない。連結符号では、誤り訂正のガジェットそのものを1段下の論理ゲートで作るので、各段の誤り訂正の誤りも $\varepsilon ^{(\ell-1)}$ の大きさに下がり、$\varepsilon ^{(\ell)}=A(\varepsilon ^{(\ell-1)})^2$ で $0$ へ向かう。古典の計算機は、部品の誤りが極めて小さく、信号を毎回 $0$ と $1$ にそろえ直す（デジタルにする）だけで足りるのでこの構成を使っていないが、量子の部品は誤りが $10^{-3}$ 程度と大きく、連結か表面符号が欠かせない。

計算量のクラス BQP

計算量の授業では、多項式時間の決定的なアルゴリズムで解ける問題のクラス P と、確率的なアルゴリズムで誤りの確率 $1/3$ 以下で解けるクラス BPP を習う。量子の版が BQP で、入力の長さの多項式個のゲートの量子回路で、誤りの確率 $1/3$ 以下で答えを出せる問題のクラスである。BPP $\subseteq$ BQP であり、BQP は PSPACE（多項式の記憶領域で解ける問題）に含まれ²2E. Bernstein and U. Vazirani (1997), SIAM J. Comput. 26, 1411。下の脚注へ閉じる、さらに PP に含まれる³3L. M. Adleman, J. DeMarrais and M.-D. A. Huang (1997), SIAM J. Comput. 26, 1524。下の脚注へ閉じる。素因数分解は BQP に入り（第6部第3章）、古典の多項式時間のアルゴリズムは知られていない。NP 完全問題が BQP に入るとは考えられておらず、第6部第4章の探索の下界 $\Omega(\sqrt N)$ はその根拠の1つである。

BQP の定義は誤りのないゲートを前提にしている。しきい値定理は、部品の誤りがしきい値より小さければ、雑音のある物理的な装置で BQP の回路を対数の多項式倍の手間で実行できることを保証し、BQP を物理的に意味のあるクラスにしている。誤り訂正なしの雑音のある装置で古典の計算機より速く解ける問題を示す実験（量子優位の実験）もあり、53量子ビットの超伝導チップでのランダムな回路の出力の標本化が最初の例として報告された⁴4F. Arute et al. (2019), Nature 574, 505。下の脚注へ閉じるが、これは役に立つ問題を解いたものではなく、古典の計算機の側の模倣の方法の改良とともに比較の評価が動いている。誤りの無い論理量子ビットで Shor のアルゴリズムのような BQP の問題を解くには、しきい値定理に従う誤り耐性の計算が要る。