技術要約：衝突問題における量子下界

1. 問題設定

本論文は、**厳密な $k$-to-one プロミス（約束）**の下での衝突問題の量子クエリ複雑性を調査している。$n = kN$ である $\mathbb{Z}_q^n$ のストリング $x$ へのオラクルアクセスが与えられたとき、入力は厳密に $k$-to-one である（現れるすべてのシンボルは正確に $k$ 回ずつ現れる）ことが約束されている。本論文では、主に2つの問題を取り扱う：

1. 約束された $k$-to-one の発見（Promised $k$-to-one Finding）: 単一のブロック（等しい値の集合）を構成する $k$ 個の位置（完全な $k$-衝突）を出力するタスク。これは、出力の多重度が任意であるランダム関数マルチコリジョン探索とは異なる。
2. $k$-to-one テスティング（$k$-to-one Testing）: 単射な入力（すべての値が異なる）と、厳密に $k$-to-one な入力を区別する決定問題。

著者らは、これら2つの問題を以下の2つの異なる量子クエリモデルで分析している：

• 適応的（Adaptive）: アルゴリズムは、後続のクエリを決定するために、以前のオラクル呼び出しからの情報を使用できる。
• 非適応的（Non-adaptive / One-round）: アルゴリズムは、単一の並列レイヤー内で全てのクエリを実行する。レイヤー内のクエリは任意に絡み合う（entangled）可能性があるが、そのレイヤーからの情報は第2のレイヤーの準備に影響を与えることはできない。

2. 手法

証明は、一様ランダム置換にアクセスする量子アルゴリズムを分析するための**調和フレームワーク（harmonic framework）**に基づいている。この置換は、困難な入力分布を生成するために使用される。

2.1. 困難な分布の構築

著者らは、衝突問題を**置換バケット発見（Permutation Bucket Finding）**へと帰着させている。一様ランダム置換 $\pi \in S_n$ を用いて、置換の出力スロットを $N$ 個の公開バケット（各サイズ $k$）に分割することで、バランスの取れた $k$-to-one 入力を生成する。インデックス $i$ における入力値は、$\pi(i)$ を含むバケットによって決定される。入力における完全な $k$-衝突を見つけることは、置換における単一のバケットにマッピングされるすべての位置を見つけることに対応する。

2.2. 圧縮オラクルとエンコーディング

核心となる技術的ツールは、Carolan [Car26] の研究に基づき、厳密な $k$-to-one 入入力用に適応させた**圧縮置換オラクル（compressed permutation oracle）**である。

• データベース表現: アルゴリズムの知識は、部分的な単射（入力・出力のペア）のデータベースとして表現される。
• 厳密なエンコーディング ($V$): 著者らは、置換レジスタをデータベースレジスタに写像する等長写像（isometry）$V$ を構築する。このエンコーディングは「置換次数（permutation degree）」（クエリ数に関連）を保存し、データベース空間における冗長な方向（例：新しい情報を運ばない一様な拡張）を排除するために、調和部分空間（harmonic subspaces）（範囲調和およびドメイン調和）を利用する。
• 誤差界: 論文では、真の置換クエリと、データベースを更新する「記録（recording）」クエリとの間の差に関するタイトな境界を確立している。具体的には、調和部分空間の外側にある局所的な記録クエリによって導入される誤差を、適応的アルゴリズムでは $O(T^2/n)$、非投影比較では $O(\sqrt{T/n})$ となるように抑えている。

2.3. 証明戦略

• 適応的下界: Liu および Zhandry [LZ19] による部分衝突の階層構造を置換の設定に適合させている。連続するクエリを通じて、「部分衝突（$j$ 個の記録されたスロットを持つバケット）」の成長を追跡する。部分衝突の数にカットオフを設定し、単一のクエリでこれらの閾値を越える振幅を制限することで、完全な $k$-衝突を構築するには特定の数のクエリが必要であることを示す。証明では、シミュレーション誤差を制御するために、各クエリの後にドメイン投影 $K_D$ を適用する**投影記録プロセス（projected recording process）**を用いている。
• 非適応的下界: 1ラウンドのアルゴリズムでは、衝突の段階的な構築は利用できない。代わりに、著者らは単一の並列クエリレイヤーの後の状態を直接分析する。彼らは、1ラウンドクエリに固有のアルゴリズムベクトルの直交性（補題 3.1）を利用して状態を分解する。その後、静的占有界（static occupancy bound）（補題 7.1）を適用し、データベースに規定された $k$ 個の値が記録される確率は $(t/n)^k$ のオーダーである $O((t/n)^k)$ で抑えられることを示す。この境界は、絡み合ったクエリに対しても成立する。
• 決定下界: $k$-to-one テスティングについては、4つの分布（独立ラベル（Fun/Block$_k$）および異なるラベル（Inj/Exact$_k$））の下でのアルゴリズムの縮退した状態を比較する。調和エンコーディングを用いて、独立ラベルを持つ状態と異なるラベルを持つ状態の間のトレース距離を境界付け、その変化が $O(t/\sqrt{q})$ と小さいことを示す。

3. 主要な貢献と結果

3.1. 適応的約束 $k$-to-one 発見

本論文は、適応的量子アルゴリズムに対するタイトな下界を確立している。

• 結果: 定数確率で成功する任意の量子アルゴリズムは、$\Omega_k(n^{\alpha_k})$ クエリを必要とする。ここで $\alpha_k = \frac{1}{2} - \frac{1}{2(2k-1)}$ である。
• 意義: これは Liu および Zhandry [LZ19] の適応的アルゴリズムによって達成された上界と一致する。これは、彼らのアルゴリズムにおける逐次的依存性が不可欠であり、厳密な $k$-to-one プロミスの下では、制限のない適応性を持っていたとしても、これ以上の量子加速は不可能であることを裏付けている。

3.2. 非適応的約束 $k$-to-one 発見

本論文は、1ラウンド量子アルゴリズムに対するタイトな下界を確立している。

• 結果: 任意の1ラウンド量子アルゴリズムは、$\Omega_k(n^{1-1/k})$ 並列クエリを必要とする。
• 意義: これは古典的なバースデーサンプリングの複雑性と一致する。これは、単一のクエリレイヤーにおける絡み合い（entanglement）だけでは、適応的アルゴリズムで見られる量子的な加速を実現するには不十分であることを示している。逐次的依存性は、単なる特定アルゴリズム設計の副産物ではなく、加速のための根本的な要件である。

3.3. 非適応的 $k$-to-one テスティング

本論文は、単射入力と $k$-to-one 入力を区別する非適応的複雑性に関する未解決問題を解決した。

• 結果: 任意の1ラウンド量子アルゴリズムは、$\Omega(\sqrt{n/k})$ クエリを必要とする。
• 意義: これは古典的な複雑性と一致し、$k=2$ の場合における Koiran, Landes, Portier, および Yao [KLPY10] が提起した未解決問題に答えるものである。証明は、異なるラベルが強制される制約を扱いながら、アルファベットサイズ $q \ge n$ に対して機能する。

4. 意義と主張

本論文は、厳密な $k$-to-one プロミスの下でのこれらの衝突問題に対する量子クエリ複雑性の完全な特性付けを提供すると主張している。

• モデルの分離: 結果は、**適応性（adaptivity）の力と量子コヒーレンス（quantum coherence）**の力を明確に分離している。量子コヒーレンスは適応的な設定において加速（古典的な $n^{1-1/k}$ の壁を打破）を可能にするが、非適応的（1ラウンド）設定においては漸近的な優位性をもたらさない。
• 最適性: 下界は既存の上界（適応的では Liu-Zhandry、非適応的では古典的サンプリング）と一致することで、タイトであることが示されている。
• 手法の進展: 著者らは、圧縮置換オラクルを用いた洗練された調和フレームワークを導入している。このフレームワークは、厳密な $k$-to-one 入力に内在する依存関係（すべての値が正確に $k$ 回現れなければならないという制約）を処理する。これは、独立性を仮定するランダム関数のための従来の圧縮オラクル技術が直接適用できない設定である。
• 同時進行中の研究との比較: 本論文は、Carolan および Majenz [CM26]、ならびに Kim [Kim26] による同時進行中の研究が圧縮置換オラクルのシミュレーションを改善していることに言及している。しかし、著者らは、特に適応的下界のための投影前方クエリプロセスや、1ラウンド下界のための静的占有界といった、彼ら自身のツールの具体的な適用方法が、厳密な $k$-to-one プロミスのために必要なタイトな下界をもたらすと主張している。

論文は、オープンな問題（具体的には $r \ge 2$ レイヤーにおける完全なラウンド階層、および Search $k$-Distinctness のアルファベットサイズ要件）を特定して締めくくっているが、それらに対する解決策は本研究内では提案していない。