本記事は, Yan 等の中国の研究者が 2022 年 12 月に発表した "Factoring integers with sublinear resources on a superconducting quantum processor" というプレプリントを解説した一連の記事の Part 4 です. この論文は QAOA という量子計算を使った新しい素因数分解アルゴリズムを提案しており, その名称を SQIF (Sublinear Quantum Integer Factorization) と呼んでいます. 本記事では SQIF の詳細な処理内容を説明します.
Part 1: 論文の概要
Part 2: 平方差法
Part 3: Schnorr の素因数分解法
Part 4: SQIF の詳細 (この記事)
Part 5: SQIF の実験結果の分析
Part 6: まとめ
アイディア
Schnorr による素因数分解法は格子の最近ベクトル問題 (CVP: Closest Vector Problem) の近似解から拡張関係式を収集しますが, 格子の次数が大きくなると近似解の近似精度が指数的に悪くなるため, 拡張関係式を求めにくくなるという課題がありました.
そこで SQIF は, CVP の求解問題をさらに最適化問題に変換し, QAOA (Quantum Approximate Optimization Algorithm) という量子計算を適用することによって近似精度の良い近似解を求めることを目指します. QAOA は量子計算の一つで, 与えられた多変数多項式の最小値とそれを実現する変数値を出力します. QAOA は量子ビットに対する耐性があることから, NISQ のような現在開発・運用されている量子計算機でも処理可能です.
ただし, SQIF は
仮定
Babai アルゴリズムによって求まる近似解の近傍に最適解(CVPの真の解)が存在する
という仮定を利用している点に注意が必要です. Babai アルゴリズムは与えられた基底ベクトルに LLL アルゴリズムを適用し, その後, 基底ベクトルごとに整数係数を定め、最終結果を CVP の近似解として出力します. 整数係数を定める際には実数値に対する丸め(四捨五入)関数 $\lceil x \rfloor$ を用いるのですが, SQIF は $x$ に最も近い整数 $\lceil x \rfloor$ だけでなく2番目に近い整数も候補として残し, QAOA による量子計算を適用することでより良い近似解を求めようとします.
SQIF の処理内容
それでは SQIF の具体的な処理内容を説明します. SQIF の流れは以下のようになります. (2) の CVP の求解法以外は Schnorr の素因数分解法と同じになっています.
(1) 格子の生成
(2) 拡張関係式の収集 (CVP の求解)
(3) 行列計算
(4) $N$ の因数分解
(1) 格子の生成
素因数分解したい合成数 $N$ と適当な方法で定義された素数の集合 $P= \{ p_1, \dots, p_s \}$ に対し, $s$ 個の基底ベクトル
\mathbb{b}_1 = \begin{pmatrix} f(1) \\ 0 \\ \vdots \\ 0 \\ N^c \log{p_1} \end{pmatrix},~
\mathbb{b}_2 = \begin{pmatrix} 0 \\ f(2) \\ \vdots \\ 0 \\ N^c \log{p_2} \end{pmatrix},~
\dots,
\mathbb{b}_s = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ f(s) \\ N^c \log{p_s} \end{pmatrix}
から生成される格子を考える. ここで関数 $f$ は $\{1,2,\dots,s\}$ 上のランダムな置換である. また実数の定数 $c$ は CVP を適切に解けるようにするためのウェイトであり, 具体的な値は別途定められる.
(2) 拡張関係式の収集 (CVP の求解)
(1) で定義された格子において, ターゲットベクトル
\mathbb{t} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ N^c \log{N} \end{pmatrix}
に対する CVP を解きます. 具体的には
(2-1) 基底ベクトルに対して LLL アルゴリズムを適用する
(2-2) (2-1) で得られた基底ベクトルに対して Babai アルゴリズムを適用し, CVP の近似解 $\mathbb{b}=\sum e_i \mathbb{b}_i$ を求める.
(2-3) ハミルトニアン $H = || \mathbb{t} - \sum x_i \mathbb{b}i - \mathbb{b} ||^2$ を求める.
(2-4) ハミルトニアン $H$ に対して QAOA を適用し, 最適化問題の解を得る.
(2-5) (2-4) で得られた近似解 $\sum x_i \mathbb{b}i$ に対して $u = \prod{x_i>0} p_i^{x_i}$, $v = \prod{x_i<0} p_i^{-x_i}$ と定め, さらに $u-vN$ の素因数分解 $\pm q_1^{f_1} \times \dots \times q_t^{f_t}$ を求める. このとき拡張関係式
\prod_{x_i>0} p_i^{x_i} \equiv \pm q_1^{f_1} \times \dots \times q_t^{f_t} \pmod{N}
を得る.
(3) 行列の計算
得られた拡張関係式から生成されるベクトルを行ベクトルとする行列を生成し, 掃き出し法を適用する.
(4) 素因数分解
(3) で得られた関係式から $N$ の因数を得る.
まとめ
本記事では SQIF の具体的な処理内容を紹介しました. ポイントは CVP の近似解を得るために Babai アルゴリズムの出力からハミルトニアンを生成し, それに QAOA を適用する点です. 数値例は次の記事で紹介します.