論文の概要: Quantum Speedups for Testing Similar Means

• arxiv url: http://arxiv.org/abs/2608.00741v1
• Date: Sat, 01 Aug 2026 16:23:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-04 15:07:24.881894
• Title: Quantum Speedups for Testing Similar Means
• Title（参考訳）: 類似した手段をテストするための量子スピードアップ
• Abstract要約: この研究は、$m$分布が類似した手段を持つか、2つのモデルの平均類似性から$$$-farであるかをテストするための量子アルゴリズムに焦点を当てている。 クエリモデルでは、どの分布からサンプリングするかをアルゴリズムが選択できるが、サンプリングモデルでは、分布が一様に選択される。
• 参考スコア（独自算出の注目度）: 4.1765120028423
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of $m$ ($m\geq 3$) distributions. This work focuses on quantum algorithms for testing whether $m$ distributions have similar means or are $ε$-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities $\tilde{O}(1/ε)$ (the $\tilde{O}$ notation hides poly-logarithmic factors) and $\tilde{O}(\sqrt{m}/ε)$ in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of $Ω\left(1/ε\right)$ and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on $ε$ up to logarithmic factors.
• Abstract（参考訳）: 分布のプロパティテストは情報理論、学習理論、統計学において中心的なトピックである。 量子アルゴリズムは、単一分布または一対の分布のプロパティテストのための重要なスピードアップを提供することが知られているが、量子アルゴリズムが$m$$$m\geq 3$のプロパティテストのためのスピードアップを提供するかどうかは不明である。 この研究は、$m$分布が類似した手段を持つか、2つのモデルの平均類似性からε$-farであるかどうかをテストするための量子アルゴリズムに焦点を当てる。 クエリモデルでは、どの分布からサンプリングするかをアルゴリズムが選択できるが、サンプリングモデルでは、分布が一様に選択される。 複素量$\tilde{O}(1/ε)$ ($\tilde{O}$ notation hides poly-logarithmic factors) と $\tilde{O}(\sqrt{m}/ε)$ の量子アルゴリズムをクエリとサンプリングモデルでそれぞれ設計し、古典的モデルよりも2次的なスピードアップを達成する。 さらに、クエリモデルとサンプリングモデルに対して、$Ω\left(1/ε\right)$と$Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$の量子下界を確立し、ε$から対数因子への依存の観点から、量子アルゴリズムの最適性を実証する。

関連論文リスト

• Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling [55.388363730120325]
  本研究では,CTMC(Continuous-Time Markov Chain)フレームワークにおいて,離散拡散を吸収するための$-leapingアルゴリズムを並列化する。 我々は,$$-leapingアルゴリズムとPicard法の連続時間積分形式を利用して,並列時間サンプリング高速化を実現する。 本研究は, 分子構造や言語生成などの応用において, 効率的な並列推論のための離散拡散モデルの可能性を広げるものである。
  論文  参考訳（メタデータ） (2026-07-01T10:59:33Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。 離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
  論文  参考訳（メタデータ） (2026-05-05T12:25:17Z)
• Uniformity testing when you have the source code [16.232881331802687]
  古典回路や量子回路の出力確率分布の特性を検証するための量子アルゴリズムについて検討する。 出力分布が全変動距離から$[d]$または$epsilon$-farで均一であるかどうかを決定する。
  論文  参考訳（メタデータ） (2024-11-07T18:48:29Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• Mind the $\ ilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。 従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。 Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
  論文  参考訳（メタデータ） (2023-04-06T02:18:52Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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