論文の概要: On converses to the polynomial method
- arxiv url: http://arxiv.org/abs/2204.12303v2
- Date: Thu, 6 Oct 2022 12:29:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 12:04:16.835468
- Title: On converses to the polynomial method
- Title(参考訳): 多項式法への逆について
- Authors: Jop Bri\"et and Francisco Escudero Guti\'errez
- Abstract要約: アーロンソンらによる驚くべき「方法への逆」は、任意の有界二次函数は、グロエンディーク定数に関連する普遍的乗法因子まで正確に計算できることを示している。
小さい加法誤差を許容した場合、結果が依然として成り立つことを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16)
shows that any bounded quadratic polynomial can be computed exactly in
expectation by a 1-query algorithm up to a universal multiplicative factor
related to the famous Grothendieck constant. A natural question posed there
asks if bounded quartic polynomials can be approximated by $2$-query quantum
algorithms. Arunachalam, Palazuelos and the first author showed that there is
no direct analogue of the result of Aaronson et al. in this case. We improve on
this result in the following ways: First, we point out and fix a small error in
the construction that has to do with a translation from cubic to quartic
polynomials. Second, we give a completely explicit example based on techniques
from additive combinatorics. Third, we show that the result still holds when we
allow for a small additive error. For this, we apply an SDP characterization of
Gribling and Laurent (QIP'19) for the completely-bounded approximate degree.
- Abstract(参考訳): Aaronson et al. (CCC'16) の驚くべき「多項式法への逆」は、任意の有界二次多項式は、有名なグロタンディーク定数に関連する普遍的乗法係数まで1-クエリアルゴリズムによって正確に計算できることを示している。
そこで提起された自然の質問は、有界なクォート多項式が2$キューリー量子アルゴリズムによって近似できるかどうかを問うものである。
arunachalam, palazuelos, そして最初の著者は、aaronsonらの結果の直接的な類似性がないことを示した。
まず、立方体からクォート多項式への変換に関係のある構成において小さな誤りを指摘し、修正する。
第二に、加法コンビネータの技法に基づく完全に明示的な例を示す。
第3に,小さな加算誤差を許容した場合,結果が持続することを示す。
これに対し、完全有界近似度に対して、Gribling and Laurent (QIP'19) のSDP特性を適用する。
関連論文リスト
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳(メタデータ) (2023-11-18T04:41:07Z) - Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic
Structure of Swap Operators [0.6395217718928152]
量子マックスカット(QMC)問題は、局所ハミルトン問題に対する近似アルゴリズムを設計するためのテスト確率として登場した。
本稿では,非可換な正方形最適化手法であるncSoSを拡張し,量子マックスカットに緩和の新たな階層を与える。
この論文の2つ目の大きな貢献は、あるグラフに対するQMCハミルトンの最大固有値を正確に計算する一般化時アルゴリズムである。
論文 参考訳(メタデータ) (2023-07-28T16:45:16Z) - Influences of Fourier Completely Bounded Polynomials and Classical
Simulation of Quantum Algorithms [0.0]
量子クエリアルゴリズムは、フーリエ完全有界な新しいクラスによって特徴づけられることを示す。
我々は、すべてのそのような変数は影響のある変数を持つと推測する。
我々の証明は単純で、より良い定数を得ることができ、ランダム性を使用しない。
論文 参考訳(メタデータ) (2023-04-13T17:58:36Z) - A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
逆法に(双対の形で)方法から単純かつ直接的に還元する。
これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
論文 参考訳(メタデータ) (2023-01-24T21:37:20Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳(メタデータ) (2023-01-22T22:08:28Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Grothendieck inequalities characterize converses to the polynomial
method [1.024113475677323]
アーロンソンらによる驚くべき「方法への反論」。
(CCC16) は、任意の有界二次体はグロタンディーク定数に関連する普遍乗法因子まで1-クエリで正確に計算できることを示した。
論文 参考訳(メタデータ) (2022-12-16T16:26:04Z) - Polynomial computational complexity of matrix elements of
finite-rank-generated single-particle operators in products of finite bosonic
states [0.0]
A$ が有限ランク行列である行列の永久計算は行列サイズで多くの演算を必要とすることが知られている。
この結果は行列の恒常的な一般化に拡張する: 境界数のボソンを持つ多くの同一のボゾン状態の積の期待値である。
論文 参考訳(メタデータ) (2022-10-20T20:09:28Z) - Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms [3.9156637371363874]
Aaronson-Ambainis予想を証明する(Theory of Computing '14)
すべての完全有界次数-$d$ブロック-多重線型形式において、常に影響が少なくとも1/mathrmpoly(d)$の変数が存在する。
我々は、量子アルゴリズムの特定のクラスに対する効率的な古典的ほぼすべてのところのシミュレーションを得る。
論文 参考訳(メタデータ) (2022-03-01T03:42:24Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳(メタデータ) (2020-02-22T01:03:33Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳(メタデータ) (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。