本記事は, Yan 等の中国の研究者が 2022 年 12 月に発表した "Factoring integers with sublinear resources on a superconducting quantum processor" というプレプリントを解説した一連の記事の Part 6 (最終回) です. この論文は QAOA という量子計算を使った素因数分解アルゴリズムを提案しており, その名称を SQIF (Sublinear Quantum Integer Factorization) と呼んでいます. 本記事では SQIF に関する疑問をまとめます.
Part 1: 背景
Part 2: 平方差法による素因数分解
Part 3: Schnorr の素因数分解法
Part 4: SQIF の詳細
Part 5: SQIF の数値実験の分析
Part 6: まとめ (この記事)
SQIF の概要
SQIF は, Schnorr の素因数分解法が拡張関係式を求める際に Babai アルゴリズムによって CVP の近似解を求めた後に, Schnorr の enumeration algorithm によってより良い近似解を探索する部分を, QAOA によって近似解の近傍からより良い近似解を探索するように変更した素因数分解法です. CVP を最適化問題に変換するために「Babai アルゴリズムの解の近傍により良い近似解が存在する」という仮定を利用しています.
疑問
a. 仮定の妥当性
SQIFは「Babai アルゴリズムの解の近傍により良い近似解が存在する」という仮定を利用しているのですが, この仮定の証明(あるいは妥当性の検証)は必須です. 特に, Schnorr の enumeration algorithm では求まることがないかどうかの議論は欠かせないと思います.
b. QAOA の性能評価
QAOA はパラメータサイズが大きくなるにつれて精度が悪くなるため, (少なくとも SQIF で利用するハミルトニアンに関して) パラメータサイズが精度に与える影響を調べる必要があります.
c. LLL アルゴリズムの影響評価
Babai アルゴリズムに対する LLL アルゴリズムの影響評価も必要だと思います (理屈の上では SQIF が利用する格子に限定した場合に何かが言えてもおかしくないのですが, 実際には難しいでしょうねぇ)
d. 収集すべき拡張関係式の個数の評価
SQIF の場合, $|u-vN|$ に登場する素数の個数が多くなりがちなので,素因数分解に必要となる拡張関係式の個数評価も必要でしょう.
e. 計算量評価
そして何よりも SQIF の計算量評価が必要でしょう. QAOA を使っている以上, 厳密な計算量評価は難しいのかもしれませんが, せめて解くべき CVP の個数くらいは知りたいものです.
f. SQIF は量子アルゴリズムなのか？
一番の疑問は, SQIF は量子アルゴリズムなのか？という点です. もちろん QAOA を使っているので量子アルゴリズムなのですが, SQIF の処理内容を分析していくと, 要は最適化問題が解ければ良いのであって, そのソルバーが QAOA に限定される理由はありません (むしろ, この形のハミルトニアンであれば他のソルバーも使えると思います). QAOA 以外のソルバーで素因数分解できるのであれば、ただの古典的な素因数分解アルゴリズムと呼ぶべきなのでしょう.
仮に QAOA の利用が必然であったとしても, SQIF は数個の拡張関係式を見つけるのがやっとなので, それ以外の大多数の拡張関係式は古典的な手法に頼ることになるわけですが, その場合に SQIF を量子アルゴリズムと呼ぶのは個人的には抵抗があります. まあ, この辺は用法の問題なので...
まとめ
6 回に渡って "Factoring integers with sublinear resources on a superconducting quantum processor" という論文の内容を紹介しました. 誤解や typo をご指摘いただけるとうれしいです.