論文の概要: Distributional Quantum Query Complexity

• arxiv url: http://arxiv.org/abs/2610.06835v1
• Date: Mon, 05 Oct 2026 17:58:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.45551
• Title: Distributional Quantum Query Complexity
• Title（参考訳）: 分散量子クエリの複雑さ
• Abstract要約: 量子クエリの複雑さは、様々なジョイント計算特性を楽しみます。 構成、直和、直積問題に対して分布計算を下限とする。
• 参考スコア（独自算出の注目度）: 0.30018539236811154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
• Abstract（参考訳）: 例えば、$Q(f\circ) を主張する合成定理。 g)=(Q) (f)Q a direct sum theorem that computing $k$ copy of a function ( or search problem) cost as much as the cost of computing one copy; and a direct product theorem that for Boolean function, even successfully at the direct sum problem with initially small probability; a direct sum theorem as $Ω(k)$ times of computing one copy to bounded error. しかし、これらの結果はすべて、最悪の量子クエリの複雑さに対して厳密に当てはまる。 例えば、入力上の固定分布$μ$がある場合、直接和定理は、入力が最悪の場合ではなく、製品分布$μ^k$から来るとき、$k$$$f$のコピーを演算する量子クエリの複雑さについて何も述べない。 (標準的な八尾型ミニマックス定理は直和問題に対して硬分布を保証するが、この硬分布が積分布である保証はない)。 直積定理と合成定理には同様の問題が生じる:これらの結果はいずれも分布を尊重するものではない。 本研究では, 構成, 直接和, 直積問題に対して, 分散連接計算の下位境界を与える。 その過程で、量子クエリの低いバウンドを扱うための新しいツールを紹介します。 (a)$γ_2$ノルムの新しい ``multiplicative'' 変種(直積定理を証明する乗法に代えて使用する) b) 分散量子クエリの複雑性の組成挙動を特徴付け, 満足度を満足する新しい「シャルティエルフリー」測度。

関連論文リスト

• Tight bounds for hybrid quantum-classical query algorithms [0.45880283710344066]
  クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。 状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。
  論文  参考訳（メタデータ） (2026-10-05T17:53:05Z)
• Distributional Variants of the Aaronson-Ambainis Conjecture [1.2366208723499545]
  均一な入力分布の下では、量子クエリアルゴリズムは古典的なアルゴリズムでシミュレートできる。 すべての固定$p inに対して、$_p$分布の下での量子クエリアルゴリズムは予想を許容し、同じが予想均一分布の下で成り立つ場合に限ることを示す。 アーロンソン・アンバイニス予想(アーロンソン・アンバイニスげん、英: Aaronson-Ambainis conjecture)は、この予想を示唆する強い言明であり、ハイパーキューブ上の有界な低次数で定式化されている。
  論文  参考訳（メタデータ） (2026-09-28T14:52:32Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• Direct sum theorems beyond query complexity [0.0]
  コンピュータサイエンスの根本的な疑問は、$n$インスタンスを同時に解決するよりも、独立して解決することが難しいか、ということです。 本稿では,古典的/量子的クエリ複雑性,機械学習のためのPAC学習,統計的推定理論などを拡張する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-28T06:53:29Z)
• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。 ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。 有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
  論文  参考訳（メタデータ） (2024-06-06T11:33:29Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• 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)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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