18歳の中国系アメリカ人の少年が「量子コンピューティングの分野における大きな進歩を無に帰した」！

わずか18歳のユーイン・タン氏は、一般的なコンピューターが量子コンピューターとほぼ同じ速さで「推奨問題」を解決できることを実証した。この画期的な発見は、量子コンピューターが大幅な高速化を実現する最初の例の1つを否定するものである。

[[238644]]

ユーイング・タンの最近の写真

ユーイング・タンは今秋大学院に入学する予定だ。画像提供: テキサス大学オースティン校の Vivian Abagiu

米国テキサス州出身の才能ある若者が量子コンピューティングコミュニティに冷水を浴びせた。今月初めにオンラインで公開された論文の中で、18歳のエウィン・タンは、普通のコンピューターが量子コンピューターに匹敵する性能で重要な計算問題を解決できることを実証した。

最も実際的な意味での「推奨問題」は、Amazon や Netflix などのサービスが、ユーザーが試してみたい製品をどのように決定するかという問題です。コンピューター科学者たちは以前、これが量子コンピューターを使用することではるかに速く解決できる問題の最初の例の 1 つであると信じており、この推奨問題はこれらの将来のマシンの威力を示す重要な例となっています。現在、唐氏はこの証拠を否定している。

「これは量子コンピューターがいかにして劇的に高速化できるかを示す最も典型的な例の一つだったが、今ではもはや通用しなくなっている」と、テキサス大学オースティン校をこの春卒業し、秋にはワシントン大学で博士号取得を目指すタン氏は語った。

2014年、14歳になったタンさんは4年生から6年生まで飛び級し、テキサス大学オースティン校に入学し、数学とコンピューターサイエンスを専攻した。 2017年の春、タン氏は量子コンピューティング分野の著名な研究者であるスコット・アーロンソン氏が教える量子情報コースを受講しました。アロンソンはタンが並外れて才能のある学生だと考え、彼の独立研究プロジェクトの指導教官を務めることを申し出た。アロンソン氏はタン氏に、推薦に関する質問を含むいくつかの選択肢の質問を投げかけた。タン氏は、やや不本意ながら推薦の質問を選択した。

タンさんは、「推奨された質問を見て、難しい質問だと思ったので躊躇しましたが、実際には彼が出した質問の中で最も簡単な質問でした」と語った。

推奨問題は、ユーザーが好む可能性のある製品を推奨することを目的としています。 Netflixを例に挙げてみましょう。あなたがどの映画を視聴したかがわかります。何百万人もの他のユーザーがどの映画を視聴しているかを知っています。これらの情報を組み合わせると、次に見たい映画は何でしょうか?

このデータは巨大なグリッドまたはマトリックスに配置され、上部に映画がリストされ、片側にユーザ​​ーがリストされ、グリッド内の各ポイントの値が各ユーザーが各映画を気に入ったかどうか、またはどの程度気に入ったかを数値化したものと考えられます。優れたアルゴリズムは、映画とユーザー間の類似点を迅速かつ正確に識別し、マトリックスのギャップを埋めて映画を推奨します。

2016年、2人のコンピューター科学者、Iordanis Kerenidis氏とAnupam Prakash氏は、既知のどの古典的アルゴリズムよりもはるかに高速に推奨問題を解決する量子アルゴリズムを発表しました。彼らは、問題を単純化することでこのスピードを達成しました。つまり、マトリックス全体に記入して推奨する最良の製品を 1 つ特定するのではなく、ユーザーを少数のカテゴリに分類する方法を開発しました。ユーザーは大ヒット映画が好きですか、それともインディーズ映画が好きですか?次に、推奨事項が十分に適切になるように、既存のデータがサンプリングされます。

クレニディス氏とプラカシュ氏が研究成果を発表した当時、量子コンピュータが従来のコンピュータよりもはるかに速く問題を解決できると思われる例はほんのわずかしかありませんでした。こうした例のほとんどは、今年初めにQuantaで報告された「相互関係」問題など、量子コンピューターを活用する狭い範囲の問題に取り組むために設計された特殊なものである。クレニディス氏とプラカシュ氏の研究結果は、量子コンピュータが古典的コンピュータよりも優れた性能を発揮できる問題の現実的な例を示している点で興味深い。

「私の意見では、これは機械学習とビッグデータの分野において、古典的コンピュータではまだやり方が分かっていないことを量子コンピュータが実現できることを示す最初の例の一つだ」とパリのコンピュータサイエンス基礎研究所のコンピュータ科学者、クレニディス氏は語った。

クレニディス氏とプラカシュ氏は、量子コンピュータが既知のどのアルゴリズムよりもはるかに高速に推奨問題を解決できることを示したが、高速な古典的アルゴリズムが存在しないことを証明したわけではない。そのため、アーロンソン氏が2017年にタン氏と協力し始めたとき、彼が提起した問題は、高速な古典的な推奨アルゴリズムが存在しないことを証明し、量子コンピューターが大幅な高速化をもたらす可能性があるというクレニディス氏とプラカシュ氏の主張を確認することだった。

「私にとって、それは物語の重要な詳細です」とアロンソン氏は語った。彼は当時、高速な古典的アルゴリズムは存在しないと主張した。

タン氏は、推奨問題を卒業論文のテーマとして追求するつもりで、2017 年秋にこの研究を始めました。タン氏は、高速な古典的アルゴリズムは存在しないことを証明しようと何ヶ月も費やした。時間が経つにつれて、タン氏はそのようなアルゴリズムが存在するかもしれないと考え始めました。

「私は高速な古典的アルゴリズムが存在すると信じ始めましたが、スコットはそのような古典的アルゴリズムは存在しないと考えていたようで、彼が権威だったので、自分自身でそれを証明できませんでした」とタン氏は語った。

その年、卒業論文の締め切りが近づくと、ドンはアーロンソンに手紙を書き、自分の抱く疑念が高まっていることを認めた。「ドンは私に手紙を書いて、『高速な古典的アルゴリズムがあると思う』と言っていました」とアーロンソンは語った。

春の間中、ドンは結果をまとめ、アーロンソンと協力して証明のいくつかのステップを明確にしました。タン氏が発見した高速古典アルゴリズムは、2年前にクレニディス氏とプラカシュ氏によって発見された高速量子アルゴリズムから直接インスピレーションを得たものです。タン氏は、彼らのアルゴリズムで使用した種類の量子サンプリング技術が古典的な設定でも再現できることを示した。 Krenidis と Prakash のアルゴリズムと同様に、Tang のアルゴリズムは多重対数時間で実行されます。つまり、計算時間は特徴 (データセット内のユーザー数や製品数など) の対数に比例し、これまで知られているどの古典的なアルゴリズムよりもはるかに高速です。

タン氏がアルゴリズムを完成させると、アーロンソン氏はそれを公表する前に結果が正しいことを確認したかった。 「ドンが論文をオンラインに投稿したら、それが間違っていて、ドンのキャリアで最初の主要な論文になったとしたらどうなるのか、私はまだ心配している」とアロンソン氏は語った。

アーロンソン氏は6月にカリフォルニア大学バークレー校で開催される量子コンピューティングのワークショップに参加する予定だった。クレニディス氏やプラカシュ氏を含む、この分野の著名人の多くが出席した。アーロンソンは正式な会議の数日後にタン氏をバークレーに招待し、彼のアルゴリズムを非公式に発表した。

6月18日と19日の午前、唐氏は2回の講演を行い、聴衆からの質問に落ち着いて答えた。 4時間後、全員が合意に達しました。タンの古典的なアルゴリズムは正しいようです。しかし、会場にいた多くの人は、講演者が実際どれほど若いのか気づいていなかった。 「彼が18歳だとは知らなかった」とクレニディスさんは語った。 「私は絶対にそうは聞こえなかった。私には、彼はとても大人びた声に聞こえた。」このアルゴリズムは現在、出版前に正式な査読を受けています。

タン氏の研究結果は量子コンピューティングコミュニティにとって衝撃的なものだったかもしれない。タン氏は量子コンピューティングの利点を示す最も明確かつ象徴的な例の1つを否定した。同時に、Tang 氏の論文は、量子アルゴリズムの研究と古典的アルゴリズムの研究が実際にお互いを促進し合うことができることをさらに証明しています。

「ドンは、量子コンピューターが物事を劇的に高速化できるというクレニディス氏とプラカシュ氏の考えを否定したが、別の意味では、ドンは彼らの研究を基にして大きな進歩を成し遂げた」とアーロンソン氏は語った。 「量子アルゴリズムがなかったら、ドンはこの古典的なアルゴリズムを思いつかなかったかもしれません。」