Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

技術要約：量子サンプリングにおけるタイトなクエリ下界、および認証されたランダムネスへの応用

問題設定
ランダム回路サンプリング実験は、量子計算優位性の主要な実証手法であり、通常、線形クロスエントロピー・ベンチマーク（XEB）を用いて検証される。XEBスコアは、デバイスの出力分布が理想的な分布 $p$ とどの程度一致しているかを、返された文字列 $z$ の $N p(z)$ の平均を計算することで測定する（ここで $N=2^n$）。高いスコアは量子優位性を示唆するが、デバイスが実際に $p$ からサンプリングしたことや、その出力がランダムであることを本質的に保証するものではない。デバイスは、最も可能性の高い文字列を決定論的に出力することで高いスコアを達成できる可能性があり（これは攻撃者が知っている可能性がある）、その場合、認証されたランダムネスの生成に失敗することになる。

本論文は、量子クエリモデルにおける2つの根本的な問いに取り組む：

1. スコアの限界： 効率的な量子デバイスは、理想的なスコアに対してどの程度高いスコアを出すことができるか？ 具体的には、効率的なデバイスは理想的なスコアを定数分超えることができるか？
2. ランダムネスの認証： デバイスが理想に近いスコアを達成した場合、その出力には（たとえデバイスと量子もつれ状態にあり、かつ後でオラクル（回路または関数）を学習した可能性がある敵対者（Eve）に対しても）どの程度の平滑化最小エントロピー（認証されたランダムネス）が含まれているか？

手法
著者らは、回路が既知のアンサンブルから抽出されたオラクルに置き換えられたクエリモデルにおいて作業を行う。彼らは以下の2つの特定のアンサンブルを分析する：

• フーリエ・サンプリング： オラクルは一様ランダムな関数 $f: \{0,1\}^n \to \{\pm 1\}$ である。正直なサンプラー（honest sampler）のスコアは約3となる。
• ハール乱数状態： オラクルは、標準的な状態準備オラクルまたはハール乱数ユニタリへのアクセスを介してアクセスされる、一様ランダムな単位ベクトル $|\phi\rangle$ を隠蔽している。正直なサンプラーのスコアは約2となる。

核心となる手法は、デバイスの状態と「正直な」状態（単一のクエリを行う状態）との偏差を定量化する進捗尺度（progress measure） $\lambda$ を定義することである。分析は以下の3段階のフレームワークに従う：

1. スコア境界： 期待スコア $B(A)$ は、進捗尺度を用いて $B(A) \leq \text{Ideal Score} + O(\lambda + \lambda^2)$ と抑えられる。
2. 成長境界： 各クエリが $\lambda$ を $O(\sqrt{(t+1)/N})$ のみ増加させることが示される（ここで $t$ はこれまでのクエリ数）。その結果、$q$ 回のクエリの後、$\lambda = O(q^{3/2}/\sqrt{N})$ となる。
3. ランダムネス抽出： 理想的なスコアに近い（欠損 $\delta$ が小さい）デバイスについて、スコア境界の証明を洗練させ、デバイスの出力ブランチが特定の補助ベクトルに近似していることを示す。これらのベクトルは、デバイスのみに作用する演算子によって生成され、そのノルムは $\text{poly}(q)\sqrt{p(z)}$ によって抑えられる。この構造は、たとえEveがオラクルを知っていたとしても、Eveによる出力の推測能力が制限されることを意味する。

主要な貢献と結果

1. 理想的なスコアを超えるためのタイトな下界
本論文は、理想的なスコアが、効率的な量子デバイスにとっての「ツィレルソン境界（Tsirelson bound）」として機能することを確立する。

• クエリ複雑性： 理想的なスコアを定数 $\epsilon$ だけ超えるために、量子アルゴリズムは $\Omega(N^{1/3})$ 回のクエリを必要とする。
  • フーリエ・サンプリングでは、期待スコア $3 + \epsilon$ を得るには $q \geq \Omega(N^{1/3})$ が必要である。
  • ハール乱数状態では、期待スコア $2 + \epsilon$ を得るには $q \geq \Omega(N^{1/3})$ が必要である。
• 上界： 著者らは、「スクエアリング・アルゴリズム（二乗アルゴリズム）」（衝突発見アルゴリズムの変種）を用いることで、$O(N^{1/3})$ 回のクエリで理想的なスコアを定数分超えることが可能であることを確認している。このアルゴリズムは、$m \approx N^{1/3}$ 個の理想的なサンプルを保持し、振幅増幅を用いて出力を理想的な分布の二乗 $p(z)^2$ へと偏らせる。
• タイト性： これらの境界はタイトである。正直なサンプラー（1クエリ）と、理想的なスコアを大幅に超える能力との間のギャップは、正確に $N^{1/3}$ の閾値によって特徴付けられる。

2. 理想的なスコアにおける認証されたランダムネス
本論文は、多項式回数のクエリを行い、理想的なスコアの $o(1)$ 以内の欠損を持つデバイスが、ほぼ最大級のランダムネスを含む出力を生成することを証明している。

• 最小エントロピー： フーリエ・サンプリングおよびハール乱数状態（標準的なオラクル経由）の両方において、出力 $Z$ は平滑化最小エントロピー $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ を持つ（ここで $R$ はオラクル、$E$ はEveのレジスタである）。
• 敵対者モデル： これは、Eveがデバイスと量子もつれ状態にあり、かつデバイスが出力 $Z$ を出した後にオラクルの完全な記述（関数 $f$ またはベクトル $\phi$）を学習した場合でも成立する。
• パラメータ： 平滑化パラメータ $\eta$ は $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$ としてスケールする。もし欠損 $\delta$ が無視できるほど小さく、$q$ が $n$ の多項式であれば、平滑化は無視可能となり、$n - O(\log n)$ ビットのランダムネスが認証される。
• 最適性： $O(\log n)$ の損失はほぼ最適であることが示されている。論文では、理想に近いスコアを得つつも、出力をサイズ $N/q^2$ の既知の集合に制限するデバイスを振幅増幅を用いて構成しており、これにより最小エントロピーが $n - 2\log q$ に制限されることが示されている。

3. 追加の結果

• 衝突分布： 衝突分布（$p(z)^2$ に比例する分布）のサンプリングのクエリ複雑性が $\Theta(N^{1/3})$ であることを示している。
• 量子アダマール積： 振幅の大きさが一様な2つの状態の量子アダマール積を準備するための、コヒーレントなスクエアリング・アルゴリズムが提示されている。このアルゴリズムは、$O(N^{1/3})$ 回のクエリを用いて、トレース距離誤差 $O(N^{-1/6})$ を達成しており、これは標準的な振幅増幅で必要な $\sqrt{N}$ 回のクエリよりも改善されている。

意義と主張
本論文は、量子サンプリング・タスクに対して、無条件の情報理論的な保証を提供し、「量子超越性ツィレルソン不等式」に関する未解決の問いを解決すると主張している。

• CHSHとの類似性： 本結果は、CHSHゲームとの直接的な類似性を描いている。CHSHゲームにおいて、ツィレルソンの境界（$\cos^2(\pi/8)$）が量子戦略の勝利確率を制限し、その境界においてランダムネスを認証するのと同様に、理想的なXEBスコアは、効率的な量子サンプラーの性能を制限し、そのスコア付近でランダムネスを認証する。
• 無条件の安全性： 計算量的困難性の仮定や、敵対者の知識の制限（例：完全なオラクルを学習しないこと）に依存していた従来の成果とは異なり、本研究は、オラクルを学習し、任意の量子もつれを保持する敵対者に対する無条件の境界を提供している。
• 限界： 著者らは、自らの結果がオラクルモデルに適用されるものであると注記している。現実世界のデバイス（[AAB+19]など）において、現在のスコアは理想からは遠い（例：1.002 対 2）。したがって、実験的な設定における認証されたランダムネスの現在の保証は、異なる、より弱い仮定（例：[AH23]）に依存している。さらに、ハール乱数状態の場合、結果はフル・ユニタリ・アクセスではなく、標準的な状態準備オラクルを必要とする。これは、フル・ハール乱数ユニタリを学習した敵対者が、ユニタリの列と出力を相関させる可能性があるためである。

要約すると、本論文は効率的な量子サンプリングの限界を厳密に定義し、理想的なスコアが効率的なデバイスにとってのハードな障壁となること、そしてその障壁に近づくことが、強力な量子敵対者に対してもほぼ全てのランダムネスを認証することを証明している。