Fugu-MT 論文翻訳(概要): An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

論文の概要: An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

arxiv url: http://arxiv.org/abs/2301.09218v1
Date: Sun, 22 Jan 2023 22:08:28 GMT
ステータス: 処理完了
システム内更新日: 2023-01-24 14:28:28.713422
Title: An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Title（参考訳）: 量子クエリ複雑性と多項式次数の指数的分離
Authors: Andris Ambainis and Aleksandrs Belovs
Abstract要約: 本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
参考スコア（独自算出の注目度）: 79.43134049617873
License: http://creativecommons.org/licenses/by/4.0/
Abstract: While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation.
Abstract（参考訳）: 量子クエリ複雑性と全関数の多項式次数の間には多項式分離が少なくとも存在することは知られているが、この2つの間の正確な関係は部分関数に対しては明確ではない。本稿では,部分ブール関数に対する完全多項式次数と近似量子クエリ複雑性の指数関数的分離を実証する。非有界なアルファベットサイズでは、定数対多項式分離がある。

関連論文リスト

Krylov complexity in quantum field theory, and beyond [68.8204255655161]
量子場理論の様々なモデルにおけるクリロフ複雑性について研究する。クリロフ複雑性の指数的成長は、カオス上のマルダセナ-シェンカー-スタンフォード境界を一般化する対物的不等式を満たす。
論文参考訳（メタデータ） (2022-12-29T19:00:00Z)
Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions [23.96475985648844]
修正線形単位を用いたディープニューラルネットワークは、連続的ピースワイド線形関数(CPWL)を表す。最近の研究では、任意のCPWL関数を正確に表すために必要なニューロンの数は、ピースの数と指数関数的に増加するか、あるいは異なる線形成分の数の因子として指数関数的に増加すると推定されている。本稿では、より厳密な境界を提案し、任意のCPWL関数に対してこれらの境界を満たすネットワークを見つけるための時間アルゴリズムを確立する。
論文参考訳（メタデータ） (2022-10-13T17:58:41Z)
Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
フォースター変換 (Forster transform) は、分布を優れた反集中特性を持つものに変換する演算である。本稿では,Forster変換が存在し,効率よく計算できる少数の分布の解離混合として,任意の分布を効率的に分解可能であることを示す。
論文参考訳（メタデータ） (2021-07-12T17:00:59Z)
Sums of Separable and Quadratic Polynomials [0.3222802562733786]
我々は分離可能プラス二次(SPQ)を研究します。凸spq最適化問題は「小さな」半定義プログラムによって解決できることを示す。
論文参考訳（メタデータ） (2021-05-11T03:26:46Z)
Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文参考訳（メタデータ） (2021-03-19T16:34:20Z)
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。私たちの後悔の限界はエピソードの数とは無関係です。
論文参考訳（メタデータ） (2020-11-09T18:32:22Z)
Complexity aspects of local minima and related notions [3.42658286826597]
我々は (i) 臨界点、 (ii) 二次点、 (iii) 局所ミニマ、 (iv) 多変量に対する厳密な局所ミニマの概念を考える。立方体が臨界点を持つかどうかを決定することはNPハードであることを示す。本稿では,3階ニュートン法の設計における局所最小値立方体探索の可能性について概説する。
論文参考訳（メタデータ） (2020-08-14T00:50:13Z)
SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。実験では最先端のアルゴリズムよりも優れています。
論文参考訳（メタデータ） (2020-02-22T01:03:33Z)
Pseudo-dimension of quantum circuits [0.0]
量子回路の出力確率に擬似次元境界を証明した。既知のサイズと深さの回路がPAC学習可能であることを示す。
論文参考訳（メタデータ） (2020-02-04T19:00:13Z)
Matrix product operator representation of polynomial interactions [0.0]
格子サイト分離を行列積演算子(MPO)として指数関数として成長する1次元格子上の相互作用ハミルトニアンの正確な構成を提供する。本研究は,多体量子演算子の相関構造に関する新たな知見を提供するとともに,対話を指数的に探索する多体系のシミュレーションにも有効である可能性が示唆された。
論文参考訳（メタデータ） (2020-01-14T04:15:32Z)

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