論文の概要: 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。