論文の概要: Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements

• arxiv url: http://arxiv.org/abs/2605.14256v1
• Date: Thu, 14 May 2026 01:48:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-15 21:45:34.570153
• Title: Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements
• Title（参考訳）: 局所ランダム化測定による分散内積推定のための最悪のサンプル複雑度境界
• Authors: Zhenyuan Huang, Kun Wang, Ping Xu,
• Abstract要約: 独立な単一量子ビットのパウリ影が最悪の場合$mathcalO(sqrt7.5n)$ for large $n$を持つことを示す。 また、独立な単一量子ビットのパウリ影がいくつかの重要な状態のクラスに対して$mathcalO(sqrt3.6n)$の最悪のスケールを持つことを示す。
• 参考スコア（独自算出の注目度）: 9.31599937600725
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study distributed inner product estimation for $n$-qubit states using local randomized measurements, for which rigorous worst-case guarantees are less understood. We first reduce the minimax kernel optimization to Hamming-distance kernels. Within this class, unbiasedness fixes a unique kernel. For this kernel under local Clifford sampling, we prove a sharp fourth-moment bound using the single-qubit Clifford commutant. This yields worst-case sample complexity $\mathcal{O}(\sqrt{4.5^n})$, attained by identical pure product stabilizer states. For the same kernel under local Haar sampling, we prove a local twirling identity that compares its fourth moment with the Clifford fourth moment. This gives the same rigorous upper bound as in the Clifford case, but the comparison is lossy. This motivates the conjectured sharper Haar scaling $\mathcal{O}(\sqrt{3.6^n})$ attained by product states, and verify it for several important classes of states. We also show that independent single-qubit Pauli shadows have worst-case scaling $\mathcal{O}(\sqrt{7.5^n})$ for large $n$.
• Abstract（参考訳）: 局所ランダム化測定を用いて,$n$-qubit状態の分散内積推定について検討した。 まずミニマックスカーネルをハミング距離カーネルに最適化する。 このクラス内では、アンバイアスネスはユニークなカーネルを修正する。 局所クリフォードサンプリングの下でのこのカーネルに対して、シングルキュービットクリフォード可換体を用いて鋭い第4モーメント境界を証明する。 これにより最悪のサンプル複雑性が$\mathcal{O}(\sqrt{4.5^n})$となる。 局所ハールサンプリングの下で同じカーネルに対して、第4モーメントとクリフォード第4モーメントを比較する局所ツイリング同一性を証明する。 これはクリフォードの場合と同じ厳密な上界を与えるが、比較は失われる。 これは予想よりシャープなHaarスケーリング $\mathcal{O}(\sqrt{3.6^n})$ を積状態によって達成し、いくつかの重要な状態のクラスに対して検証する。 また、独立な単一量子ビットのパウリ影は、大きめの$n$に対して$\mathcal{O}(\sqrt{7.5^n})$が最悪の場合であることを示す。

関連論文リスト

• The Computational Complexity of Almost Stable Clustering with Penalties [2.689067085628911]
  両次元の小さい測度において,$mathrmk-M SmallEANS$と$mathrmk-M SmallEDIAN$の安定(あるいは摂動耐性)インスタンスの複雑性について検討する。 ほぼ安定な$mathrmk-MsmallEANS$/$mathrmk-MsmallEDIAN$(罰則付き)の特別なケースは、時間内に解決可能であることを示す。
  論文  参考訳（メタデータ） (2025-10-03T16:15:12Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
  本稿では,エレガントな収束保証を有する原理的かつ単純なアルゴリズムである制約付き近位サンプリング手法を提案する。 R'enyi-infinity divergence(mathcal R_infty$)に収束することを示す。
  論文  参考訳（メタデータ） (2024-07-17T19:20:08Z)
• Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding [5.502903075972815]
  本研究では、カーネルのハーディングと同じ最悪のエラーを最小限に抑えるために、二次ノード上の結合確率分布について検討する。 我々の主な貢献は、最悪の積分誤差に対してより厳密な集中不等式を持つという意味で、モンテカルロよりも優れていることを証明することである。
  論文  参考訳（メタデータ） (2024-02-18T23:39:00Z)
• Transfer Operators from Batches of Unpaired Points via Entropic Transport Kernels [3.099885205621181]
  そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。 我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
  論文  参考訳（メタデータ） (2024-02-13T12:52:41Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  Nystr"om法に基づく効率的な近似手法を提案する。 サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。 本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
  論文  参考訳（メタデータ） (2022-01-31T08:26:06Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。