量子コンピュータと古典コンピュータの継続的な戦い

量子コンピューティングの可能性と限界はハードウェアに由来する、という誤解がよくあります。デジタル時代において、私たちはクロック速度とメモリの進歩を実感することに慣れきっています。同様に、IntelやIBMといった企業が現在開発を進めている50量子ビットの量子コンピューターは、「量子超越性」に近づいているという予測を促しています。量子超越性とは、量子コンピューターが従来のコンピューターの能力を超えることを可能にする、漠然としたフロンティアです。

しかし、量子超越性は、目指すべき単一の圧倒的勝利、つまり越えるべき大きなルビコン川のようなものではなく、むしろ長期にわたる小さな決闘の連続です。量子アルゴリズムと古典アルゴリズムの対決という、問題ごとに確立されるでしょう。「量子コンピューターの進歩は、速度だけではありません」と、シドニー工科大学の量子理論家マイケル・ブレムナー氏は述べています。「重要なのは、そこで使われるアルゴリズムの複雑さです。」

逆説的に、強力な量子計算に関する報告は、古典的計算の改良を促し、量子マシンが優位に立つことを困難にしている。「量子コンピューティングについて語る時、古典的計算は全盛期を過ぎたかのように軽視されることが多い」と、ニュージーランドのオークランド大学の数学者でコンピューター科学者のクリスチャン・カルーデ氏は述べた。「しかし、そうではありません。これは現在も続く競争なのです。」

そして、目標は変化しつつある。「超越性の閾値がどこにあるかは、最良の古典的アルゴリズムがどれだけ優れているかによって決まる」と、カリフォルニア工科大学の理論物理学者ジョン・プレスキル氏は述べた。「それらのアルゴリズムが改良されるにつれて、その境界を押し広げていかなければならない」

「そんなに簡単そうには見えない」

1980年代に量子コンピュータの夢が具体化する以前、ほとんどのコンピュータ科学者は、古典的コンピュータだけが全てであると当然のこととして考えていました。この分野の先駆者たちは、チューリングマシンと呼ばれる数学的抽象概念に代表される古典的コンピュータは、基本的な算術から株式取引、ブラックホールの衝突に至るまで、物理宇宙で計算可能なあらゆるものを計算できるはずだと説得力のある主張をしていました。

しかし、古典的な機械は必ずしもこれらの計算を効率的に実行できるわけではありません。例えば、分子の化学的挙動のようなものを理解したいとしましょう。この挙動は、分子内の電子の挙動に依存しており、電子は多くの古典的な状態の重ね合わせ状態にあります。さらに複雑なことに、各電子の量子状態は、他のすべての電子の状態に依存しています。これは、量子力学の「エンタングルメント」と呼ばれる現象によるものです。非常に単純な分子であっても、これらのエンタングルメント状態を古典的な方法で計算することは、指数関数的に複雑さが増大する悪夢となる可能性があります。

対照的に、量子コンピュータは、自身の量子ビットを重ね合わせ、絡み合わせることで、研究対象の電子の複雑な運命を扱うことができます。これにより、コンピュータは膨大な量の情報を処理できます。1つの量子ビットを追加するごとに、システムが同時に保存できる状態は2倍になります。2つの量子ビットで4つの状態、3つの量子ビットで8つの状態を保存できます。つまり、符号化に指数関数的に膨大な数の古典ビット（正確には1兆12500兆ビット）を必要とする量子状態を、わずか50個の絡み合った量子ビットでモデル化できる可能性があります。

したがって、量子マシンは、大規模な量子力学システムのシミュレーションという、古典的には扱いにくい問題を扱いやすくすることができる、少なくともそう見えた。「自然は古典的ではない、ちくしょう。自然のシミュレーションを作りたいなら、量子力学的に作った方がいい」と、物理学者リチャード・ファインマンは1981年に有名な言葉を残した。「そして、実に素晴らしい問題だ。それほど簡単には見えないのだから。」

もちろんそうではありませんでした。

量子ハードウェアをいじり始める以前から、理論家たちは適切なソフトウェアの開発に苦労していました。初期に、ファインマンとオックスフォード大学の物理学者デイヴィッド・ドイッチは、線形代数から借用した数学的演算、いわゆる「ゲート」を用いて量子情報を制御できることを発見しました。古典的な論理ゲートの類似物として、量子ゲートは量子ビットを様々な方法で操作します。量子ビットを一連の重ね合わせ状態やエンタングルメント状態に導き、その出力を測定します。ゲートを組み合わせて回路を構成することで、理論家たちは容易に量子アルゴリズムを組み立てることができました。

明確な計算上の利点を約束するアルゴリズムを考案することは、より困難であることが判明した。2000年代初頭までに、数学者たちが思いついた有力な候補はごくわずかだった。最も有名なのは、1994年にベル研究所の若手研究員ピーター・ショアが、既存のどの古典的アルゴリズムよりも指数関数的に高速に整数を因数分解する量子アルゴリズムを提案したことだ。この効率性は、多くの一般的な暗号方式を解読できる可能性を秘めていた。2年後、ショアのベル研究所での同僚、ラブ・グローバーは、ソートされていないデータベースを検索するという、古典的で退屈な処理を高速化するアルゴリズムを考案した。「量子コンピューティングの能力が古典的コンピューティングの能力を上回るはずであることを示唆する様々な例がありました」と、ケンブリッジ大学の量子情報科学者リチャード・ジョザは述べた。

しかし、ジョザ氏は他の研究者とともに、全く逆のことを示唆する様々な例も発見した。「多くの美しい量子プロセスは複雑であるように見える」ため、古典的コンピュータではシミュレーションが難しいことが判明したとジョザ氏は述べた。「しかし、巧妙で繊細な数学的手法を用いれば、それらが何をするのかを解明できるのです」。彼と同僚たちは、これらの手法を用いることで、驚くほど多くの量子回路を効率的にシミュレーション（カルデ氏の言葉を借りれば「脱量子化」）できることを発見した。例えば、エンタングルメントを省略した回路や、限られた数の量子ビットだけをエンタングルメントする回路、あるいは特定の種類のエンタングルメントゲートだけを用いる回路は、この罠に陥る。

では、ショア氏のようなアルゴリズムが他に類を見ないほど強力であることを保証するものは何なのでしょうか？「それは全く未解決の問題です」とジョザ氏は言います。「なぜ一部のアルゴリズムは古典的に容易にシミュレートできて、他のアルゴリズムはそうでないのか、私たちはまだ完全に理解できていません。エンタングルメントが重要なのは明らかですが、それですべてが終わるわけではありません。」専門家たちは、自分たちが優れていると信じていた量子アルゴリズムの多くが、実はありきたりなものである可能性を疑い始めました。

サンプリングの闘い

最近まで、量子パワーの追求は主に抽象的なものでした。「私たちはアルゴリズムの実装にはあまり関心がありませんでした。なぜなら、近い将来に量子コンピュータが登場するとは誰も信じていなかったからです」とジョザ氏は言います。例えば、標準的な128ビット暗号鍵を解読できるほど大きな整数に対してショアのアルゴリズムを実行するには、数千個の量子ビットが必要で、さらにエラー訂正のためにおそらく数千個もの量子ビットが必要になるでしょう。一方、実験者たちは、ほんの一握り以上の量子ビットを制御しようと手探りで取り組んでいました。

しかし2011年になると、事態は好転し始めた。その秋、ブリュッセルで開催された会議で、プレスキル氏は「適切に制御された量子システムが古典世界で可能な範囲を超えるタスクを実行できる日」はそう遠くないかもしれないと推測した。彼によると、最近の実験結果から、まもなく100量子ビット規模の量子マシンが実現する可能性があるという。これらのマシンで「超古典的」な偉業を成し遂げることは、不可能ではないかもしれない。（D-Wave Systemsの商用量子プロセッサは当時128量子ビットを処理でき、現在では2000量子ビット以上を誇っているが、それらは特定の最適化問題しか扱えない。多くの専門家は、それらが古典的コンピュータを上回る性能を発揮できるかどうか疑問視している。）

「私はただ、量子技術が人類文明における最も強力な情報技術となるという、人類文明における真のマイルストーンについに到達するかもしれないということを強調したかったのです」とプレスキル氏は述べた。彼はこのマイルストーンを「量子超越性」と呼んだ。その名称と楽観的な見方は定着した。「予想もしなかったほどの勢いで広まったのです」

量子超越性に関する話題は、この分野における興奮の高まりを反映していた。実験の進歩はもちろんのこと、IBMの物理学者バーバラ・ターハルとデイビッド・ディヴィンチェンツォによる2004年の論文に端を発する一連の理論的ブレークスルーに対する期待の方が大きかったかもしれない。量子資産の理解を目指す中で、二人はサンプリング問題と呼ばれる初歩的な量子パズルに着目した。やがて、この種の問題は、初期の量子マシンにおける明確な高速化を実証するための、実験家にとって最大の希望となる。

サンプリング問題は、量子情報の捉えどころのない性質を利用します。例えば、100個の量子ビットにゲートシーケンスを適用するとします。この回路は、量子ビットを2の^100乗の古典ビットに相当する数学的に巨大なものへと変化させるかもしれません。しかし、システムを測定すると、その複雑さはわずか100ビットの文字列にまで縮小されます。システムは、回路によって決定される確率で、特定の文字列（つまりサンプル）を吐き出します。

サンプリング問題では、この回路から出力されたように見える一連のサンプルを生成することが目標です。これは、コインを繰り返し投げて、（平均して）表と裏がそれぞれ50%ずつ出ることを示すようなものです。ただし、ここでは、各「投げ」の結果は単一の値（表か裏か）ではなく、複数の値の列であり、それぞれの値は他の値の一部（あるいはすべて）の影響を受ける可能性があります。

十分に機能する量子コンピュータにとって、この作業は考えるまでもなく簡単です。それが自然な動作なのです。一方、従来のコンピュータはより困難な状況に置かれているようです。最悪の状況では、あらゆる出力文字列（2の¹⁰⁰乗通り）の確率を計算し、その分布からランダムにサンプルを選択するという、扱いにくい作業をしなければならないのです。「人々は常にこれが当てはまると推測していました」と、特に非常に複雑な量子回路の場合に当てはまると、ブリストル大学の量子アルゴリズムの専門家であるアシュリー・モンタナロ氏は述べています。

テルハルとディヴィンチェンツォは、単純な量子回路でさえ、古典的な方法ではサンプリングが困難であることを示した。こうして、ハードルが設定された。もし実験者が量子システムを使ってこれらのサンプルを吐き出すことができれば、彼らは古典的な方法では比較できない何かを達成したと信じるに足る十分な理由を持つことになるだろう。

理論家たちはすぐにこの考え方を拡張し、他の種類のサンプリング問題も対象に含めました。最も有望な提案の一つは、当時マサチューセッツ工科大学に在籍していたコンピューター科学者スコット・アーロンソンと、彼の博士課程の学生アレックス・アルキポフによるものでした。2010年に科学論文プレプリントサイトarxiv.orgに掲載された論文で、彼らは光子を光回路に送り込み、量子力学的に光をシフト・分割することで、特定の確率で出力パターンを生成する量子マシンについて説明しました。これらのパターンを再現する手法は、後にボソンサンプリングとして知られるようになりました。アーロンソンとアルキポフは、ボソンサンプリングは30光子程度で古典的なリソースに負担をかけ始めると推論しました。これは妥当な実験目標値でした。

同様に魅力的だったのが、瞬間量子多項式（IQP）回路と呼ばれる計算だった。IQP回路はゲートがすべて可換である、つまり、2 + 5 = 5 + 2のように、結果を変えることなく任意の順序で動作できる。この特性により、IQP回路は数学的に魅力的だ。「解析が容易だったので研究を始めました」とブレムナー氏は語った。しかし、彼はIQP回路には他にもメリットがあることを発見した。2010年に始まり、現在英国国立サイバーセキュリティセンターに所属するモンタナロ氏とダン・シェパード氏と共同で2016年に発表した論文で、ブレムナー氏はIQP回路が非常に強力になり得る理由を説明した。数百、あるいは数十の量子ビットからなる物理的に現実的なシステムであっても、サンプリングはすぐに古典的に厄介な問題になるだろう。

2016年時点では、ボソンサンプラーはまだ6光子を超えるには至っていませんでした。しかし、GoogleとIBMのチームは50量子ビットに近いチップの開発に着手していました。同年8月、Googleはこれらの「近い将来」のデバイスで量子超越性を実証するためのロードマップを示す草稿論文をひっそりと公開しました。

Google のチームは、IQP 回路からのサンプリングを検討していました。しかし、ブレムナー氏と共同研究者による詳細な調査の結果、この回路では、最良の古典的アルゴリズムを完全に無効化するためには、追加のゲートと少なくとも数百の量子ビットが必要となるエラー訂正が必要になる可能性が高いことが示されました。そこでチームは代わりに、アーロンソン氏とブレムナー氏に類似した議論を用いて、非可換ゲートで構成された回路は、IQP 回路よりも構築と解析が難しい可能性が高いものの、古典的デバイスによるシミュレーションも困難であることを示しました。古典的計算をさらに困難にするために、チームはランダムに選択された回路からのサンプリングを提案しました。こうすることで、古典的な競合相手は、回路構造のよく知られた特徴を利用してその動作をより正確に推測することができなくなります。

しかし、古典的アルゴリズムのリソース活用を阻むものは何もありませんでした。実際、2017年10月、IBMのチームは、少しの古典的工夫を加えることで、スーパーコンピューターが最大56量子ビットのランダム回路からのサンプリングをシミュレートできることを示しました。ただし、回路の深さ（ゲート層数）があまり深くないことが条件です。同様に、より高性能なアルゴリズムが最近、ボソンサンプリングの古典的限界を約50光子まで押し上げました。

しかし、これらのアップグレードは依然として恐ろしく非効率です。例えば、IBMのシミュレーションでは、量子コンピュータが10分の1ミリ秒未満で実行できると期待される処理に2日かかりました。さらに数個の量子ビット、あるいはもう少し深度を深くすれば、量子コンピュータの挑戦者たちは容易に量子超越性の領域に滑り込む可能性があります。「一般的に言って、高度に絡み合ったシステムのエミュレーションに関しては、真にゲームを変えるような（古典的な）ブレークスルーはまだありません」とプレスキル氏は言います。「私たちは限界を爆発させるのではなく、ただかじっているだけです。」

だからといって、明確な勝利があるわけではない。「フロンティアがどこにあるかは、人々が議論を続ける問題です」とブレムナー氏は述べた。こんなシナリオを想像してみてほしい。研究者たちは、ある程度の深さを持つ50量子ビット回路（あるいは、それより少し大きくて深さの浅い回路）からサンプルを取り、量子超越性を主張する。しかし、その回路はかなりノイズが多い。量子ビットが誤動作したり、ゲートがうまく機能しなかったりするのだ。そこで、優秀な古典理論家たちが飛び込んできて、量子回路のシミュレーションを難なくこなす。「ノイズがあると、難しいと思っていたことが、古典的な観点から見るとそれほど難しくなくなるのです」とブレムナー氏は説明した。「おそらくそうなるでしょう」

さらに確かなのは、最初の「超越的」な量子マシンがもし登場したとしても、暗号を解読したり、新しい医薬品分子をシミュレーションしたりすることはないだろうということです。「それが超越性の面白いところです」とモンタナロ氏は言います。「私たちが解決する最初の問題は、答えが何なのかをあまり気にしない問題なのです。」

しかし、これらの初期の勝利は、たとえ小さなものであっても、科学者たちに正しい道を歩んでいること、つまり新しい計算体系が本当に可能であることを確信させるだろう。そして、次にどんな問題が押し寄せてくるかは誰にも分からない。

2018年2月7日訂正：この記事のオリジナル版には、クリスチャン・カルーデ氏が開発した量子アルゴリズムの古典的バージョンの例が含まれていました。その後の調査で、量子コンピューティングコミュニティにおいて、準量子アルゴリズムがオリジナルのアルゴリズムと同じ問題を解くかどうかについて激しい議論が交わされていることが明らかになりました。そのため、古典的アルゴリズムに関する記述を削除しました。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。