論文の概要: Grothendieck inequalities characterize converses to the polynomial
method
- arxiv url: http://arxiv.org/abs/2212.08559v2
- Date: Sat, 30 Dec 2023 12:26:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 02:54:31.819754
- Title: Grothendieck inequalities characterize converses to the polynomial
method
- Title(参考訳): グロタンディークの不等式は多項式法に逆を特徴づける
- Authors: Jop Bri\"et, Francisco Escudero Guti\'errez and Sander Gribling
- Abstract要約: アーロンソンらによる驚くべき「方法への反論」。
(CCC16) は、任意の有界二次体はグロタンディーク定数に関連する普遍乗法因子まで1-クエリで正確に計算できることを示した。
- 参考スコア(独自算出の注目度): 1.024113475677323
- 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. Here we show that such a result
does not generalize to quartic polynomials and 2-query algorithms, even when we
allow for additive approximations. We also show that the additive approximation
implied by their result is tight for bounded bilinear forms, which gives a new
characterization of the Grothendieck constant in terms of 1-query quantum
algorithms. Along the way we provide reformulations of the completely bounded
norm of a form, and its dual norm.
- Abstract(参考訳): Aaronson et al. (CCC'16) の驚くべき「多項式法への逆」は、任意の有界二次多項式は、有名なグロタンディーク定数に関連する普遍的乗法係数まで1-クエリアルゴリズムによって正確に計算できることを示している。
ここでは、加法近似を許容しても、そのような結果はクォート多項式や2-クエリアルゴリズムに一般化されないことを示す。
また、それらの結果から示唆される加法近似は有界双線型形式に対して密接であり、1-クエリ量子アルゴリズムの観点からグロタンディーク定数の新たな特徴付けを与える。
その過程で、形式の全有界ノルムとその双対ノルムの再構成を提供する。
関連論文リスト
- Spectral quantization of discrete random walks on half-line, and
orthogonal polynomials on the unit circle [0.0]
我々は、単位円上のバーブの観点で量子ウォークのユニタリ進化作用素を表す。
マルコフ系とそれらの測度の両方が古典的なSzegHo写像によって連結されていることを示す。
論文 参考訳(メタデータ) (2023-06-21T13:41:51Z) - Sums of squares certificates for polynomial moment inequalities [1.7725414095035827]
本稿では,通勤変数とその形式的混合モーメントにおける表現であるモーメント表現の枠組みを紹介し,開発する。
擬モーメントに対するヒルベルトの17番目の問題に対する正の解が与えられる。
応用として、量子物理学からの2つの非線形ベル不等式が解決される。
論文 参考訳(メタデータ) (2023-06-09T08:55:26Z) - 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) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
ガウスのプロセスはデータセットのサイズとともに違法にスケールする。
多くの近似法が開発されており、必然的に近似誤差を導入している。
この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。
本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
論文 参考訳(メタデータ) (2022-05-30T22:16:25Z) - On converses to the polynomial method [0.0]
アーロンソンらによる驚くべき「方法への逆」は、任意の有界二次函数は、グロエンディーク定数に関連する普遍的乗法因子まで正確に計算できることを示している。
小さい加法誤差を許容した場合、結果が依然として成り立つことを示す。
論文 参考訳(メタデータ) (2022-04-26T13:32:02Z) - 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) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。
本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
論文 参考訳(メタデータ) (2020-12-03T17:54:03Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳(メタデータ) (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。