論文の概要: Optimal Quantum-Classical Separations for Exact Learning

• arxiv url: http://arxiv.org/abs/2609.38073v1
• Date: Tue, 29 Sep 2026 17:34:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.789579
• Title: Optimal Quantum-Classical Separations for Exact Learning
• Title（参考訳）: エクササイズ学習のための最適量子古典分離法
• Abstract要約: 我々は、概念クラス$mathcal Csubseteq0,1N$のメンバシップクエリによる正確な学習について研究する。 我々の結果は、学習のための量子スピードアップがGroverやBernstein-Vaziraniのパラダイムを超えることができることを示す最初のものである。
• 参考スコア（独自算出の注目度）: 2.2165845825140695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, and $\mathsf{Q}(\mathcal C)$, respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture $$ \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N). $$ We first refute this conjecture by constructing concept classes $\mathcal C$ and $\mathcal C'$ satisfying \[ \mathsf{R}(\mathcal C)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N). \] The first bound matches the upper bound of Arunachalam et al.~[Quantum'21] up to constant factors, while the second matches the upper bound of Servedio and Gortler~[SICOMP'04]. In particular, this shows that the saving in the randomized upper bound of Arunachalam et al. fundamentally relies on randomness. Apart from characterizing the optimal relationship between classical and quantum query complexity, our results are the first to show that quantum speedups for learning can go beyond the Grover and Bernstein-Vazirani paradigms.
• Abstract（参考訳）: 概念クラス $\mathcal C\subseteq\{0,1\}^N$ のメンバシップクエリを用いて正確な学習を行い、決定論的、ランダム化、および量子クエリ複合体間の関係に着目し、それぞれ $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, $\mathsf{Q}(\mathcal C)$ と表記する。 このモデルにおける2つの正準量子スピードアップはグロバーサーチとベルンシュタイン=ヴァジラニによって観測され、長く続いた予想である$$$ \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N へと導かれる。 $$ この予想を最初に否定するのは、概念クラス $\mathcal C$ と $\mathcal C'$ を \[ \mathsf{R}(\mathcal C)=Ω\! \left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N)。 \] 第1境界はArunachalam et al ~[Quantum'21]の上界を定数要素に、第2境界はServedio と Gortler の上限を[SICOMP'04]に一致させる。 特に、Arunachalam et al のランダム化された上界の保存は、基本的にランダム性に依存していることを示している。 古典的および量子的クエリの複雑性の最適関係を特徴づける以外に、学習のための量子スピードアップがGroverとBernstein-Vaziraniのパラダイムを超えることを初めて示す。

関連論文リスト

• Quantum Codes from $r$-Nearly Self-Orthogonal Linear Codes via Jordan Canonical Form over $\mathbb{F}_{q^2}$ [5.6342405886627]
  我々は、$F_q2$を超える任意の古典的線形符号から$q$ary量子安定化器符号を構築するためのヨルダン標準形式フレームワークを導入する。 このフレームワークは、双対を含む条件(すなわち自己直交性)を満たすために古典的な線形コード$mathcalC$を必要としない。 この構成を古典的な符号に適用すると、グラスルの表でよく知られたパラメータを改善または補足するいくつかの記録量子符号が生成される。
  論文  参考訳（メタデータ） (2026-07-14T00:58:42Z)
• The Complexity of Stoquastic Sparse Hamiltonians [0.30079490585515334]
  確率スパースハミルトン問題(mathsfStoqSH$)が$mathsfStoqMA$であることを示す。 Stoquastic Local Hamiltonian は $mathsfStoqMA$-hard であるため、$mathsfStoqSH$ は $mathsfStoqMA$-complete となる。 また、$mathsfStoqMA(2)$の分離可能なバージョンが$mathsfStoqMAであることも示します。
  論文  参考訳（メタデータ） (2026-05-04T17:22:02Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• More on genuine multi-entropy and holography [0.0]
  私たちは$rm GM[mathttq]$を体系的に$mathttq$に対して構築する方法の処方則を与えます。 一般的な$mathttq$の場合、$rm GM[mathttq]$は$N (mathttq)-p(mathttq-1)-1の自由パラメータの数を含む。 これらは$N (mathttq)+1$の真の$mathttqに対する新しい診断数を与える
  論文  参考訳（メタデータ） (2025-04-23T10:13:10Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。 まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。 我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
  論文  参考訳（メタデータ） (2024-01-03T09:12:25Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。 この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
  論文  参考訳（メタデータ） (2023-06-22T17:23:36Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)

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

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