量子コンピューターは「速い」のではない

1981年、MITの講演室で

1981年5月、マサチューセッツ工科大学で「計算の物理学」という小さな会議が開かれた。物理学者とコンピュータ科学者が一堂に会するという、当時としては珍しい催しだった。基調講演に立ったのはリチャード・ファインマンリチャード・ファインマン（1918–1988）
アメリカの理論物理学者。量子電磁力学の業績でノーベル物理学賞受賞。型破りな人柄と明快な講義で知られる。。彼はノーベル賞を受けた物理学の巨人であると同時に、ボンゴドラムを叩き、金庫破りを趣味にする愉快な人物でもあった。

ファインマンの問いは明快だった。自然界の量子的な振る舞いを、普通のコンピューターでシミュレーションできるだろうか？　彼の答えは「できない」だった。粒子が50個あるだけで、その状態の組み合わせは2の50乗——約1000兆通りになる。普通のコンピューターでは、メモリが宇宙のサイズでも足りない。

ファインマンの発想はこうだ。自然が量子力学で動いているなら、量子力学で動くコンピューターを作ればいい。この講演が、量子コンピューターという概念の出発点になった。翌1982年に論文として発表され、分野全体の方向を定めた。

リチャード・ファインマン

Richard P. Feynman（1918–1988）

Wikipedia

量子電磁力学の発展に貢献し、1965年にノーベル物理学賞を受賞。ファインマン・ダイアグラムの考案者。物理学の講義は今も教科書として使われ続けている。晩年にチャレンジャー号事故の調査委員としても活躍した。

まず、普通のコンピューターの話をしよう

量子コンピューターを理解するには、まず「普通のコンピューター」が何をしているかを押さえておく必要がある。今あなたが使っているスマートフォンもノートパソコンも、すべてビットビット（bit）
情報の最小単位。0か1のどちらかの値をとる。コンピューターの中では電圧の高低や磁気の方向で表現される。で動いている。ビットとは0か1のどちらかをとるスイッチだ。

ここで量子ビット量子ビット（qubit / キュービット）
量子コンピューターの情報の最小単位。0と1の重ね合わせ状態をとれる。測定すると0か1のどちらかに確定する。の話に入ろう。量子ビットは0と1の重ね合わせ状態をとれる。ただし——ここが決定的に重要だが——測定した瞬間に、0か1のどちらかに確定する。

ここまでで、1つの重要なことが見えてくる。量子ビットが0と1の重ね合わせをとれること自体は、計算速度とは直接関係がない。測定すれば1つの答えしか出ないのだから。

「すべてを同時に試す」——最も広まった誤解

量子コンピューターについて最も広まっている説明は、おそらくこうだ。「量子ビットは0と1の重ね合わせだから、すべての組み合わせを同時に計算できる。だから速い。」　これはほぼ全面的に間違っている。次の体験で、なぜ間違いなのかを確かめてみよう。

干渉——間違いを打ち消す仕組み

量子コンピューターの本当の武器は、重ね合わせではなく干渉干渉（interference）
波が重なり合うこと。山と山が重なると強め合い、山と谷が重なると打ち消し合う。量子コンピューターでは「正しい答え」の確率を強め、「間違った答え」の確率を弱めるために使う。だ。波の干渉と同じ原理で、間違った答えの確率を小さくし、正しい答えの確率を大きくする。

第1段階: 判定装置。量子コンピューターにはOracle（判定装置）Oracle（オラクル / 判定装置）
入力が正解かどうかだけを判定する装置。正解そのものは教えてくれない。テストの答え合わせ機のようなもの——答案を入れると○か✗だけ返してくる。と呼ばれる部品がある。これは「正解かどうかだけを判定する装置」だ。テストの答え合わせ機のようなもの——答案を入れると○か✗だけ返してくる。正解そのものは教えてくれない。この装置は、正解の振幅の符号を反転させる。振幅とは「その答えが測定で出る重み」だ。プラスの振幅をマイナスにひっくり返す。確率としてはプラスと同じに見えるが（確率は振幅の二乗だから）、この「マイナス」が次の段階で決定的な役割を果たす。

第2段階: 増幅。すべての振幅の平均値を計算し、各振幅を平均を軸にして反転させる。するとどうなるか——マイナスだった正解の振幅は大きなプラスに跳ね上がり、プラスのままだった不正解の振幅はわずかに縮む。これが振幅増幅振幅増幅（amplitude amplification）
正しい答えの振幅を大きくし、間違った答えの振幅を小さくする量子操作。グローバーのアルゴリズムの核。だ。判定→増幅を数回繰り返すと、正解の確率がほぼ100%になる。なぜこれが可能かというと、量子の振幅はマイナスになれるからだ。普通の確率は常にプラスなので、打ち消し合うことができない。マイナスの振幅が存在するという性質が、量子コンピューターの力の源だ。

では実際にこのプロセスを動かしてみよう。1996年にロヴ・グローバーロヴ・グローバー
ベル研究所の研究者。1996年に「グローバーのアルゴリズム」を発表。未整理のデータベース検索を平方根のオーダーで高速化できることを示した。が発表したアルゴリズムで見てみよう。

ここで起きていることを整理しよう。量子コンピューターは、すべての答えに均等な確率を配ったあと、「正解の目印をつける」「間違いの確率を減らし正解の確率を増やす」を繰り返す。これが振幅増幅振幅増幅（amplitude amplification）
量子アルゴリズムの基本テクニック。正しい答えの振幅を大きくし、間違った答えの振幅を小さくする操作。と呼ばれる操作だ。

なぜ古典コンピューターでは同じことができないのか

「確率を操作するだけなら、普通のコンピューターでもできるのでは？」　答えはノーだ。古典コンピューターが扱えるのは「確率」だが、量子コンピューターが扱うのは「振幅」——確率の平方根に相当する量で、プラスにもマイナスにもなる。このマイナスの振幅があるから、打ち消し合いが起きる。普通の確率は常にプラスなので、打ち消し合うことができない。

どんな問題に使えるのか

グローバーのアルゴリズムが「探索」を加速するように、量子コンピューターには特定の種類の問題で力を発揮するアルゴリズムが存在する。ここでは代表的な3つの応用分野を紹介する。

たとえば、1000本のルートから最短を探す問題を想像してほしい。古典コンピューターは1本ずつ試す——平均500本調べれば見つかる。量子コンピューターは干渉で絞り込む——約32回で見つかる。これがSearch Raceで体験したグローバーのアルゴリズムの威力だ。候補が100万本になれば、古典は50万回、量子は約1000回。候補が増えるほど差は指数関数的に広がる。

ただし重要な注意がある。量子コンピューターが加速できるのは、問題に「構造」があるときだけだ。素因数分解には周期性という構造がある。分子のエネルギー計算には量子力学的な構造がある。しかし「メールを送る」「表計算をする」といった問題には、干渉で打ち消すべき構造がない。量子コンピューターは万能の加速装置ではない——特定の構造を持つ問題だけに効く、専用の道具だ。

壊れやすさとの戦い

量子コンピューターの内部——「シャンデリア」と呼ばれる希釈冷凍機の配線構造。金色の層が段階的に温度を下げ、最下部の量子チップを絶対零度近くまで冷却する（Photo: Dev Jadiya, CC BY-SA 4.0）

量子コンピューターの原理は美しいが、実際に作ると途方もない困難が待っている。最大の敵がデコヒーレンスデコヒーレンス（decoherence）
量子ビットが環境のノイズで重ね合わせ状態を失うこと。量子計算にとって最大の障害。だ。

IBM Q Systemの希釈冷凍機。この白い円筒の中で量子チップが-273℃近くまで冷却される（パブリックドメイン）

概念から実機へ——40年の軌跡

以下のタイムラインで、は核心に関わる出来事、は関連する出来事を示す。

「速さ」の先にあるもの

量子コンピューターは「すべてを同時に試す」マシンではない。重ね合わせで可能性を広げ、干渉で間違いを打ち消し、正解の確率を集中させる装置だ。

量子コンピューターは万能ではない。しかし特定の問題——素因数分解素因数分解
ある数を素数の積に分けること。大きな数の素因数分解は古典コンピューターにとって極めて困難だが、ショアのアルゴリズムで効率的に解ける。、分子シミュレーション、特定の最適化——においては、古典が何億年かかっても解けない問題を現実的な時間で解ける可能性がある。

ファインマンが1981年に夢見た装置は、40年以上を経てようやく入り口に立っている。量子コンピューターが変えようとしているのは計算の「速度」ではなく、計算の「言語」そのものだ。