The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

技術的要約：The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem.

問題設定

本論文は、有限アーベル群における**状態隠れ部分群問題（State Hidden Subgroup Problem: StateHSP）**を扱っている。これは、ショアの因数分解アルゴリズムやサイモンの問題の基礎となる標準的な隠れ部分群問題（HSP）の量子的な一般化である。

標準的なHSPでは、アルゴリズムは、部分群 $H$ によってコセット（剰余類）上で一定であり、それ以外では異なる値をとるオラクル $f: G \to X$ をクエリする。StateHSPでは、この「隠蔽関数」が未知の量子状態 $|\phi\rangle$ と群 $G$ のユニタリ表現 $R$ に置き換えられる。目標は、以下の条件を満たす隠れた部分群 $H \le G$ を特定することである：

1. 対称性: すべての $h \in H$ に対して $R(h)|\phi\rangle = |\phi\rangle$。
2. ギャップ: すべての $g \in G \setminus H$ に対して $|\langle\phi|R(g)|\phi\rangle| \le 1 - \epsilon$。ここで $\epsilon \in (0, 1]$ は既知の約束されたギャップである。

本論文は、2つの異なる入力アクセスモデルの下での複雑さを調査している：

1. サンプル・モデル (Sample Model): アルゴリズムは、$t$ 個の独立した状態 $|\phi\rangle$ のコピーにアクセスできる。
2. クエリ・モデル (Query Model): アルゴリズムは、状態準備ユニタリ $U_\phi$（$U_\phi|0\rangle = |\phi\rangle$）およびその逆行列 $U_\phi^\dagger$ へのコヒーレントなアクセスを持つ。

既存の文献では、サンプル・モデルにおいて $O(\log(|G|)/\epsilon)$ コピーという上界が確立されていたが、$\epsilon$ に対する最適な依存関係や、隠れた部分群のサイズ $|H|$ が複雑さに影響を与えるかどうかが未解決のまま残されていた。さらに、StateHSPに対するクエリ複雑性は研究されていなかった。

手法

著者らは、量子アルゴリズムの手法、情報理論的な下界、およびアドバーサリ（敵対者）引数を組み合わせて用いている。

1. アルゴリズムの枠組み（上界）:
核となる戦略は、双対部分群 $H^\perp$ の要素を生成するための弱フーリエサンプリング (weak Fourier sampling) である。アルゴリズムは、これまでに発見された生成元のスパン（張る空間）に含まれない要素（span-increasing generators）を収集するプロセスを繰り返し、$H^\perp$ が完全に張られるまで継続する。その後、$(H^\perp)^\perp = H$ を用いた古典的な後処理によって $H$ を復元する。

• 適応的停止戦略 (Adaptive Stopping Strategy): $|H|$ が未知である場合の $O(\log |G|)$ のオーバーヘッドを避けるため、著者らは適応的な予算メカニックを導入している。アルゴリズムは小さな反復予算から開始し、新しい span-increasing な生成元が見つかるたびに予算を増やしていく。これにより、複雑さは $|G|$ ではなく $\log(|G/H|)$ にスケールするようになる。
• サンプル・モデルの実装: アルゴリズムは $|\phi\rangle$ のコピーに対して弱フーリエサンプリングを行う。主要な補題（補題 3.7）は、現在のスパン $K^\perp$ が $H^\perp$ の真の部分群である場合、$H^\perp \setminus K^\perp$ の要素をサンプリングする確率が少なくとも $\epsilon/2$ であることを確立している。これにより、$O(1/\epsilon)$ 回のサンプリングを繰り返すことで、高い確率で新しい生成元が見つかる。
• クエリ・モデルの実装: 著者らは $U_\phi$ と $U_\phi^\dagger$ をコヒーレントに実行できる能力を活用する。彼らは、現在のスパン $K^\perp$ の外側にあるフーリエサンプルをフラグ立てする部分空間識別子 (subspace identifier)（ユニタリ $U_\perp$）を構築する。このフラグ立てにより、新しい生成元を見つける確率を $\epsilon/2$ から 1 に近くまで高めるために、固定点振幅増幅（fixed-point amplitude amplification、GilyénらやYoderらの手法に着想）を用いることが可能となり、これには $O(1/\sqrt{\epsilon})$ クエリのみを要する。

2. 下界の手法:

• クエリ下界: 著者らはアドバーサリ法（具体的にはBelovsによる相対 $\gamma_2$ ノルム定式化）を使用する。彼らは「分数パディングされたサイモン問題 (Fractional Padded Simon's)」の状態の族を構築する。サイモン問題を $|H|$ を変化させるようにパディングし、オラクルの差を $\sqrt{\epsilon}$ で再スケールする分数オラクルを導入することで、インスタンスの区別に $\Omega(\log(|G/H|)/\sqrt{\epsilon})$ クエリが必要であることを証明する。この境界は、共役クエリ（$U_\phi^*, U_\phi^T$）や制御クエリへのアクセスがある場合でも成立する。
• サンプル下界: 著者らは情報理論的なツール、具体的にはファノの不等式 (Fano's inequality) とヘールボンド (Holevo bound) を使用する。彼らは、隠れた部分群が大きな候補集合から選ばれるような困難なインスタンスの族を構築する。各コピーの状態が、隠れた部分群について最大でも $O(\epsilon)$ ビットの情報しか提供しないことを示す。その結果、任意の集合的測定を用いても、一定の確率で部分群を特定するには $\Omega(\log(|G/H|)/\epsilon)$ コピーが必要となる。

主要な貢献と結果

1. 厳密な複雑性の特性付け:
本論文は、定数倍の差を除いて一致する上界と下界を提供することにより、アーベル群における StateHSP の複雑性を確定させた：

アクセスモデル	複雑性	パラメータへの依存性
サンプル・モデル (コピー)	$\Theta\left(\frac{\log(|G/H|)}{\epsilon}\right)$	$1/\epsilon$ に線形；商のサイズ $|G/H|$ に依存。
クエリ・モデル (ユニタリ)	$\Theta\left(\frac{\log(|G/H|)}{\sqrt{\epsilon}}\right)$	$\epsilon$ に対して二次的な改善；商のサイズ $|G/H|$ に依存。

2. 未解決問題の解決:

• $1/\epsilon$ の最適性: 本論文は、$1/\epsilon$ のスケーリングがサンプル・モデルにおいて情報理論的に必要であり、コヒーレントなアクセスなしには改善できないことを証明している。
• 部分群のサイズの役割: 複雑さは $\log |G|$ ではなく $\log(|G/H|)$ に依存する。より大きな隠れた部分群（より小さい商）は、明らかに学習が容易である。適応的停止戦略は、 $|H|$ の事前知識なしにこれを達成する。
• 二次的な加速の源泉: $\epsilon$ に対する二次的な改善（$1/\epsilon$ から $1/\sqrt{\epsilon}$ へ）は、状態準備回路へのコヒーレントなアクセス（振幅増幅を可能にするもの）のみから生じることが示されている。下界は強力なオラクル拡張（共役および制御クエリ）に対しても成立しており、これは振幅増幅がこの設定において得られる最大の利点であることを示唆している。

3. 応用:
著者らは、これらの改善された境界が、StateHSP インスタンスとして定式化された特定の対称性学習問題にどのように適用されるかを示している：

• 非もつれ状態の特定 (Locating Unentanglement): 多体状態におけるテンソル積カットの特定。クエリモデルは、忠実度ギャップに対するスケーリングを $1/\tilde{\epsilon}^2$ から $1/\tilde{\epsilon}$ へ改善する。
• スタビライザー群の学習: 量子状態のスタビライザー群の復元。クエリモデルは、ギャップパラメータ $\epsilon$ への依存性を改善する。
• 並進対称性の特定: 多体系の状態における隠れた並進対称性の発見。複雑さはシステムサイズではなく、不変な並進の数にスケールする。

意義と主張

本論文は、アーベル群における StateHSP の完全かつ厳密な特性付けを提供することを主張している。その意義は以下の通りである：

1. オラクルアクセスの力の明確化: 単なるコピーの提供と、状態準備ユニタリへのコヒーレントなアクセスとの間の正確な計算上の優位性を分離している。結果は、コヒーレントなアクセスがギャップパラメータに対して二次的な加速を提供する一方で、群の構造に対する基本的な対数依存性は変化させないことを示している。
2. HSPと学習の架け橋: StateHSP を一般化し、最適なアルゴリズムを提供することで、ショアのアルゴリズムの代数的構造と、現代の量子学習タスク（スタビライバー学習、もつれ検出など）を結びつけている。
3. 手法の厳密性: 著者らは、クエリ最適であるだけでなく、古典的および量子的ゲートのオーバーヘッドを注意深く制限した、時間効率の良いアルゴリズムを提供しており、その結果が実用的な実装において関連性を持つことを保証している。

著者らは、自らの結果が特定のアプリケーションのための StateHSP の簡約（reduction）を最適化しているものの、下界に使用される困難なインスタンスは、その簡約のために特別に構築されたものであり、特定の物理的問題（スタビライザー学習など）の構造を直接反映しているわけではない可能性があると謙虚に述べている。したがって、それらの特定の物理的問題に対する一致する下界を確立することは、依然として未解決の方向性である。また、逆ユニタリ $U_\phi^\dagger$ が、一般的な（逆行列を持たない）ケースにおいて二次的な加速に必要であることは示唆されているが、厳密には証明されていない。