この物語 のオリジナル版はQuanta Magazineに掲載されました。
コンピュータ科学者にとって、問題解決は登山に似ています。まず、解決すべき問題を選択しなければなりません。これは登るべき山頂を特定するようなものです。そして、それを解決するための戦略を立てなければなりません。古典力学の研究者と量子力学の研究者はそれぞれ異なる戦略を用いて競い合い、健全なライバル関係を築いています。量子力学の研究者は、問題を素早く解決する方法を報告します。多くの場合、誰も登る価値があるとは考えていなかった山頂に登ることで解決します。そして古典力学のチームは、より良い方法を見つけられるかどうか競い合います。
この競争はほぼ常に事実上の引き分けに終わる。研究者が他のどのアルゴリズムよりも高速または優れた量子アルゴリズムを考案したと思った時、古典派の研究者はそれに匹敵するアルゴリズムを思いつくのが通例だ。つい先週、サイエンス誌に掲載された量子加速法とされる研究に対し、古典派マシンで同様の計算を実行する方法を示した2つの別々のグループから即座に懐疑的な意見が出された。
しかし、昨年、科学論文サイトarxiv.orgに掲載された論文の中で、研究者たちは、説得力がありかつ有用な量子加速法のようなものを説明した。研究者たちは、膨大な数の選択肢の中から最善の解を探す幅広い最適化問題において、既知のあらゆる古典的アルゴリズムよりも高速に優れた解を見つける新しい量子アルゴリズムを説明した。
これまでのところ、復号量子干渉法（DQI）と呼ばれる新しいアルゴリズムを凌駕する古典的アルゴリズムは存在しません。ライクマン大学の数学者で量子コンピューティング懐疑論の有力者であるギル・カライ氏は、これは「量子アルゴリズムにおける画期的な進歩」だと述べています。量子アルゴリズムに関する報告は研究者を興奮させます。それは、難しい問題に関する新たなアイデアを明らかにできることに加え、量子マシンをめぐる騒ぎにもかかわらず、実際にどの問題にメリットがあるのかが明確でないことが理由です。最適化タスクにおいて既知の古典的アルゴリズムを上回る性能を持つ量子アルゴリズムが実現すれば、量子コンピュータの潜在能力を最大限に引き出す大きな一歩となるでしょう。
「この研究にとても興奮しています」と、オランダ国立数学・計算機科学研究所（CWI）の理論計算機科学者、ロナルド・デ・ウルフ氏は述べた。同氏は今回の新アルゴリズムには関わっていない。しかし同時に、研究者たちが最終的に同等の性能を持つ古典的なアルゴリズムを発見する可能性は依然として十分にあると警告した。また、量子ハードウェアが不足しているため、この新アルゴリズムを実験的に検証できるようになるまでには、まだしばらく時間がかかるだろう。
カリフォルニア大学バークレー校のコンピュータ科学者、エウィン・タン氏によると、このアルゴリズムは古典的アルゴリズムの分野で新たな研究を刺激する可能性があるという。同氏は10代の頃に量子アルゴリズムに匹敵する古典的アルゴリズムを開発して注目を集めた。今回の新たな主張は「古典的アルゴリズムの研究者に『この論文を読んで、この問題に取り組むべきだ』と言いたいほど興味深い」とタン氏は述べた。
最善の道は?
古典的アルゴリズムと量子アルゴリズムが競い合う場合、多くの場合、最適化という戦場で競い合います。最適化とは、困難な問題を解決するための最善の選択肢を見つけることに焦点を当てた分野です。研究者は通常、問題が大きくなるにつれて可能な解の数が爆発的に増加する問題に焦点を当てます。配送トラックが3日間で10都市を巡回する最適な方法は何か？荷物を荷台にどう詰め込むべきか？これらの問題を解決する古典的な方法は、多くの場合、巧妙な方法で可能な解を次々と試していく必要があり、すぐに実行不可能になります。
DQIが取り組む具体的な最適化問題は、おおよそ次のようになります。紙の上に点の集合が与えられます。これらの点を通る数学関数を考え出さなければなりません。具体的には、関数は多項式、つまり変数を整数の指数で累乗し、係数を掛け合わせた組み合わせでなければなりません。ただし、あまり複雑にしすぎてはならず、つまりべき乗が大きくなりすぎてはなりません。こうすることで、紙の上を移動しながら上下に波打つ曲線が得られます。あなたの仕事は、最も多くの点に接する波線を見つけることです。
この問題のバリエーションは、コンピュータサイエンス、特にエラーコーディングと暗号学といった、データの送信時に安全かつ正確にエンコードすることに重点を置く分野において、様々な形で現れます。DQIの研究者たちは、基本的に、より良い線を描くことは、ノイズの多いエンコードされたメッセージをその正確な意味に近づけることに似ていることを認識しました。
しかし、それはすべて後から起こったことです。DQIの研究者たちがアルゴリズムの開発に着手した当初は、この問題を念頭に置いていませんでした。
問題の解読
「目標志向の研究者であれば、まず問題を提起し、量子アルゴリズムが古典アルゴリズムよりも速く解けるかどうかを調査するという選択肢は全くあり得ます」と、Google Quantum AIの物理学者であり、DQIの主要な設計者の一人であるスティーブン・ジョーダン氏は述べた。「もちろん、私たちの場合はそうではありませんでした。私たちは、逆行的で回りくどい経路を経て、この問題に辿り着いたのです。」
スティーブン・ジョーダンは、特定の問題に対する量子的なアプローチの考案に貢献しました。このアプローチは、これまでのところ、どんな古典的なアプローチよりも優れています。
ジョーダンが2023年にその道を歩み始めたのは、Googleに入社し、長年にわたり古典アルゴリズムを上回る量子アルゴリズムの研究に取り組んでいるGoogleの物理学者、エディ・ファーヒと働くことになると知った時だった。（ファーヒはかつてマサチューセッツ工科大学でジョーダンの博士課程の指導教官を務めていた。）ジョーダンは、2014年にファーヒがエネルギーを考慮し、エネルギーが低いほどより良い解が得られるという考え方を用いて、最適化問題に量子攻撃を仕掛けたことを知っていた。ファーヒにとって、エネルギーは最適化と量子物理学を結びつける要素だった。
しかしジョーダンは別のことをしたかった。量子物理学に組み込まれた別の概念、すなわちあらゆるものを波として認識するという概念に着目したのだ。量子フーリエ変換と呼ばれる数学的手法を用いて、ジョーダンはよく知られた最適化問題に対するあらゆる潜在的な解を量子波に変換する方法を発見した。これにより、より大きな波（より高い量子振幅の形で）がより良い解に対応するように量子系を操作することができた。
しかし、克服すべき大きな課題がまだ残っていました。量子システムにおいて、「最大の振幅は何か？」と問うことは、海岸で最大の波を認識するほど単純ではありません。量子ランドスケープは極めて複雑であり、最適な解に対応する量子振幅をどのように特定すればよいのかが不明でした。
幾度もの失敗を経て、ジョーダンは画期的な進歩を遂げました。最適な解を選択するプロセスは、暗号化されたメッセージからエラーを除去するプロセス、つまりデコードに似ていることが判明したのです。これはコンピュータサイエンスにおいて深く研究されている分野であり、ジョーダンが探求できる技術が豊富に存在します。最適化問題を量子問題に置き換え、デコードというレンズを当てはめることで、彼は量子アルゴリズムを開発する新たな方法にたどり着いたのです。
イラスト：ダニエル・ガルシア（Quanta Magazine）
ジョーダンは、同じくGoogleのノア・シャッティと共に、復号方式のテストを開始し、様々な最適化問題において従来のアルゴリズムと比較検討しました。適切なアプローチと、それが機能する問題の両方が必要でした。「従来のアルゴリズムに勝つのは難しいことが分かりました」とジョーダンは言います。「数ヶ月の試行錯誤を経ても、量子アルゴリズムではまだ成果を上げられていませんでした。」
しかし最終的に、二人は1960年代に初めて導入された、暗号化されたメッセージ内の個々のエラーを見つけて修正する復号アルゴリズムにたどり着いた。その問題を見つけることが鍵だった。「調べてみると、ほぼすぐに成功に近づいたように見えました」とジョーダン氏は語った。ついに、彼らは問題と、それらが組み合わさって量子加速に見えるアプローチを発見したのだ。
もちろん、だからといってそれが完璧というわけではありません。「もしかしたら、あなたのアプローチ全体を効率的に再現できる古典的な方法があるかもしれません」とジョーダン氏は言います。「そのような逆量子化は必ずしも自明ではありません。」
自信を得る
こうした懸念を和らげるため、彼らは符号理論の専門家であり、シャッティ氏のスタンフォード大学での博士課程の指導教官でもあるメアリー・ウッターズ氏に相談した。ウッターズ氏は、彼らの量子加速に匹敵する可能性のある既知の古典的アルゴリズムを綿密に調査した。その結果、量子加速の優位性は維持された。チームの検証結果も、この優位性が今後も維持されることを示唆している。「彼らは十分な注意を払ったのです」とタン氏は述べた。
この分析に勇気づけられ、彼らは自分たちが解こうとしていた最適化問題をより注意深く検討した。ジョーダンは、この問題がニッチすぎて幅広い応用が期待できないのではないかと懸念していたが、シャッティはこの復号問題が暗号化などの分野でよく知られ、有用な問題のバリエーションであることを認識した。
ジョーダン氏は、十分に大きな量子マシンがなければ、DQIは理論的なブレークスルーにとどまるだろうと認めている。「DQIは現在の量子コンピュータでは動作しません」と彼は述べた。しかし、彼らはまだ前進を続けている。研究チームが昨年8月に研究成果を発表して以来、DQIの適用範囲は当初の問題から、より広範な最適化問題へと拡大しており、そこには「最良経路」問題のより多くのケースが含まれる。
ジョーダン氏は、これまでのところ、DQI はこれらの問題でも従来のアルゴリズムに勝てると予想していると述べた。
今のところ、量子コミュニティは依然として興奮している。「古典的アルゴリズムよりも優位性を示す量子アルゴリズムの発見は、過去30年間における非常に刺激的な取り組みであり、そのような優位性を示す明確なアルゴリズムの数は多くありません」とカライ氏は述べた。「だからこそ、あらゆる新しいアルゴリズムは祝福に値するのです。」
オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得 て転載されました。
