論文の概要: Grothendieck inequalities characterize converses to the polynomial method
- arxiv url: http://arxiv.org/abs/2212.08559v3
- Date: Tue, 12 Nov 2024 14:04:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-13 13:16:23.580796
- Title: Grothendieck inequalities characterize converses to the polynomial method
- Title（参考訳）: グロタンディークの不等式は多項式法への逆を特徴づける
- Authors: Jop Briët, Francisco Escudero Gutiérrez, Sander Gribling,
- Abstract要約: アーロンソンらによる驚くべき「方法への反論」。
(CCC16) は、任意の有界二次体はグロタンディーク定数に関連する普遍乗法因子まで1-クエリで正確に計算できることを示した。
- 参考スコア（独自算出の注目度）: 1.137457877869062
- License:
- 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-クエリ量子アルゴリズムの観点からグロタンディーク定数の新たな特徴づけを与える。
その過程で、フォームの完全有界ノルムとその双対ノルムの再構成を提供する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Revisiting Tropical Polynomial Division: Theory, Algorithms and
Application to Neural Networks [40.137069931650444]
熱帯幾何学は、最近、一方向線形活性化関数を持つニューラルネットワークの解析にいくつかの応用を見出した。
本稿では,熱帯分断問題に対する新たな考察とニューラルネットワークの単純化への応用について述べる。
論文 参考訳（メタデータ） (2023-06-27T02:26:07Z) - 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.6385815610837167]
本稿では,通勤変数とその形式的混合モーメントの表現であるモーメント表現の枠組みを紹介し,開発する。
応用として、量子物理学からの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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。