量子アルゴリズムが新しい種類の問題を克服します!

1994 年、数学者は、通常の古典的なコンピューターではできないことを量子コンピューターに実行させる方法を発見しました。この研究は、原理的には、量子力学の規則に基づいたマシンが、多数の数値を主因数に効率的に分解できることを示しています。これは、今日のインターネット セキュリティの基礎の大部分を構成する古典的なコンピューターにとっては非常に困難な作業です。

#それに伴い、楽観主義の波が押し寄せてきました。おそらく研究者たちは、多数の異なる問題を解決できる量子アルゴリズムを発明できるだろうと信じています。

#しかし、進歩は停滞しています。カーネギーメロン大学のライアン・オドネル氏は、「ちょっと残念だ。人々は『これは素晴らしい、きっと他にもあらゆる種類の素晴らしいアルゴリズムが開発されるだろう』と言うだろう。そして彼らはそう言うだろう」と語った。科学者らは、NP と呼ばれる標準セット内の単一の狭いクラスの問題でのみ大幅な高速化を発見しました。これは、因数分解などの効率的な検証可能な解決策があることを意味します。

過去 3 年間、このような状況が続いています。そして4月、研究者らは量子コンピューターが古典的なコンピューターよりも速く解決できる全く新しい種類の問題を発明した。これには、乱雑な出力のみに基づいて複雑な数学的プロセスの入力を計算することが含まれます。この問題が単独の問題なのか、それとも他の多くの問題のうちの最初の問題なのかはまだ判明していません。

「興奮の感覚があります。」とマサチューセッツ工科大学のコンピューター科学者、ヴィノッド・ヴァイクンタナサン氏は語ります。

コンピューター科学者は、量子コンピューターを表す数学的モデルを研究することで、量子コンピューターの何が優れているのかを理解しようとします。通常、彼らは、量子コンピューターまたは古典コンピューターと、オラクルと呼ばれる理想的なコンピューターを組み合わせたモデルを想像します。オラクルは、入力を受け取り、所定の出力を出力する単純な数学関数またはコンピューター プログラムのようなものです。

これらはランダムな動作をする可能性があり、入力がランダムな範囲 (たとえば、12 から 67) 内にある場合は「yes」を出力し、それ以外の場合は「no」を出力します。または、周期的である場合もあるため、1 から 10 までの入力は「はい」を返し、11 から 20 までは「いいえ」を返し、21 から 30 までは再び「はい」を返します。

#これらの周期的な予言の 1 つがあるが、その期間はわからないと仮定します。あなたができることは、それに数値を与えて、それが何を出力するかを確認することだけです。これらの制約の下で、コンピューターはどれくらい早くサイクルを見つけることができるでしょうか? 1993 年、当時モントリオール大学にいたダニエル サイモンは、量子アルゴリズムが、どの古典的なアルゴリズムよりも速く、密接に関連した問題に対する答えを計算できることを発見しました。

この結果により、サイモンは量子コンピューターが大きな利点を持つ可能性がある最初の兆候の 1 つを特定することができました。しかし、彼が主要な会議に論文を提出したところ、却下されました。しかし、この論文は、当時ニュージャージー州のベル研究所で働いていた会議プログラム委員会の若手メンバー、ピーター・ショールの興味をそそった。

ショールはさらに、サイモンのアルゴリズムを微調整して、神託があればその期間を計算できることを発見しました。その後、アルゴリズムを再度微調整して、周期的な予言のように動作する方程式、つまり周期的な因数分解を記述する方程式を解くことができることに気づきました。

ショールの結果は歴史的でした。彼が発見した量子アルゴリズムは、膨大な数をその構成素因数に迅速に還元することができますが、これは既知の古典的なアルゴリズムでは不可能なことです。その後数年で、研究者たちは他の効率的な量子アルゴリズムを発見しました。ショールのアルゴリズムなど、それらの中には指数関数的な利点さえも提供するものもありますが、非周期 NP 問題で顕著な量子的利点を証明できた人は誰もいません。

#進歩が見られないことに、テキサス大学オースティン校のスコット・アーロンソンとラトビア大学のアンドリス・アンバイニスという二人のコンピューター科学者が観察するようになりました。量子優位性の証明は常に、周期性などの非ランダム構造による予測に依存しているようです。 2009 年に、彼らは、ランダムまたは非構造化 NP 問題については大幅な高速化はなく、誰も例外を見つけることができないと推測しました。

彼らの推測は、量子コンピューターの機能を制限します。ただし、特定の種類の非構造化 NP 問題 (答えが「はい」または「いいえ」の問題) については、大幅な高速化はないと述べているだけです。この推測は、より具体的で定量的な答えを見つける必要がある問題、いわゆる検索問題には当てはまりません。

これを念頭に置いて、NTT 社会情報学研究所の山川崇研究者と NTT Research およびプリンストン大学の Mark Zhandry 研究者は、Oded Regev が開発したプロジェクトを調査することにしました。 2005 年に提示された特定の検索質問を試してみましょう。

#すべてが同じ方向を向いている一連の風見鶏を想像してください。それぞれを慎重に押して、突風が方向に影響を与えるようにしてください。 Regev は、最終的な方向に基づいて、最初にどこを指していたかを判断したいと考えています。このような問題は、推力と風が元の方向のランダムな誤差源として機能するため、「誤差学習」として知られるようになりました。古典アルゴリズムと量子アルゴリズムはどちらも解決が難しいという証拠があります。

山川とザンドリーが設定を微調整しました。彼らは、より予測しやすくするために、これらのスタートのパワーを修正しました。彼らはまた、ランダムな神託によって風を決定したため、場合によってはさらにランダムになりますが、完全に休止状態になる場合もあります。

#これらの変更により、研究者らは、量子アルゴリズムが初期方向を効果的に見つけることができることを発見しました。彼らはまた、古典的なアルゴリズムは指数関数的に遅くなる必要があることも証明しました。その後、ショールと同様に、彼らは問題の現実的なバージョンを解決するためにアルゴリズムを適応させ、予測を実際の数式に置き換えました。

コンピューター科学者は、この問題を理解して解決しようとまだ努力しています。 Vaikuntanathan 氏は、これをデータ圧縮時に発生する別の状況に例えました。情報が圧縮されると、2 つのビットが誤って同じ場所に押し込まれ、上書きされる可能性があります。このような衝突を事前に予測して回避するという問題には、いくつかの類似点があります。 「これは基本的に次のような問題のクラスです。おそらくこれらの問題は量子的に解決できるでしょう。」

人々はそう願っています。今日の量子コンピューターの誕生したばかりのバージョンでは、新しい問題のような非構造化問題を解決でき、それらをテストする方法が提供されます。構造化されていない問題は、プログラムに必要なリソースが少なくて済み、あるいはすでにランダムであるため、ノイズの影響を受けにくくなる可能性があるという考えでした。しかし今のところ、この新たな問題は、既存の量子コンピューターでは解決するにはまだ高度すぎるようです。 「奇妙な質問ですね。定義することは考えていませんでした」とアーロンソン氏は言いました。「しかし、振り返ってみると、これには非常に優れた機能がいくつかあります。」

この結果は、非構造化 NP 問題における重要な量子的利点の最初の例を提供します。量子の世界の他の多くの問題は、ほぼ解決不可能から解決可能になるのでしょうか?今ではそう考える理由がさらに増えています。 「これは、量子コンピューターがどのような問題を解決するのが得意なのかについての私たちの見方をある程度変えるものです」とオドネル氏は言う。

以上が量子アルゴリズムが新しい種類の問題を克服します!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。