論文の概要: On converses to the polynomial method
- arxiv url: http://arxiv.org/abs/2204.12303v3
- Date: Wed, 20 Dec 2023 16:58:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 22:37:10.249860
- 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特性を適用する。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。
この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。
複素解析を用いた補体系に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-06T16:47:11Z) - 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) - 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.137457877869062]
アーロンソンらによる驚くべき「方法への反論」。
(CCC16) は、任意の有界二次体はグロタンディーク定数に関連する普遍乗法因子まで1-クエリで正確に計算できることを示した。
論文 参考訳（メタデータ） (2022-12-16T16:26:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。