STAGE4 128ビットの照合 ― オラクルは比較しない

STAGE 4128ビットの照合

ANDの鎖と逆計算

🎯 ミッション

「全部1なら反転」の巨大な門番を、補助量子ビットとANDの鎖で自分で建てよう。使い終わったメモを逆計算で消す理由を「手がかり」という言葉で説明できれば合格。128ビットの照合コストが2¹²⁸ではなく128に比例することまで言えれば完璧だ。

未達成

ねこ博士

前回の宿題からいこう。実物の量子コンピュータに用意されている基本ゲートは、1量子ビットに働くもの（XやZやHなど）と、2〜3量子ビットに働くもの（CNOTなど）だけだ。「128ビット全部が1なら反転」という門番は、既製品の棚には置いていない。
ただ、これは量子に限った話でもなくてね。古典の錠前でも「128入力のAND」という1個の素子は使わない。2入力のANDを127個つないで作る。y₁とy₂のANDを取り、その結果とy₃のANDを取り……と鎖にするんだ。

うさ美

論理回路の旅でもそうでした。大きな回路は小さなゲートの積み重ねでした。
ということは、量子側でも「2入力ANDに相当するゲート」があれば、同じ鎖が組めるはずですね。でも、量子のゲートで途中の計算結果はどこに書くんですか。古典なら配線の途中に信号が流れるだけですが。

ねこ博士

いい着眼だ。書く場所として、補助量子ビットを追加で用意する。計算用のメモ帳だと思えばいい。最初は全部 |0⟩ にしておく。
そしてメモに書き込むペンが、トフォリゲートだ。CNOTの親戚で、制御ビットが2つある。働きは「制御の2つが両方1のときだけ、標的のビットを裏返す」。
標的をあらかじめ0にしておくと、どうなるか。両方1なら0→1に裏返り、そうでなければ0のまま。つまり標的には y₁ AND y₂ がそのまま書き込まれる。これが量子版の2入力ANDだよ。

うさ美

それなら鎖が組めます。補助ビットを a₁、a₂、……として、
a₁ ＝ y₁ AND y₂
a₂ ＝ a₁ AND y₃
a₃ ＝ a₂ AND y₄
……
a₁₂₇ ＝ y₁ AND y₂ AND … AND y₁₂₈
トフォリを127回。最後のメモ a₁₂₇ が1になるのは、128ビット全部が1のときだけです。

ANDの鎖の設計図。バケツリレーのように、「ここまでの結果」を持ったメモと新しい入力1本のANDを、次のメモに書き込んでいく。1段目のT₁だけは入力2本（y₁とy₂）を受け、2段目からは直前のメモ＋新しい入力の繰り返し。段数は入力の本数で決まるから、128ビットでもトフォリ127個――候補の数2¹²⁸はどこにも登場しない。最後のメモ a₁₂₇ が「全部1か？」の答えを1ビットで持つ。

ねこ博士

そう。そして仕上げは簡単だ。Zゲートという1量子ビットの基本ゲートがあって、働きは「そのビットが1の成分の矢印だけ反対向きにする」。これを a₁₂₇ に1発掛ければ、全部1だった成分にだけ−が付く。STAGE2で「多重制御Z」と呼んだ門番の正体は、このトフォリの鎖＋Z1発の組み立て品だったわけだ。
さて――ここで終わりにして、平均のまわりの折り返しに進みたいところだが、どうかな。

うさ美

……駄目だと思います。デコヒーレンスの旅で習ったことをそのまま当てはめると、補助ビットには手がかりが残っています。
いまの状態を成分ごとに見ると、当たりの成分だけメモが 1、外れの成分はメモが 0。つまりメモを見れば道筋を区別できてしまう。区別のつく道筋どうしは、矢印を足し合わせて打ち消し合うことができない――干渉できないのでした。このまま進むと、あとの「折り返し」が働かなくなりませんか。

ねこ博士

その通り。よく既習の道具で言い当てた。補助ビットに残った計算メモは、環境に漏れた手がかりと同じ働きをして、せっかくの重ね合わせを事実上バラバラにしてしまう。グローバーの折り返しは干渉そのものだから、手がかりが残っていては目印を長さに変えられない。
だから、位相を反転し終わったら、トフォリの鎖を逆順にもう一度掛ける。トフォリは同じ場所に2回掛けると元通りになる性質があるからね（裏返しの裏返しは元通り）。a₁₂₇から順に消していけば、メモは全部 |0⟩ に戻る。これを逆計算と呼ぶ。STAGE2でXを「戻した」のと同じ型――行きの変換を、帰りに逆再生するだ。

うさ美

消してしまって大丈夫なんですね。目印の−は矢印の向きに付いているから、メモを0に戻しても消えない。手がかりだけがなくなって、目印は残る。
全体の手順を数え上げてみます。128ビットの一致判定は、
①Cの0の桁にX（最大128個）
②トフォリの鎖で ANDを積む（127個）
③Zを1発
④鎖を逆再生（127個）
⑤Xを戻す（最大128個）
合計数百ゲート。多いですが、2¹²⁸に比べれば無いも同然です。

ねこ博士

それが正直な勘定だ。2つの俗説を同時に退治できたことになるね。
ひとつ、「オラクルは2¹²⁸個の候補と1個ずつ比較する」――しない。固定回路が線形性で全成分に効く。
ふたつ、「オラクルは基本ゲート1個で瞬時に判定する」――これも違う。数百ゲートぶんの、れっきとした計算だ。ただしその数はビット数に比例するのであって、候補の数2¹²⁸には比例しない。
ここまでで錠前は128ビット版も建った。次は、この錠前をAESの鍵探索という実戦に配置してみよう。

入力: 111111（全部1＝当たりの成分）

128ビットの代わりに6ビットで建てた鎖。「1歩進む」で、トフォリゲートが a₁＝y₁ AND y₂、a₂＝a₁ AND y₃……とメモに書き込んでいく。最後のメモ a₅ が1（＝入力が全部1）ならZが矢印を反転。そのあと鎖を逆順にたどってメモを全部0に戻すと、手がかりは消え、−の目印だけが残る。「y₄を切り替え」で外れの成分にすると、鎖の途中で0が混ざり、Zは働かず、符号は＋のまま――同じ回路が両方の成分を正しくさばく。

【「全部1なら反転」の建て方（nビット）】・道具：トフォリゲート（制御2つが両方1のときだけ標的を裏返す）。標的を |0⟩ にしておけば「AND の書き込み」になる・行き（ANDの鎖）：補助量子ビット（メモ）に a₁＝y₁∧y₂、a₂＝a₁∧y₃、……、a₁₂₇＝y₁∧…∧y₁₂₈ と順に書き込む（∧はANDの記号）・仕上げ：a₁₂₇ に Zゲート（そのビットが1の成分の矢印だけ反転）を1発・帰り（逆計算）：トフォリの鎖を逆順にもう一度掛け、メモを全部 |0⟩ に戻す。メモが残ると手がかりになり、成分どうしが区別できて干渉が壊れるから・目印の−は矢印の向きに付いているので、メモを消しても残る・費用：Xサンド＋トフォリ127×2＋Z1 ＝ 数百ゲート。「基本ゲート1個で瞬時」ではないが、2¹²⁸ にも比例しない。ビット数に比例する

確認クイズ

Q1. 位相を反転したあと、トフォリの鎖を逆順に掛けてメモ（補助ビット）を0に戻すのはなぜ？

Q2. 128ビットの一致判定（オラクルの照合部分）に必要な基本ゲートの数は、おおよそ？

Q3. トフォリゲートで標的ビットに「y₁ AND y₂」を書き込むための準備は？

← 前のステージ