Resource-Efficient Digitized Adiabatic Quantum Factorization

技術要約：リソース効率の高いデジタル化された断熱量子因数分解

問題提起
本論文は、デジタル化された（ゲートベースの）量子コンピュータ上で、効率的な断熱量子因数分解を実装するという課題に取り組んでいる。Pengら[1]によって提案された標準的な手法では、整数因数分解を、多項式非制約バイナリ最適化（PUBO）関数から導出された問題ハミルトニアンの基底状態探索として定式化している。この定式化では、3体および4体非局所相互作用（$Z^3$ および $Z^4$）を含むハミルトニアンが生成される。デジタルデバイスにおいて、これらの高次相互作用は複数のネイティブな2量子ビットゲート（例：CNOT）への分解を必要とするため、回路の深さとゲートカウントの増大を招く。この複雑さは、機械学習の手法を用いても、91より大きい数に対して成功確率が劇的に低下するなど、アルゴリズムの忠実度とスケーラビリティを著しく制限している。

手法
著者らは、二次非制約バイナリ最適化（QUBO）フレームワークを用いて因数分解問題を再定式化する、新しいデジタル断熱アルゴリズムを提案している。この核心となる手法の転換には、以下の2つの主要な変更が含まれる。

1. カーネル部分空間エンコーディング： 解を $F^2$ の二乗関数の基底状態（エネルギー最小値ゼロ）としてエンコードする代わりに、著者らは問題ハミルトニアン $\hat{H}_{LP}$ を、線形関数 $F(N, \hat{p}', \hat{q}')$ そのものとして定義する。この定式化において、解はハミルトニアンのゼロエネルギー固有状態（カーネル部分空間）に対応する。これは、グローバルなスペクトルに対しては励起状態となる。
2. QUBO定式化： 線形関数を利用することで、結果として得られるハミルトニアンは2体相互作用のみを含み、QUBO問題として分類される。これにより、PUBO問題をQUBOにマッピングするために通常必要とされるNP困難な多項式簡約や補助変数の必要性が排除される。

このアルゴリズムは、変分量子アルゴリズム（具体的にはQAOA）を用いて実装されている。プロトコルは、システムを一様重ね合わせ状態（具体的には $\hat{H}_{LP}$ の零部分空間に合わせるための $|+\rangle|-\rangle\dots$）に初期化し、コストハミルトニアン（$\hat{H}_{LP}$）と混合ハミルトニアン（$\hat{H}_M$）から導出される交互作用ユニタリを用いて進化させる。古典的最適化器によって最小化されるコスト関数は、ゼロ固有値解への収束を確実にするため、ハミルトニアンの絶対値の期待値 $C_{LP} = \langle |\hat{H}_{LP}| \rangle$ として定義される。

主な貢献

• 回路の簡素化： 提案されたQUBOアプローチは、問題ハミルトニアンを2体相互作用へと削減する。これにより、複雑な多量子ビットゲートの分解が不要となり、回路の深さが大幅に削減される。
• 新しいエンコーディング戦略： 断熱因数分解は、PUBO定式化の限界を回避し、基底状態ではなくカーネル部分空間（ゼロエネルギー励起状態）をターゲットにすることで、正常に実行できることを本論文は示している。
• ロバスト性分析： 著者らはハミルトニアンのスペクトル密度を分析し、QUBO定式化がPUBO定式化と比較して解の周辺における状態密度が疎であることを示しており、これが最適化中の局所解やバレン・プラトー（barren plateaus）の回避に寄دする。

結果
著者らは、最大8ビットの整数（具体的には $N=25, 119, 143$）の因数分解において、提案するQUBOベースのアルゴリズムを標準的なPUBOアプローチと比較検証した。

• ゲート複雑度： QAOA回路の1レイヤーあたり、QUBOアプローチは大幅に少ないCNOTゲートを必要とする。例えば、$N=25$ の因数分解において、PUBO法（3体および4体ゲートの分解後）が34個のCNOTを必要とするのに対し、QUBO法では1レイヤーあたり8個のCNOTで済む。
• 忠実度と信頼度： QUBOアルゴリズムは、正しい因数を特定する上で実質的に高い忠実度を示した。$N=119$ や $N=143$ のような大きな数に対して、PUBO法は正しい解に確率振幅を集中させることができず、結果として低い信頼度スコアと高いシャノンエントロピーをもたらした。対照的に、QUBOアプローチは正しい解の状態に確率を正常に集積させた。
• コスト関数の収束： QUBOアルゴリズムは、PUBOアプローチ（最大2桁の減少）と比較して、より深いコスト関数の減少（最大3桁の減少）を達成しており、より効果的な最適化が行われていることを示している。
• スペクトル分析： エネルギースペクトルの分析により、PUBOハミルトニアンは解の近くに高い状態密度を持ち、古典的最適化器を妨げる「平坦な」ランドスケープを形成していることが明らかになった。一方、QUBOハミルトニアンは、カーネル部分空間付近でより広いエネルギーギャップを持つ、より広く分散したスペクトルを示し、状態準備を容易にしている。

意義と主張
本論文は、この研究がデジタル化された断熱量子因数分解へのリソース効率の高い経路を提供するものであると主張している。主な意義は、回路の複雑さを大幅に削減し、それに伴うアルゴリズムの忠実度を向上させたことにあり、これにより近傍のデバイス上でのより大きな整数の因数分解が可能になる。

著者らは、励起状態（カーネル）をターゲットにすることは、基底状態のデコヒーレンス保護を欠く量子アニーラーにとっては困難であるが、デジタル化された量子アニーラーにとっては有利であると強調している。ゲートベースのシステムにおいては、デコヒーレンスはしば der 局所的な単一量子ビットの減衰によって支配されることが多いため、QUBOアプローチによるゲート数の削減は、総実行時間とエラーへの露出を最小限に抑える。これらの結果は、QU0Bベースの定式化がQAOAベースの最適化においてPUBOベースの定式化を凌駕し得ることを示唆しており、特定の構造に対してPUBOが必要、あるいは優れていると仮定してきた従来の文献に一石を投じるものである。本研究は、より広範な数論的問題や複雑なハミルトニアンに対するデジタル断熱プロトコルのさらなる探求を動機付けるものである。