⚛️ quantum physics

Can PCE solve the factorisation problem via optimisation?

本論文は、量子ビット要件を劇的に削減する手法として、パウリ相関符号化（PCE）アルゴリズムを整数因数分解問題に適応させることの実現可能性を検討するものであり、計算上の優位性を主張することなく、近未来の量子ハードウェアに対するその潜在性と限界についての予備的な分析を提供するものである。

原著者： Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

公開日 2026-07-28

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、銀行口座やメール、そしてオンラインで行うほぼすべての活動を守っている秘密のコードを解読しようとしているところだと想像してみてください。このコードは、シンプルですが巧妙な数学のゲームに基づいています。それは、2つの巨大な素数（1とその数自身でしか割り切れない数）を取り、それらを掛け合わせ、その結果を世界に公開するというものです。それらを掛け合わせるのは簡単ですが、もし最終的な巨大な数だけを与えられた場合、どの2つの素数がその数を作り出したのかを突き止めるのは、ケーキを「逆焼き」して、正確に何個の卵と何杯の小麦粉が使われたかを見つけ出すようなものです。現在のコンピュータにとって、これはほぼ不可能です。これが「整数因数分解」問題であり、現代のデジタルセキュリティの根幹となっています。

ここで、単に計算するだけでなく、量子力学の奇妙な法則を利用して、多くの可能性を一度に探索する新しい種類のコンピュータを想像してください。科学者たちは、この「逆焼き」問題を解くように量子マシンを教えようと試みてきました。ピーター・ショアによって考案された有名な手法は、理論的には完璧ですが、私たちがまだ構築できる技術を持っていないほど強力で静かな量子コンピュータを必要とします。そのため、研究者たちは「量子に着想を得た（quantum-inspired）」ショートカット、つまり、現在私たちが持っているノイズが多く不完全なマシンでも実行できる、少しの量子の魔法を用いた手法を探しています。大きな疑問は、「この巨大な数学の問題を、初期の量子コンピュータが実際に解けるような、小さく管理可能なパズルへと押し込めることができるか？」ということです。

この論文は、**パウリ相関エンコーディング（PCE）**と呼ばれる巧妙な新しいトリックを用いて、まさにその問いを探求しています。PCEを、超効率的な圧縮アルゴリズムだと考えてください。通常、多くの変数（巨大な数のビットのようなもの）を持つ複雑な問題を表現するには、膨大な数の量子ビット（qubit）が必要です。PCEは魔法のジッパーのように機能し、研究者が数千の変数をより少ない数の量子ビットの中に詰め込むことを可能にします。著者であるフェルナンド・アロンソ氏とガリシア・スーパーコンピューティング・センターのチームは、「もしこのジッパーを使って因数分解問題を圧縮できたら、最適化手法を用いて答えを見つけることができるだろうか？」と問いかけました。

彼らはただ推測したわけではありません。探索を導くために2つの異なる「地図」を構築しました。最初の地図である**基本アプローチ（Basic approach）**は、2つの素数のバイナリコードを直接推測することで因数を見つけようとするものでした。彼らはこれを最大25ビットの数でテストしました。結果はやや芳しくありませんでした。小さな数に対してはうまく機能しましたが、数が大きくなるにつれて成功率は低下し、コンピュータはしばしば「自明な」解（例えば、ある数を自分自身と1の積であると言うようなこと）に陥ってしまいました。

2つ目の地図であるDoTS（Difference of Two Squares：二乗の差）は、より賢い戦略でした。因数を直接探すのではなく、二乗の差がターゲットとなる数の倍数になるような2つの数を探しました。これは、2人の人物が体重計の上に立ったとき、その体重差が特定のパターンに完璧に一致するような人を見つけるようなものです。このアプローチははるかに成功しました。シミュレーションにおいて、DoTS法は36ビットまでの数を正常に因数分解することに成功しました。

チームは、この地図をナビゲートするために3つの異なる「検索エンジン（オプティマイザ）」を使用しました：差分進化戦略（DE）、粒子群最適化（PSO）、そして量子に着想を得たQDPSOです。結果は、DEオプティマイザが明確な勝者であり、他の手法が苦戦する場面でも一貫して正しい答えを見つけたことを示しました。

しかし、著者たちは自分たちがコードを「破った」と主張しないよう、非常に慎重になっています。彼らの手法は、他の量子アプローチよりもはるかに少ない量子ビットを使用しているため（現在のハードウェアでの実行が可能になります）、依然として古典的なコンピュータ上で実行されているシミュレーションであることを強調しています。彼らは、数理的な問題をより効果的に捉えるためには、現在の「コスト関数（コンピュータに書いたルールブック）」を書き直す必要があることを示唆しながら、現在の方法では40ビットを超える数に対しては失敗し始めることも明らかにしました。また、もしこれを実際の量子ハードウェア上で実行した場合、ノイズがコンピュータが袋小路から脱出するのを助けることもあれば、計算を台無しにする可能性もあることも指摘しています。

要約すると、この論文は、PCEが因数分解問題をより小さく、より管理しやすいものにするための有望なツールであることを示唆しています。これは現実世界の暗号で使用される巨大な数を解くものではありませんが、新しい扉を開いています。適切な圧縮と適切な探索戦略があれば、量子コンピュータが予想よりも早く本格的な数値計算を行うことができる可能性があることを、たとえ世界で最も大きなケーキを「逆焼き」できるようになるまでには、まだ長い道のりがあったとしても、示しているのです。

技術要約：PCEは最適化を通じて因数分解問題を解決できるか？

問題提起
整数因数分解、特に半素数（ $N = p \cdot q$ ）の因数分解は、計算数論における基礎的な問題であり、RSA暗号のセキュリティの根拠となっている。ショアのアルゴリズムは多項式時間での量子解法を提供するが、現在のNISQ（Noisy Intermediate-Scale Quantum）ハードウェアは、実用的な実装に必要な量子ビット数やコヒーレンスを欠いている。変数のバイナリ数に対して量子ビット数が線形にスケールするという課題を抱える、因数分解をバイナリ最適化問題へと変換する変分量子アルゴリズム（VQA）のような代替手法も存在する。この線形スケーリングにより、大規模なインスタンスへの適用は困難となっている。本論文では、 $m$ 個のバイナリ変数を、多項式個の量子ビット（ $n \ll m$ ）を用いてエンコード可能なフレームワークである**パウリ相関エンコーディング（Pauli Correlation Encoding: PCE）**を、限られたリソースを用いた最適化による因数分解問題に適応できるかどうかを調査している。

手法
本研究では、因数分解問題をバイナリ最適化タスクとして再定式化し、量子ビット数を削減するためにPCEを適用している。手法には以下のプロセスが含まれる：

エンコーディング戦略： 因数分解の制約をコスト関数にマッピングするために、2つの異なるアプローチを開発した。
- 基本アプローチ（Basic Approach）： 未知の因数 $p$ および $q$ のバイナリ表現を直接エンコードする。コスト関数は、ターゲットとなる整数 $N$ と候補の積 $x_p \cdot x_q$ との間の二乗ハミング距離を最小化し、自明な解（例： $N \cdot 1$ ）を避けるためのペナルティを加える。
- 二乗の差（DoTS）アプローチ： 問題を、 $a^2 \equiv b^2 \pmod N$ （ただし $a \not\equiv \pm b$ ）を満たす整数 $a$ と $b$ を見つける問題へと再定式化する。因数は $\gcd(a-b, N)$ および $\gcd(a+b, N)$ を通じて回収される。コスト関数は、モジュロ合同式を強制する項と、結果としての因数分解を検証する項を組み合わせる。
量子回路： 単一量子ビット回転（ $R_X, R_Y, R_Z$ ）と絡み合いゲート（ $R_{XX}, R_{YY}, R_{ZZ}$ ）が交互に現れる、ハードウェア効率的な「ブリックワーク（brickwork）」アンザッツを採用した。PCEの圧縮次数 $k$ が、回路の深さと必要な量子ビット数（ $n \approx m/k$ ）を決定する。
最適化： パラメータ化された量子回路は、Qiskit Aerを用いて古典的にシミュレートされた。最適化には、差分進化法（DE）、粒子群最適化（PSO）、および量子デルタ粒子群最適化（QDPSO）の3つの勾配フリーアルゴリズムを用いた。実数値解が無限大になるのを防ぐため、双曲線正接（hyperbolic tangent）による緩和ではなく、符号関数（sign function）を用いてバイナリ変数を近似した。

主な貢献と結果

リソース削減： 本研究は、PCEが因数分解に必要な量子ビット数を劇的に削減できることを示している。典型的なRSA鍵長に対して、必要な量子ビット数は現在または近未来のハードウェアで「入手可能」な範囲内に収まり、 $k > 2$ の圧縮次数では、量子回路のエミュレーションを通じて問題全体を古典コンピュータ上で解決できる。
性能比較：
- DoTS vs. 基本アプローチ： DoTSアプローチは、一貫して基本アプローチよりも優れた性能を示した。DoTSのコスト関数は、二乗の差の関係の算術構造を捉えており、より高い成功率とより好ましい最適化ランドスケープをもたらした。
- 最適化手法の感度： 差分進化法（DE）が最も堅牢な最適化手法であることが証明され、様々なビット長にわたって成功裏に因数分解を達成した。群ベースの手法（PSO, QDPSO）は成功率が著しく低く、最適化のランドスケープがこれらの特定のアルゴリズムにとって困難であることを示唆している。
- スケーラビリティの限界： 本手法は、DoTSアプローチとDEを用い、 $k=4$ の条件下で36ビットまでの半素数の因数分解に成功した。25〜36ビットを超える整数に対しては成功率が低下しており、これは大規模なインスタンスに対する現在のコスト関数定式化の固有の限界を示している。
探索効率： 目的関数の評価回数の分析により、本アルゴリズムが総当たり探索に依存していないことが示された。評価回数は組合せ探索空間のサイズ（ $2^n$ ）よりも数桁低く抑えられており、誘導された探索プロセスであることを示している。

意義と主張
本論文は、本研究を決定的な解決策や既存アルゴリズムに対する計算上の優位性の主張ではなく、予備的かつ探索的な貢献として位置づけている。

実現可能性： 主要な知見は、PCEベースのアルゴリズムが、限られた量子リソースを用いて因数分解を最適化問題として研究するための妥当なフレームワークであるということである。これは、変数の数と量子ビット数を切り離すことで、VQFやQAOAといった確立された手法に対する代替的な視点を提供する。
限界： 著者らは、現在の定式化が暗号学的に重要な整数サイズ（例：2048ビットRSA）に対しては成功裏にスケールしないことを明示している。本手法の成功は、古典的なコスト関数の設計と最適化手法の選択に強く依存している。
今後の方向性： 本研究は、以下の事項に焦点を当てた将来の研究を提案している：
- （キャリー変数を組み込むなど）因数分解の算術構造をより良く捉える、より情報量の多いコスト関数の設計。
- 変数数を削減するための、バランスの取れた因数仮定（RSAで一般的）の探索。
- ウォームスタート戦略および代替アンザッツ・アーキテクチャの調査。
- 現実的なノイズモデル下での性能評価。

結論として、本手法は現在、RSAのセキュリティを脅かすものではないが、量子に着想を得た最適化による因数分解を調査するための、リソース効率の高い実行可能なフレームワークを確立しており、コスト関数の設計とアルゴリズムの洗練に関するさらなる研究の価値がある。

技術要約：PCEは最適化を通じて因数分解問題を解決できるか？

関連論文