論文の概要: Optimal Quantum Algorithm for Vector Interpolation

• arxiv url: http://arxiv.org/abs/2212.03939v1
• Date: Wed, 7 Dec 2022 20:08:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-09 17:04:28.230253
• Title: Optimal Quantum Algorithm for Vector Interpolation
• Title（参考訳）: ベクトル補間のための最適量子アルゴリズム
• Authors: Sophie Decoppet
• Abstract要約: 本研究では,Childsらによって設計されたIn量子アルゴリズムを用いて学習できる関数について検討する。 成功確率は、大きめの$q$と大域の$|mathcalV|に対して1に近づく。 この成功確率を達成するのに必要なクエリ数に対する保守的な公式を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study the functions that can be learned through the polynomial interpolation quantum algorithm designed by Childs et al. This algorithm was initially intended to find the coefficients of a multivariate polynomial function defined on finite fields $\mathbb{F}_q$. We extend its scope to vector inner product functions of the form $\mathcal{O}_{\mathbf{s}}(\mathbf{v}) = \mathbf{s}\cdot\mathbf{v}$ where the goal is to find the vector $\mathbf{s} \in \mathbb{F}_q^n$. We examine the necessary conditions on the domain $\mathcal{V}$ of $\mathcal{O}_{\mathbf{s}}$ and prove that the algorithm is optimal for such functions. Furthermore, we show that the success probability approaches 1 for large $q$ and large domain order $|\mathcal{V}|.$ Finally, we provide a conservative formula for the number of queries required to achieve this success probability.
• Abstract（参考訳）: 本稿では,Childsらによって設計された多項式補間量子アルゴリズムを用いて学習可能な関数について検討する。 このアルゴリズムは当初、有限体 $\mathbb{f}_q$ で定義される多変数多項式関数の係数を求めることを意図していた。 我々は、その範囲を $\mathcal{O}_{\mathbf{s}}(\mathbf{v}) = \mathbf{s}\cdot\mathbf{v}$ という形のベクトル内積関数に拡張し、そこではベクトル $\mathbf{s} \in \mathbb{F}_q^n$ を求める。 我々は、$\mathcal{v}$ of $\mathcal{o}_{\mathbf{s}}$という領域に必要な条件を調べ、そのような関数に対してアルゴリズムが最適であることを示す。 さらに、大きな$q$ と大きなドメインオーダー $|\mathcal{v}| に対して成功確率が 1 に近づくことを示した。 最後に、私たちはこの成功の確率を達成するのに必要なクエリ数に関する保守的な公式を提供します。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Local approximation of operators [0.0]
  距離空間 $mathfrakX$ と $mathfrakY$ の間の非線形作用素の近似の度合いを決定する問題について検討する。 例えば、$mathbbSd$ の近似に関係する定数は $mathcalO(d1/6)$ である。
  論文  参考訳（メタデータ） (2022-02-13T19:28:34Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Interpolating Log-Determinant and Trace of the Powers of Matrix $\mathbf{A} + t \mathbf{B}$ [1.5002438468152661]
  関数 $t mapto log det left( mathbfA + t mathbfB right)$ and $t mapto nametraceleft (mathbfA + t mathbfB)p right)$ ここで行列 $mathbfA$ と $mathbfB$ はエルミート的で正(半)で、$p$ と $t$ は実変数である。
  論文  参考訳（メタデータ） (2020-09-15T23:11:17Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。