研究者らは、暗号用に、より小型でノイズ耐性に優れた量子因数分解回路を提案している。

あなたが最近送信した電子メールは、おそらく、最も高速なコンピュータでも巨大な数字を効率的に因数分解することはできないという考えに基づいた、実績のある方法を使用して暗号化されたものです。

一方、量子コンピュータは、従来のコンピュータでは絶対に解読できない複雑な暗号システムを迅速に解読できると期待されている。この期待は量子因数分解に基づいている。 アルゴリズム これは、現在 MIT の教授であるピーター・ショアによって 1994 年に提案されました。

しかし、研究者たちは過去30年間で大きな進歩を遂げてきたものの、ショアのアルゴリズムを実行できるほど強力な量子コンピューターをまだ構築できていない。

研究者の中には、より大型の量子コンピュータの構築に取り組む者もいる一方で、ショアのアルゴリズムをより小型の量子回路で実行できるように改良しようとしている者もいる。約 1 年前、ニューヨーク大学のコンピュータ科学者オデッド・レゲフ氏は、理論上の大きな改良を提案した。同氏のアルゴリズムはより高速に実行できるが、回路にはより多くのメモリが必要になるという。

MIT の研究者は、これらの結果を基に、Regev のアルゴリズムの速度と Shor のアルゴリズムのメモリ効率を組み合わせた、両方の長所を兼ね備えたアプローチを提案しました。この新しいアルゴリズムは、Regev のアルゴリズムと同等の速度で、必要な量子ビットと呼ばれる量子構成要素が少なく、量子ノイズに対する耐性も高いため、実際に実装するのがより現実的になる可能性があります。

長期的には、この新しいアルゴリズムは、量子コンピューターの暗号解読力に耐えられる新しい暗号化方法の開発に役立つ可能性があります。

「もし大規模な量子コンピュータが構築されれば、因数分解は不可能となり、暗号化に使用できる別の方法を見つけなければなりません。しかし、この脅威はどの程度現実的なのでしょうか? 量子因数分解は実用化できるのでしょうか?

「私たちの研究は、実用的な実装に一歩近づく可能性があります」と、フォード財団工学教授であり、コンピュータサイエンスおよび人工知能研究所（CSAIL）のメンバーであり、 紙 アルゴリズムを説明します。

この論文の主著者は、MIT電気工学・コンピュータサイエンス学部の大学院生、セユーン・ラガヴァン氏です。この研究は、2024年国際暗号学会議（クリプト2024）。

暗号解読

インターネット経由でメッセージを安全に送信するために、電子メール クライアントやメッセージング アプリなどのサービス プロバイダーは通常、1970 年代に MIT の研究者 Ron Rivest、Adi Shamir、Leonard Adleman によって発明された暗号化方式である RSA に依存しています (「RSA」という名前はここから来ています)。このシステムは、2,048 ビットの整数 (617 桁の数字) を因数分解するのは、コンピューターが妥当な時間内に行うには難しすぎるという考えに基づいています。

その考えは1994年に、当時ベル研究所に勤務していたショアが量子コンピューターがRSA暗号を破るのに十分な速さで因数分解できることを証明するアルゴリズムを発表したときに一変した。

「あれは転換点だった。しかし1994年当時、十分な大きさの量子コンピューターの作り方を誰も知らなかった。そして、まだその実現には程遠い。量子コンピューターが作られる日が来るのか疑問に思う人もいる」とヴァイクンタナサン氏は言う。

ショアのアルゴリズムを実行するには、量子コンピューターに約 2,000 万量子ビットが必要であると推定されています。現在、最大の量子コンピューターには約 1,100 量子ビットが搭載されています。

量子コンピュータは、古典コンピュータが古典回路を使用するのと同じように、量子回路を使用して計算を実行します。各量子回路は、量子ゲートと呼ばれる一連の操作で構成されています。これらの量子ゲートは、量子コンピュータの最小の構成要素である量子ビットを使用して計算を実行します。

しかし、量子ゲートはノイズを発生させるため、ゲートの数を少なくすればマシンの性能は向上する。研究者たちはショアのアルゴリズムを強化して、より少ない量子ゲートでより小さな回路で実行できるように努めてきた。

レゲフ氏が1年前に提案した回路はまさにそれだった。

「これは1994年のショアのサーキットに対する最初の本格的な改良だったので、大きなニュースでした」とヴァイクンタナサンは言う。

ショア氏が提案した量子回路のサイズは、因数分解される数の二乗に比例する。つまり、2,048 ビットの整数を因数分解する場合、回路には数百万のゲートが必要になる。

Regev の回路では必要な量子ゲートの数は大幅に少なくなりますが、十分なメモリを提供するにはさらに多くの量子ビットが必要になります。これにより、新たな問題が発生します。

「ある意味で、ある種の量子ビットはリンゴやオレンジのようなものです。そのままにしておくと、時間の経過とともに劣化します。保存しておく必要のある量子ビットの数を最小限に抑えたいのです」とヴァイクンタナサン氏は説明する。

彼は、昨年 8 月に行われたワークショップで、レゲフ氏がその成果について話すのを聞いた。講演の最後に、レゲフ氏は質問を投げかけた。「誰かが彼の回路を改良して、必要な量子ビットの数を減らすことはできるだろうか?」ヴァイクンタナサン氏とラガバン氏はその質問に取り組んだ。

量子ピンポン

非常に大きな数を因数分解するには、量子回路を何度も実行し、2 の 100 乗のような計算能力を必要とする操作を実行する必要があります。

しかし、量子コンピューターは可逆な演算しか実行できないため、このような大きな累乗を計算するのはコストがかかり、量子コンピューターで実行するのは難しい。数を二乗することは可逆な演算ではないため、数を二乗するたびに、次の二乗を計算するために量子メモリを追加する必要がある。

MIT の研究者たちは、二乗ではなく、可逆な単純な乗算を必要とするフィボナッチ数列を使用して指数を計算する巧妙な方法を発見しました。この方法では、任意の指数を計算するのに 2 つの量子メモリ ユニットしか必要ありません。

「これはピンポンゲームのようなもので、数字から始めて、2つの量子メモリレジスタ間で乗算しながら前後に跳ね返ります」とヴァイクンタナサン氏は付け加えた。

彼らはまた、誤り訂正の課題にも取り組んだ。ショアとレゲフが提案した回路では、アルゴリズムが機能するためにはすべての量子演算が正確であることが必要だとヴァイクンタナサンは言う。しかし、実際のマシンでは誤りのない量子ゲートは実現不可能だろう。

彼らは、不正な結果を除外し、正しい結果のみを処理する技術を使用してこの問題を克服しました。

最終結果は、メモリ効率が大幅に向上した回路です。さらに、エラー訂正技術により、アルゴリズムの導入がより実用的になります。

「著者らは、以前の量子因数分解アルゴリズムにおける 2 つの最も重要なボトルネックを解決しました。まだすぐに実用化できるわけではありませんが、彼らの研究により、量子因数分解アルゴリズムは現実に近づきました」と Regev 氏は付け加えています。

将来的には、研究者たちはアルゴリズムをさらに効率化し、いつかそれを使って実際の量子回路で因数分解をテストしたいと考えています。

「この研究の後に残る疑問は、これが実際に RSA 暗号の解読に近づくことになるのか、ということです。これはまだ明らかではありません。これらの改善は現在、整数が 2,048 ビットよりはるかに大きい場合にのみ有効になります。このアルゴリズムを推し進めて、2,048 ビットの整数に対しても Shor のアルゴリズムよりも実現可能にすることはできるでしょうか?」と Ragavan 氏は言います。

このストーリーはMIT Newsの許可を得て転載したものです（ウェブ.mit.edu/newsoffice/）、MIT の研究、イノベーション、教育に関するニュースを扱う人気サイトです。