1994 年、数学者は、通常の古典的なコンピューターでは不可能なことを量子コンピューターに実行させる方法を発見しました。この研究により、原理的には、量子力学の規則に基づいたマシンが、多数の数値を効率的に素因数に分解できることが明らかになりました。これは、古典的なコンピュータでは非常に困難な作業であり、今日のインターネット セキュリティの多くの基礎を形成しています。
楽観的な見方が続いた。 おそらく、研究者たちは、さまざまな問題を解決できる量子アルゴリズムを発明できるだろうと考えました。
しかし、進歩は行き詰まりました。 「それは少し厄介な軌道でした」と言いました ライアン・オドネル カーネギーメロン大学の。 「人々は、 『これはすごい、他のあらゆる種類のすごいアルゴリズムを手に入れると確信している』のようでした。 いいえ。" 科学者たちは、標準セット内からの単一の狭いクラスの問題に対してのみ劇的なスピードアップを発見しました NPと呼ばれる、つまり、因数分解などの効率的に検証可能なソリューションがあったことを意味します。
それはほぼXNUMX年間のケースでした。 それからXNUMX月に、研究者は 考案 量子コンピューターが古典的な問題よりも指数関数的に速く解決できるはずの根本的に新しい種類の問題。 それは、そのごちゃごちゃした出力だけに基づいて、複雑な数学的プロセスへの入力を計算することを含みます。 問題が単独で発生するのか、それとも他の多くの新しいフロンティアの最初の問題であるのかは、まだ決定されていません。
「興奮の感覚があります」と言いました ヴィノド・ヴァイクンタナサン、マサチューセッツ工科大学のコンピューター科学者。 「多くの人が他に何があるかを考えています。」
コンピューター科学者は、量子コンピューターを表す数学的モデルを研究することによって、量子コンピューターが何をよりよく行うかを理解しようとします。 多くの場合、彼らはオラクルと呼ばれる理想化された計算機とペアになった量子または古典的なコンピューターのモデルを想像します。 オラクルは、単純な数学関数やコンピュータプログラムのようなもので、入力を受け取り、所定の出力を吐き出します。 それらはランダムな動作をする可能性があり、入力が特定のランダムな範囲（たとえば、12〜67）内にある場合は「はい」を出力し、そうでない場合は「いいえ」を出力します。 または、周期的である可能性があります。そのため、1〜10の入力は「はい」を返し、11〜20は「いいえ」を返し、21〜30は再び「はい」を返します。
これらの定期的なオラクルの1993つがあり、期間がわからないとします。 あなたができることは、それに番号を与えて、それが何を出力するかを見るだけです。 これらの制約がある場合、コンピューターはどのくらいの速さで月経を見つけることができますか？ XNUMX年、当時モントリオール大学に在籍していたダニエルサイモンは、量子アルゴリズムが、従来のアルゴリズムよりも指数関数的に高速に関連する問題の答えを計算できることを発見しました。
その結果、サイモンは、量子コンピューターの劇的な優位性が期待できる場所の最初のヒントのXNUMXつを決定することができました。 しかし、彼が彼の論文を主要な会議に提出したとき、それは拒否されました。 しかし、この論文は、会議のプログラム委員会のジュニアメンバーに関心を持っていました— ピーターショール、当時ニュージャージーのベル研究所にいた。 Shorはさらに、Simonのアルゴリズムを適応させて、オラクルの期間があればそれを計算できることを発見しました。 次に、彼はアルゴリズムをもう一度適応させて、周期的なオラクルと同様に動作する方程式を解くことができることに気付きました。これは、周期的な因数分解を表す方程式です。
Shorの結果は歴史的でした。 彼が発見した量子アルゴリズムは、巨大な数をそれらの構成素因数に急速に減らすことができました。これは、既知の古典的なアルゴリズムでは不可能なことです。 その後の数年間で、研究者たちは他の効率的な量子アルゴリズムを発見しました。 ショアのアルゴリズムのように、それらのいくつかは指数関数的な利点さえ提供しましたが、周期的ではないNP問題に対して劇的な量子的利点を証明できる人は誰もいませんでした。
この進歩の欠如により、XNUMX人のコンピューター科学者が スコットAaronson テキサス大学オースティン校、および アンドリス・アンバイニス ラトビア大学の観察をするために。 量子超越性の証明は常に、周期性などのある種の非ランダム構造を持つオラクルに依存しているように見えました。 2009年に、彼らは 推測された ランダムな、または構造化されていないNP問題で劇的なスピードアップはあり得なかった。 誰も例外を見つけることができませんでした。
彼らの推測は、量子コンピューターの力に限界をもたらしました。 しかし、特定のタイプの非構造化NP問題（「はい」または「いいえ」の回答がある問題）には劇的なスピードアップはなかったとだけ述べています。 探索問題として知られている、より具体的で定量的な答えを見つけることを含む問題の場合、推測は当てはまりませんでした。
それを念頭に置いて、研究者 山川隆 NTT社会情報学研究所と マーク・ザンドリー NTTリサーチとプリンストン大学の研究者は、2005年に導入された特定の探索問題を実験することを決定しました。 オデッド・レジェブ.
すべて同じ方向を向いている風見鶏のセットを想像してみてください。 それらのそれぞれに測定された突き出しを与え、次に突風がそれらの方向に影響を与えるようにします。 Regevは、最終的な方向性に基づいて、最初に全員がどこを指していたかを判断したいと考えていました。 このような問題は、突き出しと風が元の方向でランダムなエラーの原因のように機能するため、「エラーを伴う学習」と呼ばれるようになりました。 古典的アルゴリズムと量子アルゴリズムの両方を解くのは難しいという証拠があります。
山川とザンドリーはセットアップを微調整しました。 彼らはそれらの最初の突き棒の強さを修正し、それらをより予測可能にしました。 それらはまた、風がランダムオラクルによって決定されるようにしたので、ある場合にはさらにランダムでしたが、他の場合には完全に休眠していました。
これらの変更により、研究者たちは、量子アルゴリズムが効率的に初期方向を見つけることができることを発見しました。 彼らはまた、古典的なアルゴリズムは指数因子によって遅くなければならないことを証明しました。 Shorと同様に、彼らはアルゴリズムを適応させて、問題の実際のバージョンを解決しました。これにより、オラクルが実際の数式に置き換えられます。
コンピュータ科学者はまだ問題を理解し、構築するために働いています。 Vaikuntanathanは、データ圧縮を行うときに発生する別のビットと比較します。情報が圧縮されているときに、XNUMXつのビットが誤って同じ場所に圧縮され、上書きされる可能性があります。 これらの衝突を事前に予測して回避できるようにするという問題には、いくつかの類似点があります。 「それは基本的にこのように見える問題のクラスです」と彼は言いました。 「たぶん、これらの問題は量子的に解決できるでしょう。」
新しい問題のような構造化されていない問題は、今日の新しいバージョンの量子コンピューターでも解決できる可能性があり、それによってそれらをテストする手段を提供することが期待されていました。 構造化されていない問題は、すでにランダムであるため、プログラミングに必要なリソースが少なくなるか、ノイズに対する感度が低くなる可能性があると考えられていました。 しかし、これまでのところ、新しい問題は、既存の量子コンピューターでは解決するにはまだ進んでいるように見えます。 「それは奇妙な問題です。 私はそれを定義することを考えていませんでした」とアーロンソンは言いました。 「しかし、振り返ってみると、いくつかの非常に優れた機能があります。」
結果は、非構造化NP問題に対する劇的な量子優位性の最初の例を提供します。 量子世界が実質的に解けないものから解けるものに変わる他の多くの問題があるでしょうか？ 今ではそう考える理由がもっとあります。
「量子コンピューターが得意とする問題の種類についての私たちの信念はやや覆されました」とオドネルは言いました。
