論文の概要: A Direct Reduction from the Polynomial to the Adversary Method

• arxiv url: http://arxiv.org/abs/2301.10317v1
• Date: Tue, 24 Jan 2023 21:37:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-26 16:22:57.605871
• Title: A Direct Reduction from the Polynomial to the Adversary Method
• Title（参考訳）: 多項式から逆法への直接的還元
• Authors: Aleksandrs Belovs
• Abstract要約: 逆法に(双対の形で)方法から単純かつ直接的に還元する。 これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
• 参考スコア（独自算出の注目度）: 92.54311953850168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.
• Abstract（参考訳）: 多項式と逆法は、量子アルゴリズムのクエリ複雑性に対する下界を証明する2つの主要なツールである。 どちらの方法も多くのアプリケーションを見つけており、いくつかの問題は1つの方法に適している。 逆法は一般の負重み付きバージョンでは有界誤差量子アルゴリズムでは厳密であるが、多項式法はそうではないことが知られている。 前者の厳密性により、任意の多項式下界に対して、対応する逆下界が存在するべきである。 しかし、直接の削減は分かっていない。 本稿では, 逆多項式法に対して, 多項式法(二重多項式の形で) から逆多項式法へ単純かつ直接還元する。 これは、双対多項式の形の任意の下界が、実際には特定の形式の逆下界であることを示している。

関連論文リスト

• Complementary polynomials in quantum signal processing [0.0]
  与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。 この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。 複素解析を用いた補体系に対する新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-06T16:47:11Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• A degree reduction method for an efficient QUBO formulation for the graph coloring problem [0.32985979395737774]
  本稿では,自由マンと石川が導入した従来の次数還元法を一般化した二乗変数の斉次対称に対する新しい次数還元法を提案する。 また、2変数の一般に対する次数削減アルゴリズムを設計し、ランダムグラフのグラフ彩色問題にシミュレートし、従来の手法と比較した。
  論文  参考訳（メタデータ） (2023-06-21T07:56:56Z)
• Sparse resultant based minimal solvers in computer vision and their connection with the action matrix [17.31412310131552]
  いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。 コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
  論文  参考訳（メタデータ） (2023-01-16T14:25:19Z)
• Grothendieck inequalities characterize converses to the polynomial method [1.137457877869062]
  アーロンソンらによる驚くべき「方法への反論」。 (CCC16) は、任意の有界二次体はグロタンディーク定数に関連する普遍乗法因子まで1-クエリで正確に計算できることを示した。
  論文  参考訳（メタデータ） (2022-12-16T16:26:04Z)
• On converses to the polynomial method [0.0]
  アーロンソンらによる驚くべき「方法への逆」は、任意の有界二次函数は、グロエンディーク定数に関連する普遍的乗法因子まで正確に計算できることを示している。 小さい加法誤差を許容した場合、結果が依然として成り立つことを示す。
  論文  参考訳（メタデータ） (2022-04-26T13:32:02Z)
• l1-Norm Minimization with Regula Falsi Type Root Finding Methods [81.55197998207593]
  Regula Falsiルートフィンディング技術を使用して、非可能性に対する効率的なアプローチを開発します。 実用的性能は l1 正規化クラス t を用いて示される。
  論文  参考訳（メタデータ） (2021-05-01T13:24:38Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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