カリフォルニア州サニーベール – 26 年 2022 月 XNUMX 日 – NTT Research は、 暗号と情報セキュリティ (CIS) ラボ そしてそこの同僚 NTT社会情報研究所 (SIL) は、量子優位性に関する画期的な論文を書きました。 この論文は、31 月 3 日から XNUMX 月 XNUMX 日に開催される年次 IEEE Symposium on Foundations of Computer Science (FOCS) での発表に選ばれました。 デンバーでXNUMX位。
「」というタイトルの論文の共著者構造のない検証可能な量子的優位性」は、NTT SIL の特別研究員である山川隆博士と、 NTTリサーチ CIS ラボこの作業の一部はプリンストン大学で行われました。山川博士は客員研究員であり、Zhandry 博士はコンピューター サイエンスの助教授も務めています。
量子の利点 (または量子スピードアップ) のトピックは、量子コンピューターが従来のコンピューターまたは非量子コンピューターよりも速く解決できる問題の種類と、それらがどれだけ高速であるかに関連しています。 問題となっている問題は、一般的に非決定論的多項式時間 (NP) クラスとして説明されます。 どのくらいの利点が大幅に異なる可能性があります。 量子コンピューターは、特定の問題を XNUMX 分または XNUMX 秒で解決できる可能性があります。これは、従来のコンピューターでは XNUMX 週間、あるいは計り知れないほどの指数関数的な時間がかかる可能性があります。 この論文では、著者はこの優位性を検証し、効率的に検証するという課題に取り組んでいます。 これまでのところ、量子優位性の実証には、重要な「構造」、つまり XNUMX つ以上の関係者間のやり取りが含まれていました。 Yamakawa と Zhandry の論文のブレークスルーは、構造なしで検証が可能な NP 困難な問題を実証することです。
「ランダム オラクルのみを必要とする NP 検索問題の指数関数的な量子スピードアップを見たのはこれが初めてです」と、テキサス大学オースティン校のコンピュータ サイエンス教授である Scott Aaronson 博士は、初期バージョンについてコメントしました。 13 年 2022 月 XNUMX 日にシモンズ コンピューティング理論研究所で開催されたワークショップでの論文の説明。 ランダム オラクル、つまり各クエリに対してランダムな応答を生成する理論上のブラック ボックスのみを必要とすることで、Yamakawa と Zhandry は、構造化されていない計算上の仮定に基づいて問題を構築しました。 そのため、彼らの問題は、公開鍵暗号に見られるような構造化された関数ではなく、一方向関数とより密接に関連しています。 この一方向の配置により、効率的な検証が容易になります。
「NTT 傘下の暗号技術者が、NTT Research のもう XNUMX つの重点分野である量子コンピューティングの理解を深める論文において、再び『ブレイクスルー』のラベルに値する研究に協力していることは非常に喜ばしいことです。」 、NTT Research 代表取締役社長。 「この権威ある IEEE カンファレンスに参加されたすべての方々にお祝いとご多幸をお祈り申し上げます。」
山川と Zhandry が考案した NP 探索問題は、1) 与えられた誤り訂正符号の符号語である n 記号列と、2) それぞれがシンボルは、ランダムオラクルの下でゼロにマップされます。 各問題は個別に簡単です。 しかし、コードワードであり、ゼロにマップされる単一のシンボル文字列を見つけることは、少なくとも古典的にははるかに困難です。 「量子なら、これを多項式時間で解くことができます」と Zhandry 博士は言いました。 一方、潜在的な解決策が与えられた場合、それが XNUMX つの問題のそれぞれを個別に解決することを確認することによって、それを検証するのは簡単です。 FOCS の論文にふさわしく、この作業は基本的または基礎的なものであることに注意してください。 Simons Institute での Aaronson 博士の講演で指摘されているように (この NTT Research で説明) ブログ記事)、Yamakawa-Zhandry の議論は、スピードアップのクラスに分類され、数学的には容易に確認できますが、実際の量子コンピューターによってすぐに実際に実証されることはありません。 しかし、その画期的な検証スキームを超えて、この論文は、量子スピードアップの程度に関して何か新しいことも指摘しています。
「私たちの仕事の前に、因数分解やブラックボックス設定での期間発見など、NP問題に対する量子的利点の例がありました. しかし、これらすべての例の根底にある量子アルゴリズムは基本的に周期発見であることが判明しましたが、これらの例に周期発見を適用する方法を示すことはしばしば重要でした. 「私たちの論文は、少なくとも XNUMX 番目のケースがあることを示しています。 これは、量子優位性が以前に考えられていたよりも広範囲に及ぶという希望があると楽観的に解釈することができます。」
IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) が後援する FOCS は、理論的コンピューター サイエンスの分野における主要な会議です。 第 2022 回年次総会である FOCS 63 の論文募集では、量子コンピューティングが 17 の一般的な関心分野の 31 つとして挙げられました。 Yamakawa-Zhandry 論文は、2022 年 10 月 15 日午前 XNUMX 時 XNUMX 分 (MT) に発表される予定です。 このイベントの詳細と登録については、次の Web サイトをご覧ください。 FOCS2022 ウェブサイトをご覧ください。
