STAGE 5
並列計算の神話
ドイチュのアルゴリズム
🎯 ミッション
「全部の答えを同時に計算するから速い」という説明の、どこが正しくてどこが間違っているのかを見極めよう。ドイチュの問題を1回の質問で解き、速さの正体が干渉の設計であることを説明できれば合格。
未達成
ねこ博士
道具はそろった。今日はいよいよ、量子コンピュータで実際に問題を解く。世界でいちばん小さな量子アルゴリズム――1985年にデイヴィッド・ドイチュが考えた問題だ。
ここに、中身の見えない箱がある。0か1を1個入れると、0か1を1個返してくる。この箱の中の対応づけを f と呼ぼう。f のあり得るパターンは何通りかな。
ここに、中身の見えない箱がある。0か1を1個入れると、0か1を1個返してくる。この箱の中の対応づけを f と呼ぼう。f のあり得るパターンは何通りかな。
うさ美
入力2通りに対して出力が2通りずつなので、4通りです。
①0を入れても1を入れても0を返す ②どちらを入れても1を返す ③入れたものをそのまま返す ④入れたものを逆にして返す。
①0を入れても1を入れても0を返す ②どちらを入れても1を返す ③入れたものをそのまま返す ④入れたものを逆にして返す。
ねこ博士
その4通りを2組に分けよう。①と②は、入力によらず答えが変わらないから定数タイプ。③と④は、0を入れたときと1を入れたときで答えが違うからバランスタイプと呼ぶ。
さて、問題はこうだ。「この箱は定数タイプか、バランスタイプか」だけを知りたい。箱に何回質問すればいいか。箱の中身を分解して覗くのはなしだよ。入力を入れて出力を見る、それだけが許された操作だ。
さて、問題はこうだ。「この箱は定数タイプか、バランスタイプか」だけを知りたい。箱に何回質問すればいいか。箱の中身を分解して覗くのはなしだよ。入力を入れて出力を見る、それだけが許された操作だ。
うさ美
ふつうに考えると2回です。0を入れて答えを見て、1を入れて答えを見る。2つが同じなら定数、違えばバランス。
1回では絶対に無理ですよね。たとえば0を入れて0が返ってきても、それだけでは①（いつも0）なのか③（そのまま返す）なのか決められません。もう片方を試さないと、区別のしようがない。
1回では絶対に無理ですよね。たとえば0を入れて0が返ってきても、それだけでは①（いつも0）なのか③（そのまま返す）なのか決められません。もう片方を試さないと、区別のしようがない。
ねこ博士
きみの理屈は完全に正しい。ふつうのコンピュータでは、どう工夫しても2回必要だ。ところが、量子コンピュータなら1回で済む。（正確に言うと、ドイチュが1985年に示した最初の手順は半分の確率でしか答えが出なくて、確実に1回で済むよう磨き上げられたのは1998年のことなんだ。ここで組むのは、その磨き上げた版だよ。）
うさ美
えっ……でも、1回の質問で得られる情報は1個の答えだけのはずです。0を入れた答えと1を入れた答え、両方を知らないと判定できないのに。
――もしかして、入力を重ね合わせにするんですか？ |0⟩ と |1⟩ が0.71ずつの状態を箱に入れる。そうすれば、箱は両方の入力について同時に計算してくれる。でも、それでも読み出せるのは1つだけですよね。「同時に計算」しても、答えを1つしか取り出せないなら、結局2回測ることになりませんか。
――もしかして、入力を重ね合わせにするんですか？ |0⟩ と |1⟩ が0.71ずつの状態を箱に入れる。そうすれば、箱は両方の入力について同時に計算してくれる。でも、それでも読み出せるのは1つだけですよね。「同時に計算」しても、答えを1つしか取り出せないなら、結局2回測ることになりませんか。
ねこ博士
いま、きみは「量子コンピュータは全部同時に計算するから速い」という有名な説明の、いちばん弱いところを自力で突いた。その説明はここで必ず行き詰まる。同時に計算できても、読み出しは1回1つ。だから並列計算だけでは、1ミリも速くならないんだ。
ドイチュの発明は、この壁を別の角度から破ったところにある。糸口は、きみが最初に言った判定のしかたの中にあるよ――「2つが同じなら定数、違えばバランス」。知りたいのは f(0) の値でも f(1) の値でもなく、その2つが同じかどうかだけなんだ。
ドイチュの発明は、この壁を別の角度から破ったところにある。糸口は、きみが最初に言った判定のしかたの中にあるよ――「2つが同じなら定数、違えばバランス」。知りたいのは f(0) の値でも f(1) の値でもなく、その2つが同じかどうかだけなんだ。
うさ美
……全体についての1個の性質。個々の答えは要らない。読み出しの窓は1つしかないけれど、そこから出てくるのが「f(0) の値」ではなく「f(0) と f(1) が同じかどうか」なら、1回で足りる。
そんな読み出し方が作れるんですか？
そんな読み出し方が作れるんですか？
ねこ博士
作れる。そのために、まず箱を量子ゲートの形に直そう。量子ゲートは可逆でなければならなかったから、箱にも入力を残してもらう。約束はこうだ。量子ビットを2個用意して、1個目に入力 x、2個目に答えを書き込む場所 y を割り当てる。箱は、y のところに「f(x) が1ならひっくり返す、0なら何もしない」という書き込みをする。x はそのまま残る。
この形の箱をオラクルと呼ぶ。「神託を告げる者」という意味で、中身は分からないが質問には答えてくれる、という気持ちの名前だね。
この形の箱をオラクルと呼ぶ。「神託を告げる者」という意味で、中身は分からないが質問には答えてくれる、という気持ちの名前だね。
うさ美
「ひっくり返すか、何もしないか」……それはCNOTと同じ形ですね。制御が「f(x)が1かどうか」に変わっただけだ。
それで、答えを書き込む2個目の量子ビットは、最初どんな状態にしておくんですか。ふつうに考えれば |0⟩ ですけれど。
それで、答えを書き込む2個目の量子ビットは、最初どんな状態にしておくんですか。ふつうに考えれば |0⟩ ですけれど。
ねこ博士
そこが、この手品のいちばん美しい部分だ。2個目を |−⟩ にしておく。前に作ったね――|0⟩ に0.71、|1⟩ に正反対の向きで0.71 の状態だ。|1⟩ に H を当てれば作れる。
この |−⟩ を、箱がひっくり返すとどうなるか、計算してみてほしい。「ひっくり返す」は |0⟩ 行と |1⟩ 行の入れ替えだよ。
この |−⟩ を、箱がひっくり返すとどうなるか、計算してみてほしい。「ひっくり返す」は |0⟩ 行と |1⟩ 行の入れ替えだよ。
うさ美
|−⟩ は「|0⟩ に0.71、|1⟩ に正反対の0.71」。入れ替えると「|0⟩ に正反対の0.71、|1⟩ に0.71」……
あれ、これは元の |−⟩ の矢印を2本ともまとめて反転させたものです。形は |−⟩ のまま！ 状態としては |−⟩ で、ただ全体の向きが正反対になっただけ。
……つまり、箱が2個目に書き込んだはずの答えは、2個目の状態を何も変えていない。代わりに、表全体の向きの反転という形で残った。
あれ、これは元の |−⟩ の矢印を2本ともまとめて反転させたものです。形は |−⟩ のまま！ 状態としては |−⟩ で、ただ全体の向きが正反対になっただけ。
……つまり、箱が2個目に書き込んだはずの答えは、2個目の状態を何も変えていない。代わりに、表全体の向きの反転という形で残った。
ねこ博士
その通り。この現象には名前がついていて、位相キックバックという。「答えが、値としてではなく、矢印の向きとして跳ね返ってくる」という意味だ。整理するとこうなる。
・f(x)＝0 のとき → 何も起きない（向きはそのまま）
・f(x)＝1 のとき → その x の行の矢印が、正反対の向きになる
2個目の量子ビットは最初から最後まで |−⟩ のままで、何の情報も持たない。答えは全部、1個目の表の矢印の向きに書き込まれる。
・f(x)＝0 のとき → 何も起きない（向きはそのまま）
・f(x)＝1 のとき → その x の行の矢印が、正反対の向きになる
2個目の量子ビットは最初から最後まで |−⟩ のままで、何の情報も持たない。答えは全部、1個目の表の矢印の向きに書き込まれる。
うさ美
つながりました！ 1個目を H で重ね合わせ（|+⟩）にしてから箱に通せば、|0⟩ の行と |1⟩ の行が、それぞれ f(0)、f(1) に応じて向きを変える。
そして、向きの違いを長さの違いに変える道具を、私たちはもう持っています。H をもう一度当てればいい。
計算します。箱を通ったあと、1個目の表は「|0⟩ 行が0.71（f(0)が1なら正反対）」「|1⟩ 行が0.71（f(1)が1なら正反対）」。
・定数タイプなら f(0) と f(1) が同じなので、2つの矢印は同じ向き。これは |+⟩（あるいは全体が反転した |+⟩）なので、H を当てると |0⟩ に戻る。測れば必ず0。
・バランスタイプなら2つの矢印は逆向き。これは |−⟩ なので、H を当てると |1⟩ になる。測れば必ず1。
……できました。箱への質問はたった1回。そして出てきた1ビットが、まさに知りたかった「同じか違うか」そのものです！
そして、向きの違いを長さの違いに変える道具を、私たちはもう持っています。H をもう一度当てればいい。
計算します。箱を通ったあと、1個目の表は「|0⟩ 行が0.71（f(0)が1なら正反対）」「|1⟩ 行が0.71（f(1)が1なら正反対）」。
・定数タイプなら f(0) と f(1) が同じなので、2つの矢印は同じ向き。これは |+⟩（あるいは全体が反転した |+⟩）なので、H を当てると |0⟩ に戻る。測れば必ず0。
・バランスタイプなら2つの矢印は逆向き。これは |−⟩ なので、H を当てると |1⟩ になる。測れば必ず1。
……できました。箱への質問はたった1回。そして出てきた1ビットが、まさに知りたかった「同じか違うか」そのものです！
箱の中身を選ぶ
f(0)＝0
f(1)＝0
タイプ 定数
測定結果 必ず 0
上段が1個目の量子ビットの表（|0⟩ 行と |1⟩ 行）の変化。左から順に、①H で五分五分の重ね合わせにする、②箱を1回だけ通す（f(x)が1の行だけ矢印が正反対になる＝位相キックバック）、③もう一度 H を当てる、④測定。4種類の箱を切り替えても、箱を通る回数はつねに1回だけ。それでも、定数タイプ（①②）なら測定結果は必ず0、バランスタイプ（③④）なら必ず1になる。最後の H のところで、いらない答えの矢印が打ち消し合い、欲しい答えの矢印だけが残っているのが読み取れる。
ねこ博士
よく組み上げたね。ではここで、今日いちばん大事な問いに答えてほしい。この手品は、どこが決定的だったのかな。「重ね合わせで同時に計算したから」でいいのか。
うさ美
違いますね。重ね合わせで箱に通しただけの段階では、まだ何も得していません。そこで測ってしまえば、0か1が五分五分で出るだけで、f についてほとんど何も分からない。
決定的だったのは最後の H です。あそこで、f(0) と f(1) が同じ場合には |1⟩ 行の矢印が打ち消し合ってゼロになり、違う場合には |0⟩ 行の矢印が打ち消し合ってゼロになる。いらない答えの側を必ずゼロにするから、残った側を読むだけで確実に判定できる。
……つまり、重ね合わせは材料にすぎなくて、速さを生んだのは干渉のさせ方だったんですね。
決定的だったのは最後の H です。あそこで、f(0) と f(1) が同じ場合には |1⟩ 行の矢印が打ち消し合ってゼロになり、違う場合には |0⟩ 行の矢印が打ち消し合ってゼロになる。いらない答えの側を必ずゼロにするから、残った側を読むだけで確実に判定できる。
……つまり、重ね合わせは材料にすぎなくて、速さを生んだのは干渉のさせ方だったんですね。
ねこ博士
それが今日の結論だ。「量子コンピュータは全部の答えを同時に計算するから速い」――この説明は、前半だけ正しくて後半が抜けている。正しくはこうだよ。
すべての答え候補に矢印を割り当てて計算し、そのあとで、いらない候補の矢印が打ち消し合い、欲しい候補の矢印が強め合うように干渉させる。この後半の設計ができて初めて速くなる。
そして、その設計は問題ごとに人間が発明しなければならない。どんな問題にも効く万能の設計は見つかっていない――ここが、量子コンピュータが「何でも速くする魔法の箱」ではない理由だ。
すべての答え候補に矢印を割り当てて計算し、そのあとで、いらない候補の矢印が打ち消し合い、欲しい候補の矢印が強め合うように干渉させる。この後半の設計ができて初めて速くなる。
そして、その設計は問題ごとに人間が発明しなければならない。どんな問題にも効く万能の設計は見つかっていない――ここが、量子コンピュータが「何でも速くする魔法の箱」ではない理由だ。
うさ美
納得しました。でも正直に言うと、腑に落ちない点があります。手順を書き出してみたんです。素朴な方法は、|0⟩ を箱に通す、測る、X で |1⟩ を作る、箱に通す、測る、測定結果を照らし合わせる、で6手。ドイチュの方法も、X、H、H、箱、H、測る、で6手。合計の手数はほとんど変わらず、浮いたのは箱1回だけです。これで「速くなった」と言えるんでしょうか。
ねこ博士
いい検算だ。その通り、合計はほとんど変わらない。ここで数えているのは合計ではなく、箱への質問の回数だけなんだ。H や X は、装置に電磁波を一瞬当てるだけの安い操作。一方、箱の中身は正体不明で、実際の応用では巨大な計算が丸ごと入っている想定だ。箱1回に1秒かかり、H が10億分の1秒なら、勝負は箱の回数だけで決まる。逆に言えば、箱が H 並みに安いなら、この技は何の得にもならない。ドイチュの問題それ自体は「干渉で得ができる」ことを世界で初めて示した見本であって、実用はない――と言われるのは、そのためでもある。
でも、この形は素直に大きくできる。入力を n ビットに広げて、「箱はすべての入力に同じ答えを返す（定数）か、ちょうど半分ずつ0と1を返す（バランス）か」を判定する問題を考えよう。これはドイチュ＝ジョサの問題と呼ばれている。ふつうのコンピュータで確実に答えるには、最悪の場合 2ⁿ⁻¹＋1回――入力の半分より1つ多く質問しなければならない。n が40なら5000億回を超える。
量子コンピュータなら、まったく同じ骨組みで1回。増える安い操作は H が 2n＋2 個――n に比例してしか増えない。節約される質問は指数で増えるから、1ビットでは箱1回ぶんの得にすぎなかったものが、40ビットでは圧勝に変わる。
でも、この形は素直に大きくできる。入力を n ビットに広げて、「箱はすべての入力に同じ答えを返す（定数）か、ちょうど半分ずつ0と1を返す（バランス）か」を判定する問題を考えよう。これはドイチュ＝ジョサの問題と呼ばれている。ふつうのコンピュータで確実に答えるには、最悪の場合 2ⁿ⁻¹＋1回――入力の半分より1つ多く質問しなければならない。n が40なら5000億回を超える。
量子コンピュータなら、まったく同じ骨組みで1回。増える安い操作は H が 2n＋2 個――n に比例してしか増えない。節約される質問は指数で増えるから、1ビットでは箱1回ぶんの得にすぎなかったものが、40ビットでは圧勝に変わる。
うさ美
5000億回が1回……。それは確かに桁が違います。
骨組みは同じということは、n個の量子ビット全部に H を当てて2ⁿ通りの候補をそろえ、箱を1回通して各候補の矢印に向きを付け、もう一度全部に H を当てて干渉させる、ということですね。定数タイプなら全部の候補が同じ向きだから、干渉の結果すべてが |00…0⟩ に集まる。バランスタイプなら向きが半々なので、|00…0⟩ の行はきれいに打ち消し合ってゼロになる。だから、測って全部0が出たら定数、1が1個でも混じっていたらバランス。
骨組みは同じということは、n個の量子ビット全部に H を当てて2ⁿ通りの候補をそろえ、箱を1回通して各候補の矢印に向きを付け、もう一度全部に H を当てて干渉させる、ということですね。定数タイプなら全部の候補が同じ向きだから、干渉の結果すべてが |00…0⟩ に集まる。バランスタイプなら向きが半々なので、|00…0⟩ の行はきれいに打ち消し合ってゼロになる。だから、測って全部0が出たら定数、1が1個でも混じっていたらバランス。
ねこ博士
まさにその通りに動くよ。
ただし公平を期して言えば、ドイチュ＝ジョサの問題も実用の問題ではないし、「必ず正解する」という条件を緩めてほぼ確実でよいことにすると、ふつうのコンピュータでも数回の質問で済んでしまう。だから、これは「量子が指数的に速い」という主張の完全な証拠ではないんだ。
本物の勝負は次からだよ。次のステージでは、誰もが本当に困っている問題――膨大な選択肢から当たりを探す問題を、干渉の設計で速くする。
ただし公平を期して言えば、ドイチュ＝ジョサの問題も実用の問題ではないし、「必ず正解する」という条件を緩めてほぼ確実でよいことにすると、ふつうのコンピュータでも数回の質問で済んでしまう。だから、これは「量子が指数的に速い」という主張の完全な証拠ではないんだ。
本物の勝負は次からだよ。次のステージでは、誰もが本当に困っている問題――膨大な選択肢から当たりを探す問題を、干渉の設計で速くする。
【ドイチュのアルゴリズム ― 干渉が「全体の性質」を取り出す】
・問題：箱 f が定数タイプ（f(0)＝f(1)）かバランスタイプ（f(0)≠f(1)）かを判定する。ふつうのコンピュータは2回の質問が必要
・道具1 オラクル：可逆にするため、2個目の量子ビットに「f(x)が1ならひっくり返す」形で答えを書き込む
・道具2 位相キックバック：2個目を |−⟩ にしておくと、ひっくり返しても状態は |−⟩ のまま、矢印の向きだけが反転する。答えは値ではなく1個目の表の向きに残る
・手順：1個目に H → 箱を1回通す → 1個目に H → 測定。
定数タイプなら必ず0、バランスタイプなら必ず1 ・速さの正体：重ね合わせ（材料）ではなく、いらない候補の矢印を打ち消し、欲しい候補を残す干渉の設計。この設計は問題ごとに発明が要る ・この勝負で数えるのは箱への質問の回数だけ（H や X は安い操作という前提）。
1ビットでは浮くのは箱1回だけ。箱が安ければ得はない ・n ビットへの拡張＝ドイチュ＝ジョサの問題：ふつうは最悪 2ⁿ⁻¹＋1回、量子なら1回。ただし「ほぼ確実でよい」と条件を緩めるとふつうのコンピュータでも数回で済む
定数タイプなら必ず0、バランスタイプなら必ず1 ・速さの正体：重ね合わせ（材料）ではなく、いらない候補の矢印を打ち消し、欲しい候補を残す干渉の設計。この設計は問題ごとに発明が要る ・この勝負で数えるのは箱への質問の回数だけ（H や X は安い操作という前提）。
1ビットでは浮くのは箱1回だけ。箱が安ければ得はない ・n ビットへの拡張＝ドイチュ＝ジョサの問題：ふつうは最悪 2ⁿ⁻¹＋1回、量子なら1回。ただし「ほぼ確実でよい」と条件を緩めるとふつうのコンピュータでも数回で済む
確認クイズ
Q1. 「量子コンピュータは全部の答えを同時に計算するから速い」という説明の、決定的に抜けている部分は？
正解！ 重ね合わせて計算するところまでは誰でも書けるが、それだけでは測定でランダムに1つ出るだけ。ドイチュのアルゴリズムで決定的だったのは最後のアダマール――そこで、いらない側の矢印が必ずゼロになるよう設計されていた。
Q2. 答えを書き込む2個目の量子ビットを |−⟩ にしておくと何が起きる？（位相キックバック）
正解！ |−⟩ をひっくり返すと、矢印が2本ともまとめて反転した |−⟩ になる――状態の形は同じで、向きだけが変わる。だから答えは2個目には残らず、1個目の表の「向き」として跳ね返る。これがあとで干渉の材料になる。
Q3. ドイチュのアルゴリズムの測定で「1」が出た。分かることは？
正解！ 得られたのは f(0) でも f(1) でもなく、「2つが同じか違うか」という全体についての1個の性質だけ。個々の値は干渉で消えている。読み出し口が1つしかない量子コンピュータで得をするには、こういう「まとめて1個」の問いを設計するしかない。