フラッシュ2022年11月1日
-
NTT、量子超越性を示す新たなアルゴリズムを30年ぶりに考案
by MITテクノロジーレビュー編集部 [MIT Technology Review Japan]NTTの研究チームは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子コンピューターの優位性(「量子超越性」と呼ぶ)を示す新たな量子アルゴリズムを初めて考案した。「ショア(Shor)の素因数分解アルゴリズム」以来、約30年ぶりの本質的に新しいアイディアに基づく、検証可能な量子超越性を示すアルゴリズムだという。
研究チームは、構造を持たないランダムな関数(入力nビット、出力1ビット)の出力が0になる入力を見つける問題に、その入力が誤り訂正符号にもなっているという条件を追加。量子コンピューターでは高速に解けるが、古典コンピューターでは高速に解の探索ができない問題を定義することに成功した。
量子コンピューターが高速に解ける問題として、1994年に示されたShorの素因数分解アルゴリズムがよく知られている。Shorの素因数分解アルゴリズムは、自然数の累乗の剰余が周期性という「構造」を持っていることを利用している。出力に周期性のないハッシュ関数のような「構造」を持たない関数を用いた問題について、検証可能な量子超越性を示す結果はこれまで知られていなかった。
今回の成果により、これまで実用的な量子アルゴリズムを見つけることは難しいと考えられてきた問題に対するアルゴリズムの研究が促進され、量子計算機の適用範囲が広がることが期待される。この研究は、2022月10月31日~11月3日に開催される理論計算機科学の国際会議「IEEE Symposium on Foundations of Computer Science (FOCS) 2022」で発表される。
(中條)
-
- 人気の記事ランキング
-
- AI can make you more creative—but it has limits 生成AIは人間の創造性を高めるか? 新研究で限界が明らかに
- Promotion Call for entries for Innovators Under 35 Japan 2024 「Innovators Under 35 Japan」2024年度候補者募集のお知らせ
- A new weather prediction model from Google combines AI with traditional physics グーグルが気象予測で新モデル、機械学習と物理学を統合
- How to fix a Windows PC affected by the global outage 世界規模のウィンドウズPCトラブル、IT部門「最悪の週末」に
- The next generation of mRNA vaccines is on its way 日本で承認された新世代mRNAワクチン、従来とどう違うのか?