論文の概要: The Compressed Oracle is a Worthy (Multiplicative) Adversary

• arxiv url: http://arxiv.org/abs/2509.07876v1
• Date: Tue, 09 Sep 2025 15:58:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-10 14:38:27.390819
• Title: The Compressed Oracle is a Worthy (Multiplicative) Adversary
• Title（参考訳）: 圧縮されたOracleは(多種多様な)敵である
• Authors: Stacey Jeffery, Sebastian Zur,
• Abstract要約: 圧縮オラクル法は乗算逆法の特殊な場合であることを示す。 これにより、MLADV法は、圧縮されたオラクル法を非生産物分布に拡張する現在の探索において有望な方向になる可能性がある。
• 参考スコア（独自算出の注目度）: 0.08594140167290097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The compressed oracle technique, introduced in the context of quantum cryptanalysis, is the latest method for proving quantum query lower bounds, and has had an impressive number of applications since its introduction, due in part to the ease of importing classical lower bound intuition into the quantum setting via this method. Previously, the main quantum query lower bound methods were the polynomial method, the adversary method, and the multiplicative adversary method, and their relative powers were well understood. In this work, we situate the compressed oracle technique within this established landscape, by showing that it is a special case of the multiplicative adversary method. To accomplish this, we introduce a simplified restriction of the multiplicative adversary method, the MLADV method, that remains powerful enough to capture the polynomial method and exhibit a strong direct product theorem, but is much simpler to reason about. We show that the compressed oracle technique is also captured by the MLADV method. This might make the MLADV method a promising direction in the current quest to extend the compressed oracle technique to non-product distributions.
• Abstract（参考訳）: 量子暗号解析の文脈で導入された圧縮オラクル技術は、量子クエリの下界を証明する最新の方法であり、この方法を通じて古典的な下界直観を量子環境にインポートすることの容易さから、その導入以来、驚くほど多くのアプリケーションがある。 従来,主量子クエリローバウンド法は,多項式法,逆法,乗算逆法であり,その相対力はよく理解されていた。 本研究は,本手法が乗算逆法の特殊な場合であることを示すことにより,この確立した景観内に圧縮されたオラクル手法を配置する。 これを実現するために,乗法逆法MLADV法を単純化した制限を導入する。これは多項式法を捕捉し,強い直積定理を示すのに十分強力だが,推論ははるかに簡単である。 また, MLADV法により, 圧縮オラクル法も捉えることができる。 これにより、MLADV法は、圧縮されたオラクル法を非生産物分布に拡張する現在の探索において有望な方向になる可能性がある。

関連論文リスト

• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods [37.1630298053787]
  我々はヘルパーフレームワークと呼ばれる新しいフレームワークを提案する。 グローバルな複雑性保証を備えた分散アルゴリズムと二階アルゴリズムの統一的なビューを提供する。
  論文  参考訳（メタデータ） (2023-02-23T12:18:28Z)
• A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
  逆法に(双対の形で)方法から単純かつ直接的に還元する。 これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
  論文  参考訳（メタデータ） (2023-01-24T21:37:20Z)
• Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle [16.290192687098383]
  本稿では,アフィン制約を伴う凸複合最適化問題について考察する。 正確なプロジェクション/近距離計算が難解な高次元アプリケーションにより,テキスト投影のないラグランジアン型拡張手法を提案する。
  論文  参考訳（メタデータ） (2022-10-25T12:51:43Z)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  モーフィファイド相互作用エネルギー降下(MIED)と呼ばれる新しい最適化に基づくサンプリング手法を提案する。 MIEDは、モル化相互作用エネルギー(MIE)と呼ばれる確率測度に関する新しいクラスのエネルギーを最小化する 我々は,制約のないサンプリング問題に対して,我々のアルゴリズムがSVGDのような既存の粒子ベースアルゴリズムと同等に動作することを示す。
  論文  参考訳（メタデータ） (2022-10-24T16:54:18Z)
• A new method for directly computing reduced density matrices [0.0]
  オープン量子系の減密度行列要素の摂動計算を可能にする第1原理に基づく実用的手法のパワーを実証する。 このアプローチは、熱場力学、シュウィンガー・ケルドシーの公式主義、ファインマン・ヴァーノンの影響関数のような非平衡量子場理論の技法に基づいている。
  論文  参考訳（メタデータ） (2022-04-19T11:58:36Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLEは、局所的、計量的項と大域的、位相的項の両方で損失関数を最小化し、初期埋め込みを補正する次元推論後処理ステップである。 DIPOLEは、UMAP、t-SNE、Isomapといった一般的な手法よりも多くの一般的なデータセットで優れています。
  論文  参考訳（メタデータ） (2021-06-14T17:19:44Z)
• Understanding Nesterov's Acceleration via Proximal Point Method [52.99237600875452]
  近似点法(PPM)は最適化アルゴリズムを設計するためのビルディングブロックとしてよく用いられる。 本研究では、PPM法を用いて、Nesterovの加速度勾配法(AGM)の異なるバージョンの収束解析とともに、概念的に単純な導出を提供する。
  論文  参考訳（メタデータ） (2020-05-17T17:17:18Z)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  そこでは,この知識を最適な値である$f_*$で置き換える。 まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
  論文  参考訳（メタデータ） (2020-02-03T17:50:28Z)

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

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