Quantum Approximate Counting with Bernoulli Oracles

技術要約：ベルヌーイ・オラクルを用いた量子近似計数

1. 問題定義

本論文は、標準的なメンバーシップ・オラクルがベルヌーイ・オラクルに置き換わった設定における**量子近似計数（Quantum Approximate Counting）**の問題を扱う。

• 標準的な設定: 古典的および標準的な量子計数では、メンバーシップ・オラクルが集合の要素に対して決定論的に0または1のラベルを付与する。目的は、加法的誤差 $\epsilon$ 以内で、1とラベル付けされた要素の割合 $\rho$ を推定することである。量子アルゴリズムは、古典的なサンプリングの $\Theta(\rho/\epsilon^2)$ に対し、$\Theta(\sqrt{\rho}/\epsilon)$ クエリで実現される二次的な高速化（quadratic speedup）を達成する。
• ベルヌーイ・オラクル設定: 著者らは、ラベルが確率的であるより現実的なシナリオを検討している。アルゴリズムは、$m$ 個の未知のバイアス $p_1, \dots, p_m \in [0, 1]$ を持つベルヌーイ分布の集合 $D = \{D_1, \dots, D_m\}$ へのアクセス権を持つ。
  • ある分布が**正（positive）**であるとは、$p_i \ge 1/2 + \Delta$ であることを指す。
  • ある分布が**負（negative）**であるとは、$p_i \le 1/2 - \Delta$ であることを指す。
  • 目的は、正の分布の割合 $\rho$ を加法的誤差 $\epsilon$ 以内で推定することである。
  • 量子オラクル $O$ は、インデックス・レジスタ $A$ と補助レジスタ $B, C$ に対して次のように作用する：
    $$O |i\rangle_A |\vec{0}\rangle_{B,C} = |i\rangle_A \left( \sqrt{p_i} |1\rangle_B |\phi_{i,1}\rangle_C + \sqrt{1-p_i} |0\rangle_B |\phi_{i,0}\rangle_C \right)$$

このモデルは、有界誤差オラクル（各クエリが定数確率 $p_e \ge 9/10$ で正しいラベルを返すものに対応し、$\Delta = 2/5$ となる）および標準的なメンバーシップ・オラクル（$\Delta = 1/2$）を一般化したものである。

2. 手法

論文では、それぞれ異なる手法を用いて、クエリ複雑性の上下限の両方を確立している。

上界の技術:
主な課題は、特定の分布が正か負かを判断するために、量子重ね合わせを崩壊させることなく、限定された数のクエリで完璧に行うことはできない点である。標準的な誤差減少（反復と中央値の取得）は測定を必要とするが、これは量子振幅推定に必要なコヒーレンスを破壊してしまう。

これを解決するために、著者らは3段階のアルゴリズムを提案している：

1. QSVTによるコヒーレントな誤差減少: 測定を行う代わりに、アルゴリズムは**量子特異値変換（QSVT）**を用いて、バイアス・ギャップをコヒーレントに増幅する。ステップ関数を次数 $O(\frac{1}{\Delta} \log \frac{1}{\epsilon})$ の多項式で近似することにより、アルゴリズムは状態を以下のように変換する：
   • もし $p_i \ge 1/2 + \Delta$ ならば、$|1\rangle$ を測定する確率は $\ge 1 - \epsilon$ となる。
   • もし $p_i \le 1/2 - \Delta$ ならば、$|1\rangle$ を測定する確率は $\le \epsilon$ となる。
     このサブルーチンであるRST（Robust Single Distribution Transform）は、インデックス・レジスタ上の重ね合わせを保持したまま、コヒーレントな層の中で完全に誤差減少を実行する。
2. 2段階適応型振幅推定: RST サブルーチンは、適応型振幅推定スキームの中に組み込まれる。
   • 第1段階: $\rho$ の粗い推定値を得る。
   • 第2段階: $\rho$ が無視できない場合、粗い推定値を用いて、より精密な第2段階の推定実行の精度を調整する。これにより、$\rho$ が非常に小さい場合に高精度な推定にリソースを浪費することを避ける。
3. 信頼度の向上: 全工程を $\Theta(\log(1/\delta)$ 回繰り返し、その中央値を取ることで、成功確率を $1-\delta$ に高める。

下界の技術:
著者らは、推定問題を合成された決定問題である Count $\circ$ DD へ還元することで、下界を証明している。

• 外側関数 (Count): $m$ ビットの文字列のハミング重みが $\rho m$ か $(\rho + \epsilon)m$ であるかを判定する標準的なブール関数。
• 内側関数 (DD): $R$ 個の独立したサンプルが与えられたとき、2つの未知の分布 $P$ と $Q$ を区別する平均ケースの問題。

著者らは、Boolean-over-average-case 方向における量子アドバーサリ法の新しい合成定理を導入している。標準的な合成定理は、Boolean-over-Boolean または average-case-over-Boolean を扱うが、本研究は逆方向（外側が Boolean、内側が average-case）を扱っている。

• 障害1 (内側の非一様性): 異なるブロック間の内積が等しいことが保証されない。著者らは、すべてのブロックの内積が1となる特定の内部アドバーサリ行列を構成することで、互換性を確保している。
• 障害2 (外側の不整合): 一般的なブール関数に対するアドバーサリ行列の主固有ベクトルに対して、外側層の一様分布ベクトルが整列しない。著者らは、特定の「Count」関数（0-1 行列）については、全一ベクトルがスペクトルノルムに対する十分な下界を提供することを示し、不整合の問題を解決した。

3. 主要な結果

本論文は、ベルヌーイ・オラクルを用いた量子計数のクエリ複雑性をほぼ完全に特徴付けている。

上界 (Theorem 1.2):
$\rho$ を加法的誤差 $\epsilon$ 以内で、成功確率 $1-\delta$ で推定する量子アルゴリズムが存在する。そのクエリ数は以下の通りである：
$$\tilde{O}\left( \left( \frac{\sqrt{\rho}}{\Delta \epsilon} + \frac{1}{\Delta \sqrt{\epsilon}} \right) \log \frac{1}{\delta} \right)$$

• これは、古典的なサンプリング複雑性 $\Theta(\frac{\rho}{\Delta^2 \epsilon^2})$ に対する二次的な高速化を達成している。
• 有界誤差オラクル ($\Delta = \Theta(1)$) の特殊なケースでは、この境界は $\tilde{O}(\frac{\sqrt{\rho}}{\epsilon} + \frac{1}{\sqrt{\epsilon}})$ に簡略化される。

下界 (Theorem 1.3):
成功確率 $2/3$ で $\rho$ を加法的誤差 $\epsilon$ 以内で推定するいかなる量子アルゴリズムも、以下のクエリを必要とする：
$$\Omega\left( \frac{\sqrt{\rho}}{\Delta \epsilon} \right)$$

• この下界は、全範囲の $\Delta$ において、対数因子を除いて上界と一致している。
• 有界誤差オラクル ($\Delta = \Theta(1)$) の場合、下界は $\Omega(\frac{\sqrt{\rho}}{\epsilon})$ である。

包含関係の連鎖:
論文は、以下のオラクルの階層関係を確立している：Membership $\subset$ Bounded-error $\subset$ Bernoulli。

• $\Delta = 1/2$ の場合のベルヌーイ・オラクルの結果は、標準的な量子計数の境界を回収する。
• $\Delta = 2/5$ の場合のベルヌーイ・オラクルの結果は、有界誤差オラクルを用いた量子計数の複雑性を特徴付けており、これは以前に研究されていたものの、この特定の文脈では完全には特徴付けられていなかった問題である。

4. 意義と主張

著者らは、本研究が、確率的なラベル付けの下での量子近似計数のクエリ複雑性を本質的に完全に特徴付けていると主張している。

• 高速化の一般化: 本研究は、オラクルが決定論的なラベルではなく確率的なサンプルを返す場合でも、バイアス・ギャップ $\Delta$ が既知であれば、量子計数の二次的な高速化が堅牢であることを示している。
• コヒーレントな誤差減少: QSVT を用いてコヒーレントに誤差減少を行う手法を導入しており、これにより、古典的な誤差減少を量子振幅推定と合成する際に妨げとなる、重ね合わせの崩壊を回避している。
• 新しい合成定理: 下界の導出において、Boolean-over-average-case 方向の量子アドバーサリ法に関する新しい合成定理を導入しており、それまで分析を困難にしていた特定の構造的障害（内側の非一様性と外側の不整合）を克服している。
• 有界誤差オラクルの特徴付け: 直接的な帰結として、本論文は有界誤差オラクルを用いた量子計数のクエリ複雑性を解決し、それが $\tilde{O}(\sqrt{\rho}/\epsilon)$ でスケールすることを示し、標準的なメンバーシップ・オラクルとのスケーリングを（対数因子を除いて）一致させている。

論文は最後に、2つの未解決の問いを挙げている。一つは、上界における対数因子を取り除くことができるかどうかであり、もう一つは、ここで用いられた適応型クエリモデルではなく、サンプリングモデル（アルゴリズムがランダムなインデックスとサンプルのペアを受け取るモデル）の下で複雑性がどのように変化するかである。