論文の概要: Quantum Query Lower Bounds from Classical Moment Matching
- arxiv url: http://arxiv.org/abs/2611.05117v1
- Date: Tue, 03 Nov 2026 16:07:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 14:21:46.85023
- Title: Quantum Query Lower Bounds from Classical Moment Matching
- Title（参考訳）: 古典的モーメントマッチングによる量子クエリの低いバウンド
- Abstract要約: 我々は、古典的モーメントマッチング法の量子類似性を証明し、特性試験において低い境界を証明した。
我々の結果は、新しい連続的ハイブリッド引数と非競合的手法を組み合わせたものである。
このフレームワークの主な利点は単純さであり、量子的下界証明を適切なモーメントマッチング分布の構成に還元する。
- 参考スコア（独自算出の注目度）: 1.5267236995686553
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables $X_0$ and $X_1$ whose moments match up to the first $r-1$ moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length $N$ constructed from $X_0$ and $X_1$, respectively, unless it performs at least $Ω(N^{1-1/r})$ queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as $Ω(N^{1/2-1/(2r)})$, while our second moment matching theorem yields a sharper lower bound of $Ω(N^{1/2-1/(2(2^r-1))})$, albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on $k$-distinctness, $k$-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and $K$-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.
- Abstract（参考訳）: 本研究では,古典的モーメントマッチング手法の量子類似性を証明する。
2つの確率変数 $X_0$ と $X_1$ のモーメントが最初の$r-1$ モーメントと一致する場合、古典的なモーメントマッチング法では、少なくとも$Ω(N^{1-1/r})$クエリを実行しなければ、それぞれ$X_0$ と $X_1$ から構築された長さの入力インスタンスを確実に区別できない。
この手法はRaskhodnikova、Ron、Shpilka、Smith (STOC 2007) のセミナルな研究から広く研究されてきたが、量子的類似性を証明できるかどうかは未解決のままである。
この量子モーメントマッチング法の2つの変種を証明する。
第1の量子クエリは$Ω(N^{1/2-1/(2r)})$、第2のモーメントマッチング定理はよりシャープな$Ω(N^{1/2-1/(2(2^r-1))}$、より小さいパラメータ範囲に対してアルベットとなる。
この結果は、新しい連続ハイブリッド引数と多項式法を組み合わせたものである。
連続ハイブリッド引数は、サンプルから生成される2つのハード入力分布を、両方の分布を連続的に変化させることで比較し、中間段階ごとに同一に分布し続ける。
単一のサンプルの分布を変える効果と比較する。
多項式法は一致したモーメントによって決定される条件をキャンセルする。
我々はこれらのモーメントマッチング定理を適用し、$k$-distinctness,$k$-star-freeness,$k$-planarity and outerplanarity testingの新たな最適下界を証明し、画像サイズ検定や対数係数による$K$-junta testの事前下界を改善する。
このフレームワークの主な利点は単純さであり、量子的下界証明を適切なモーメントマッチング分布の構成に還元する。
関連論文リスト
- Two-Sample Testing via Generative Processes [60.42943145582429]
生成輸送は、2つのサンプルが同じ分布から来るかどうかを決定する新しい方法を提供する。
2つのサンプルの間に直接補間体を構築し、対称スケジュールでは、その法則が時間反射の下で不変であることを観察する。
したがって、t と 1-t の辺辺が、Jensen-Shannon の発散を計算することで一致するかどうかをテストする。
論文 参考訳（メタデータ） (2026-10-06T12:48:27Z) - Tight bounds for hybrid quantum-classical query algorithms [0.45880283710344066]
クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。
状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。
論文 参考訳（メタデータ） (2026-10-05T17:53:05Z) - A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds [1.3254304182988286]
我々は、ソートのための最初の完全な量子時空間トレードオフを証明した。
ノイズ演算子引数を適用するには、純粋に古典的な推論が必要です。
また、強い普遍的なハッシュ関数ファミリである$H$を$n$bitsから$m$bitsにすると、ほぼすべてのハッシュ関数が$H$で、少なくとも$S$qubitsのメモリを持つアルゴリズムを必要とすることを証明するためにも使用しています。
論文 参考訳（メタデータ） (2026-09-30T17:57:33Z) - Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。
非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
論文 参考訳（メタデータ） (2026-09-03T13:06:12Z) - A Lower Bound Framework for Quantum Functional Estimation [13.491187998442596]
我々は、$d$次元量子状態の関数を推定するための下界の証明のための統一的なフレームワークを開発する。
このフレームワークは、Haar-randomのモーメントエンコーディングプロセスとモーメントマッチングと最適な近似を組み合わせる。
論文 参考訳（メタデータ） (2026-08-03T17:59:11Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下界を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
論文 参考訳（メタデータ） (2023-08-03T14:41:49Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。