From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

技術要約：周期探索から格子サンプリングへ

問題提起
ショアのアルゴリズムは、理論的には整数因分解を多項式時間で解決するが、現在のNISQ（Noisy Intermediate-Scale Quantum）ハードウェアにおける実装は、回路の深さ、ゲート誤差、およびデコヒーレンスによって厳しく制約されている。これらの制限により、周期探索という1次元の問題ではなく、高次元の格子サンプリング・タスクとして問題を再定式化するレゲブのアルゴлоリズムのような、代替となる因分解アルゴリズムへの関心が高まっている。しかし、既存の実験的解析の多くは、異なるアルゴリズム構造が現実のハードウェアノイズとどのように相互作用するかを理解するための、厳密に制御された条件下での体系的なマルチバックエンド比較を欠いている。本研究は、ショアのアルゴリズムとレゲブのアルゴリズムを実際の量子ハードウェア上で実験的に比較することで、それらの相対的な堅牢性と失敗モードを特性化し、この空白を埋めるものである。

手法
著者らは、ベンチマーク・インスタンス $N = 15$ を用いて制御された実験的研究を行った。両アルゴリズムはQiskitを用いて実装され、CESGA（Centro de Supercomputación de Galicia）のQMIO量子コンピュータと、IBMのオープンアクセス量子プロセッサ（ibm_torino）という2つの異なる量子バックエンド上で実行された。理想的（無ノイズ）なシミュレーションが参照ベースラインとして使用された。

• アルゴリズム構成:
  • ショアのアルゴリズム: 基数 $a=2$、制御レジスタ $k=3$ 量子ビットを使用し、位数 $r=4$ を求める。回路は、回路の深さを最小限に抑えるために、一般的な算術演算ではなく置換に基づく特殊な浅い剰余冪乗構成を利用している。
  • レゲブのアルゴリズム: 2次元インスタンス（$d=2$）、基数 $a_1=4, a_2=49$ として構成。$\mathbb{Z}^d$ 上のガウス型重ね合わせを用いた後、双対格子のベクトルを近似するためにフーリエ・サンプリングを用いている。
• コンパイルと実行: 回路は、各バックエンドのネイティブゲートセットと接続性に合わせてパラメータを調整したQiskitを用いてトランスパイルされた。すべてのハードウェア実行では4,046ショットが使用された。
• 評価指標: 全ての実行に対して完全な古典的再構成を行うことなくノイズの影響を定量化するために、著者らは分布ベースの指標を導入した：
  • シャノン・エントロピー ($H(p)$): 確率分布の分散を測定する。
  • 有効サポートサイズ ($N_{eff}$): 分布に大きく寄与しているアウトカムの数を推定する。
  • Top-K Mass ($M_4$): 最も頻度の高い4つのアウトカムに含まれる全確率の割合。

主な貢献

1. 制御された実験的ベンチマーク: 本論文は、複数のハードウェアプラットフォームおよび理想的なシミュレーションにわたって、同一の問題インスタンス（$N=15$）におけるショアのアルゴリズムとレゲブのアルゴリズムの直接的な低レベル比較を提供している。
2. マルチバックエンド評価: IBMおよびQMIOデバイスの両方について結果を報告しており、異なるハードウェアアーキテクチャがアルゴリズムの性能にどのように影響するかについての洞察を提供している。
3. 情報符号化の解釈: 著者らは、実験結果を「情報の集中」（ショア）対「情報の分布」（レゲブ）という観点から解釈している。これは、構造的な違いがいかにして測定ヒストグラムにおける質的に異なるノイズ誘発型の劣化をもたらすかを実証している。
4. 再現性: 著者らは、実験的な分布を生成するために使用された具体的なアルゴリズムパラメータとコンパイル・パイプラインを報告している。

結果
実験データは、NISQの制約下における2つのアルゴリズムの明確な失敗モードを明らかにしている：

• ショアのアルゴリズム（情報の集中）:

  • 理想的なシミュレーションでは、確率質量は少数のスペクトルピークに高度に集中している（低エントロピー、$N_{eff} \approx 4$、$M_4 = 1.0$）。
  • IBMハードウェア上では、分布は広がるものの主要なピークは保持されており（$M_4 = 0.921$）、位数の部分的な復元が可能である。
  • よりノイジーなQMIOデバイスでは、スペクトルのピークが著しく平坦化し、不明瞭になっており（$M_4 = 0.564$、$N_{eff} \approx 7.8$）、古典的な再構成に必要な周期構造の喪失を招いている。
  • 観察: ショアのアルゴリズムは位相誤差に対して非常に敏感であり、一度鋭いピークがノイズによって広がると、アルゴリズムは有用な情報を提供できなくなる。

• レゲブのアルゴリズム（情報の分布）:

  • 理想的なシミュレーションでは、分布は本質的にショアよりも分散しているが、依然として双対格子と一致する一連の支配的なベクトルを示す（$N_{eff} \approx 2.34$、$M_4 = 0.944$）。
  • IBMハードウェア上では、分布はより拡散するが（$M_4 = 0.645$）、一部のアウトカムが格子簡約をサポートするのに十分なほど支配的なまま残っている。
  • QMIOでは、幾何学的な信号が強く希釈され（$M_4 = 0.29$、$N_{eff} \approx 15.8$）、確率質量が多くのベクトルに一様に広がり、格子構造を事実上覆い隠してしまう。
  • 観察: レゲブのアルゴリズムは、複数の相関したサンプル間の統計的バイアスに依存している。回路の深さはより浅いものの（表2によれば、レゲブのコンパイル後の深さは両方のプラットフォームでショアよりも低い）、多次元サンプリング段階がノイズ感受性を導入し、幾何学的信号の急速な分散を引き起こしている。

• 回路の深さと堅牢性: レゲブのアルゴリズムは、コンパイル後の回路の深さがより浅いにもかかわらず（例：IBMにおいて147対210）、この削減は現在のハードウェアにおける優れた堅牢性にはつながらなかった。測定分布は、ノイズの下でショアよりも急速に分散した。

意義と主張
本論文は、現在のNISQデバイスにおける小さな $N$ の領域（$N=15$）において、どちらのアルゴリズムも他方に対して実用的な優位性を示さないことを控えめに主張している。代わりに、本研究は根本的なトレードオフを浮き彫りにしている：

• ショアのアルゴリズムは、ノイズが低い場合には高度に構造化され、集中した出力を得るが、位相コヒーレンスが失われると壊滅的に失敗する。
• レゲブのアルゴリズムは、情報を高次元空間に分布させる。これはより大きな問題に対して異なるスケーリング特性を提供する可能性があるが、現在は多次元サンプリングにおけるノイズへの感受性の増大に苦しんでいる。

著者らは、これらの結果が実験的なベンチマーキングの価値を強調していると結論付けている。彼らは、フォールトトレラントな設定における漸近的な関係が、NISQハードウェアにおける同様の挙動を保証するわけではないことを強調している。そこでは、算術情報の特定の符号化（集中か分布か）が、ノイズがどのように現れ、アルゴリズムがどのように失敗するかを決定づけるのである。今後の課題として、より大きな $N$ への拡張や、これらの特定のトレードオフを対象とした誤差緩和戦略の探索が提案されている。