ゴールデンウィークの自由研究として, Yan 等の中国の研究者グループが 2022 年 12 月に発表した "Factoring integers with sublinear resources on a superconducting quantum processor" という論文 (プレプリント) を 6 回に分けて解説します. この論文は QAOA という量子計算を使った素因数分解アルゴリズム SQIF (Sublinear Quantum Integer Factorization) を提案しています. 初回である本記事では SQIF の背景と, SQIF の主張内容とその評価を概観します.
Part 1: 論文の概要 (本記事)
Part 2: 平方差法による素因数分解
Part 3: Schnorr の素因数分解法
Part 4: SQIF の詳細
Part 5: SQIF の数値実験の分析
Part 6: まとめ
更新履歴
- 2023年5月29日：Typo を修正するとともに、わかりにくい部分を変更しました。
- 2023年5月8日：一連の記事へのリンクを追加しました。また各記事の用語やトーンを揃えるため、全体的に加筆変更しました。
背景
SSL/TLS などで広く使用されている RSA 暗号・RSA 署名は巨大な合成数の素因数分解が難しいという性質を利用しており, RSA 暗号・RSA 署名を安全に使用するには, すぐには素因数分解できないような巨大合成数を鍵として設定する必要があります. 古典計算機を用いた素因数分解の世界記録は 829 ビット合成数の素因数分解であるため, RSA 暗号・RSA 署名を安全に使用する場合, マージンを考えて 2048 ビット以上の合成数を鍵として設定します.
他方で, 理想的な量子計算機を用いた場合, Shor アルゴリズムを利用することで素因数分解が劇的に簡単になります. ただし Shor アルゴリズムは合成数 $N$ を素因数分解するのに $O(\log{N})$ 個の量子ビットを必要とするので, 2048 ビット合成数を素因数分解するには数千量子ビットが必要となり, さらには量子ビットの誤りエラーを許容しないため, 量子計算機で 2048 ビット合成数が素因数分解できるのはまだまだ先の話だと思われてきました.
ところが 2022 年の 12 月に Yan 等の中国人研究者グループが発表したSQIF という素因数分解アルゴリズムは驚くべきものでした. 素因数分解問題を最適化問題に変換し, それを QAOA (Quantum Approximate Optimization Algorithm) という量子計算によって解くことで素因数分解が可能になることを示しました. また必要な量子ビット数は $O(log{N}/\log \log{N})$ という劣線型 (sublinear) であることも示したため, 従来よりも少ない量子ビット数で 2048 ビット合成数の素因数分解になるのではないかという期待/不安が高まりました.
メディアの反応
このように SQIF の提案論文はセキュリティに大きなインパクトを与える内容だったため, 海外のメディアから大きな注目を集めました.
- The Record: Chinese researhers claim to have broken RSA with a quantum computer. Experts aren't so sure. (Jan 4, 2023)
- Financial Times: Chinese researchers claim to find way to break encryption using quantum computers (Jan 7, 2023)
- The Register: Chinese researchers' claimed quantum encryption crack looks unlikely (Jan 7, 2023)
- Forbes: Did China Break The Quantum Barrier? (Jan 10, 2023)
これに対し日本のメディアは反応が鈍く, オリジナルな記事はほとんど見かけませんでした.
- 日経新聞: 中国研究者、量子コンピューターで「暗号解読」主張 (Jan 6, 2023) [Financial Times 記事の翻訳]
- Forbes Japan: 中国が量子コンピュータで「暗号の壁」を破る？ (Jan 13, 2023) [Forbes 本紙の記事の翻訳]
- Gigazine: 量子コンピューターは既にRSA暗号を解読できると中国人研究者が主張も専門家からは「誤解を招く論文」「そんなに楽じゃない」との指摘も (Jan 13, 2023)
識者の反応
暗号や量子計算の研究者等はブログやSNSを通じてコメントを発表しました.
- Peter Shor: "There are apparently possible problems with this paper." (Dec 28, 2023)
- Bruce Schnier: "I am much less worried that this technique will work now. But this is something the IBM quantum computing people can test right now." (Jan 3, 2023)
- Scott Aaronson: "No. Just No." (Jan 4, 2023)
- Michael Mosca: "Do'nt panic" (Jan 7, 2023)
https://www.linkedin.com/feed/update/urn
activity:7016808281847336960/
これらコメントは端的でわかりやすいのですが, 反面でなぜそのような結論に至ったのかがよくわかりません. 本記事を執筆する目的の一つは, これらコメントの意味を理解できるようになることだと考えています.
論文の概要
それでは肝心の論文の主張を確認していきます.
(1) SQIF (Sublinear-resource Quantum Integer Factorization) という新しい素因数分解アルゴリズムを提案する.
(2) SQIF は古典計算と量子計算のハイブリッドであり, 古典計算には Schnorr による素因数分解法, 量子計算には QAOA (Quantum Approximate Optimization Algorithm) を用いる.
(3) 合成数 $N$ を素因数分解するのに必要な量子ビット数は $O(\log{N}/\log \log{N})$ となる. これは $N$ のサイズの劣線型 (sublinear) であり, 従来の量子素因数分解アルゴリズムに比べて優れている.
(4) 超伝導素子による量子計算機において実験を行い, 以下の合成数の素因数分解に成功した:
- $N=1961$ (11ビット合成数): 3量子ビットを使用
- $N=48567227$ (26ビット合成数): 5量子ビットを使用
- $N=261980999226229$ (48ビット合成数): 10量子ビットを使用
(5) SQIF を 2048 ビット合成数に適用した場合に必要な量子ビット数を見積もり, 372 物理量子ビットが必要であることを明らかにした.
こう書かれてもポカンだと思いますので, これら主張の意味するところを以下で詳しく見ていきます.
(1) は名称に関する話なので, 特に言うことはありません.
(2) で言っている古典と量子のハイブリッドという話も珍しいものではありません. 例えば, これから比較対象として何回も登場しますが, 量子素因数分解アルゴリズムとして有名な Shor アルゴリズム はもともとは元の位数を計算するアルゴリズムなので, Shor アルゴリズムの前後に古典計算を付け加えてハイブリッドにすることで, 素因数分解を実現しています.
他方で, 量子アルゴリズムとして QAOA という最適化アルゴリズムを用いる点はとても特徴的です. QAOA は量子ビットにエラーがあってもそれなりに動作するため, NISQ のような現在の量子計算機でも利用できるからです. (これに対し Shor アルゴリズムは量子ビットのエラーへの耐性が低いことが知られており, NISQ に Shor アルゴリズムを実装しても正しい答えを求めることは困難です.)
(3) は SQIF が必要とする量子ビット数が劣線型 (sublinear) になることを言っています. 従来の量子素因数分解アルゴリズムである Shor アルゴリズムは線型 (linear) の量子ビット数 $O(\log N)$ を必要とするので, この点で SQIF は Shor アルゴリズムよりも優れています. 合成数 $N$ を量子計算機に記憶させるには $O(\log N)$ 量子ビットが必要になるので, SQIF は合成数 $N$ 自身を記憶せずに素因数分解を実現していることがわかります. この劣線型という性質のすごさが故に論文名や素因数分解名にも sublinear という単語が使用されています.
(4) の実験結果は SQIF が量子計算機上で正しく動作することを検証しており, それはそれで素晴らしい結果なのですが, それ以上に注目すべきは素因数分解できている合成数の大きさです. 量子計算機を用いたこれまでの素因数分解実験では, $N=15, 21$ を素因数分解するのがやっとだったのに対し, この実験では $N=1961, 48567227, 261980999226229$ という合成数の素因数分解に成功しており, 量子計算機による素因数分解記録も大きく更新しています. (ただし後で説明するように SQIF 全体に対する量子計算の割合はごくわずかなので, このように比較して良いかについては議論の余地があります.)
(5) の見積もり結果もセンセーショナルで, 372物理量子ビットの NISQ を用いれば 2048 ビット合成数が可能になるかもしれないことを示唆しています. 実際, IBM が 2022 年 9 月に発表した Osprey という量子プロセッサは 433 物理量子ビットが処理可能なので, スペックだけを見ればすぐにでも 2048 ビット合成数が素因数分解できる錯覚に陥ってしまいます.
論文の評価
このように SQIF は発表直後は大きな話題になりましたが, 主張に対する肯定的な評価はほとんど見かけません. 確かに SQIF は実験では期待通りに動作しているのですが, QAOA は大きなパラメータに対しては近似解の精度が劣化することから, SQIF は大きな合成数に対しては期待通りには動作しないだろうと予測されているからです. また, 論文の細かな主張にもさまざまな疑問があるため, 現状では, 量子計算機による素因数分解が簡単になったとは言えない状況です. せめてもっと大きな合成数の素因数分解に成功しないと世間は受け入れてもらえないのではないかと思います.
論文に対する疑問
SQIF の主張の正当性を示すには, QAOA 以外にも以下の疑問を解消する必要があると (@izutetsuya は) 考えます.
a. 仮定の妥当性：SQIF の提案論文では QAOA を適用する問題に対する仮定を設定しているので, その証明 (妥当性) が必要です.
b. QAOA の性能評価：前述したように QAOA はパラメータサイズが大きくなると解の精度が劣化します. このため, 少なくとも SQIF が扱う最適化問題に対し, 精度を評価する必要があります.
c. LLL アルゴリズムの影響評価：SQIF は内部的に LLL アルゴリズムを使用するのですが, この LLL アルゴリズムはパラメータが大きくなると近似精度が劣化することが知られており, 大きな合成数に対しては期待通りには動作しない可能性が高いので, 成功確率を見積もる必要があります.
d. 収集すべき拡張関係式の個数の評価：SQIF は, Schnorr の素因数分解における「拡張関係式」と呼ばれるデータを大量に収集するステップを QAOA によって代替します. この「拡張関係式」は合成数のサイズに応じて数十個から数百個が必要なのですが, SQIF によって求められる拡張関係式は数個に留まっており, 残りの拡張関係式は他の(おそらく古典的な)方法によって収集されています. したがって, 拡張関係式の収集ステップに対する QAOA の効果を明らかにする必要があります.
e. 計算量評価: SQIF の計算量の算出が必要です. (もっとも, SQIF が利用している Schnorr の素因数分解法も計算量が明らかになっていないのですが)
f. 量子計算の必然性の評価: SQIF は QAOA によって最適化問題を解くことで拡張関係式を収集していますが, 他の最適化問題のソルバーを利用できるかどうかについての言及がありません. 仮に古典的(非量子的な)ソルバーでも処理できるのであれば, SQIF が主張する量子性は必然ではない可能性があります.
まとめ
QAOA を用いた素因数分解法の概要を紹介しました. 論文では, 48 ビット合成数が10量子ビットによって素因数分解できた, や, 2048 量子ビット合成数は 372 物理量子ビットの NISQ で処理可能, と主張されており, とてもインパクトのある内容なのですが, 現状ではそれを裏付ける十分な証拠が追いついていないという状況です.
本記事は SQIF の概観の紹介を目的としたため, SQIF の詳細には立ち入りませんでした. しかし上記の疑問の意味するところを理解するには SQIF の処理内容を把握する必要がありますので, 次の記事からは各ステップを紹介していきます.