Lattice-quantile estimation of {\pi} and convex-region integrals from coined two-dimensional quantum walks

技術要約：コインを用いた二次元量子ウォークによる $\pi$ および凸領域の格子・分位点推定

問題提起
モンテカルロ（MC）積分は、本質的にクラメール・ラオの下限によって制約を受けている。この下限は、不偏標本平均推定値が期待値に対して $O(M^{-1/2})$ の速度で収束することを規定しており（ここで $M$ はサンプル数）、精度 $\epsilon$ に到達するには $M \sim \epsilon^{-2}$ のサンプルを必要とする。準モンテカルロ（QMC）法は低不一致系列によって前係数を改善するものの、標本平均の構造と漸近的な分散依存性は保持されている。量子振幅推定（QAE）やセゲディ・ウォークといった既存の量子加速フレームワークは、二次的な改善（$O(\epsilon^{-1})$）を提供するが、複雑なオラクル構成や位相推定に依存しており、近未来のハードウェアにとってはリソース集約的である。

本研究は、コインを用いた離散時間量子ウォーク（DTQW）における弾道的な拡散（ballistic spreading）（位置の分散が古典的なランダムウォークの拡散的な $T$ ではなく $T^2$ でスケールする現象）を利用することで、オラクル符号化や位相推定を必要とせずに、数値積分の標本平均の障壁を回避できるかという問いに取り組むものである。

手法
著者らは、2Dコイン型DTQWの位置分布を格子点の計数に関する数論的漸近論と結合させた、格子・分位点（lattice-quantile）フレームワークを提案している。核心となる手法は、標準的なMCからの以下の3つの構造的転換である：

1. 推定量の構造： 指標関数の経験的平均を計算する代わりに、推定器はランク統計量を利用する。具体的には、$T$ ステップ後の量子ウォークの $M$ 回の射影測定から得られる動径方向の位置の $\alpha$-分位点 $\hat{R}(\alpha)$ を計算する。
2. 決定論的マッピング： 推定器は $\hat{\pi} = N(\hat{R}) / \hat{R}^2$ と定義される。ここで $N(R)$ は半径 $R$ の円の内側にある整数格子点の古典的な計数である。これにより、確率的な標本平均が、決定論的な数論関数へと置き換えられる。
3. 誤差分解： この推定器の誤差は、以下の2つの異なる成分に分解されることが示されている：
   • バイアス・フロア（Bias Floor）： ガウスの円問題に関するハーディ・ハクスリーの漸近式から導かれる、ウォークの深さ $T$ によって制御される決定論的な誤差項：$N(R)/R^2 = \pi + O(R^{\gamma-2})$。このフロアは $M$（サンプル数）とは独立して $O(T^{\gamma-2})$（ただし $\gamma \le 131/208$）でスケールする。
   • サンプリング分散： $M \to \infty$ で消失するが、実用的なサンプルサイズにおいてはバイアス・フロアに対して劣位となる統計的項。

このフレームワークは、単位円板を超えて以下に拡張されている：

• 凸平滑領域： 一般的な凸領域に対するクラッツェルの格子漸近論を用いる。
• 平滑な積分： カヴァリエリの原理を用いて、回転対称な関数の積分を $\pi \cdot Q$（$Q$ は古典的に事前計算された定数）として表現する。これにより、単一の量子測定バッチによって、積分ファミリー全体を再構成することが可能となる。
• 環状領域： 非単調な動径プロファイル（例：調和振動子の励起状態）において、超レベル集合が環状になる場合を扱う補遺。

主な貢献
本論文は、以下の6つの具体的な貢献を提示している：

1. 標本複雑度の境界： バイアス・フロアより高い目標精度に対して、固定された $\epsilon$ に依存しないサンプル数 $M$ が十分であることを示す命題。これは $M \sim \epsilon^{-2}$ を要求する古典的MCと対照的である。
2. バイアス・フロア恒等式： パラメータフリーのエンベロープ形式の恒等式（定理4）であり、古典的なガウスの円の残差と、コノの極限測度の動径密度を用いてバイアス・フロアを予測する。この予測は、テストされたすべての深さにおいて、実測されたフロアと1.5倍以内の誤差で一致する。
3. 漸近分散の最適値： サンプリング分散項を最小化する最適分位点 $\alpha^*$ の導出。ただし、著者らはこれが実用上はバイアス・フロアに次いで二次的な問題であると述べている。
4. 一般化された推定器： クラッツェルの定理を介した、任意の凸平滑領域への拡張。
5. カヴァリエリ推定器： 単一の量子ウォークの実行が、古典的な乗数を介して積分ファミリー全体の値を決定する、平滑な積分のための手法。
6. 数値検証： $\pi$ 推定、様々な2D形状の面積推定、ガウス累積分布、および2D量子調和振動子のエネルギー階段における包括的なベンチマーク。

結果
著者らは、量子的な寄与を分離するために、同一の格子・分位点推定器を用いて、一様MC、スクランブルド・ソボルQMC、および古典的ランダムウォーク（RW）に対して手法のベンチマークを行った。

• $\pi$ 推定： ウォークの深さ $T=200$、 $M=100$ において、量子ウォーク（QW）は $\approx 6 \times 10^{-4}$ のRMSEを達成した。この精度に達するために、一様MCは約 $7 \times 10^6$ 個のサンプルを必要とし（約 $7 \times 10^4 \times$ の減少）、スクランブルド・ソボルQMCは（外挿により）約 $5 \times 10^4$ 個のサンプルを必要とした（約 500 倍の減少）。同じ推定器を用いた古典的RWは、その拡散的スケーリング（$T^{(\gamma-2)/2}$）により、はるかに高いバイアス・フロア（$\approx 4\text{--}7 \times 10^{-3}$）で停滞した。
• バイアス・フロアのスケーリング： QWの位相平均バイアス・フロアは、ハーディの予想（$T^{-3/2}$）と一致する $\approx -1.50$ の傾きで減衰する。対照的に、古典的RWのフロアは $T^{-0.85}$ で減衰する。
• 誤差伝播： 単一の測定バッチによって、2DガウスCDFのファミリーおよび2D量子調和振動子のエネルギー階段の再構成に成功した。QWは、古典的RWのベースラインよりも10倍タイトな統計的不確定性でレベル間隔を決定した。誤差予算は解析的に予測可能であり、レベル指数に対して線形にスケールした。
• ハードウェアの実現可能性： 著者らは、量子ビット数（$T=200$ に対して約20個）は現在のデバイスの範囲内であるが、ゲート深さ（$\sim 10^6\text{--}10^7$ 個のCNOTゲート）は現在の能力を超えていると指摘している。本手法はQAE的な意味での「オラクルフリー」であり、被積分関数を符号化する制御ユニタリを必要としない。

意義と主張
本論文は、単なるアルゴリズム的な改善ではなく、構造的な改善を実証していると主張している。精度を決定する量を、統計的な分散（$M$ によって制御される）から決定論的な数論的残差（$T$ によって制御される）へと移転させることで、本フレームワークは標本平均推定器のクラメール・ラオの障壁を回避している。

著者らは、この利点を、精度 $\epsilon$ がバイアス・フロアより高い場合のサンプル数比 $M_{MC}/M_{QW} = \Theta(\epsilon^{-2})$ によって特徴付けられる**「弾道的加速（ballistic acceleration）」**と定義している。彼らは、これは固定された精度における測定回数の比較であり、量子回路の実行コストを含まないことを明記している。本研究は、QAEやセゲディ・ウォークとは異なり、オラクルフリーであり、標本平均ではなくランク統計量推定器を利用している点で区別される。

その意義は、格子点の計数に還元可能な特定の幾何学的および平滑な積分に対して適用可能であり、単一の測定の精度を観測量の全ファミリーへと伝播させることができる、既存の量子アルゴリズムとは構造的に異なる量子強化積分への経路を提供することにある。著者らは、本手法が現在は凸/環状領域に限定されていることを認めつつ、謙虚な姿勢を保っており、要求されるウォークの深さを実用的に実現することは実験的な課題であるとしている。