論文の概要: Fast Quantum Algorithms for Learning Linear Threshold Functions
- arxiv url: http://arxiv.org/abs/2609.40331v2
- Date: Mon, 05 Oct 2026 16:18:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.492279
- Title: Fast Quantum Algorithms for Learning Linear Threshold Functions
- Title（参考訳）: 線形閾値関数学習のための高速量子アルゴリズム
- Abstract要約: 線形しきい値関数は$f_w,(x)=textsign(langle x,w rangle -)$であり、重みベクトル$winmathbbRn$は単位ベクトルである。
LTFの学習には3つの肯定的な結果が得られた。
- 参考スコア（独自算出の注目度）: 42.535091514980515
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Linear threshold functions are $f_{w,θ}(x)=\text{sign}(\langle x,w \rangle -θ)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $θ\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $θ=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,θ}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,θ}$ up to Euclidean error $ε$ using $O(\log(n/ε))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,θ}$ up to error $O(ε)$ when $x$ is Gaussian. Classical algorithms need $Ω(n\log(1/ε))$ queries. 2. A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) quantum examples under Gaussian measure, corresponding to $\int_x \sqrt{γ_n(x)}|x\rangle |f_w(x)\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs $f_w$ with error $ε$ under the Gaussian distribution, using $O(n^{1/4}/\sqrtε)$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/ε^4)$ other gates.
- Abstract（参考訳）: 線形しきい値関数は$f_{w,θ}(x)=\text{sign}(\langle x,w \rangle -θ)$、重みベクトル$w\in\mathbb{R}^n$は単位ベクトル、$θ\in\mathbb R$はしきい値、通常$x\in\mathbb{R}^n$または$x\in\mathbb{-1,1\}^n$である。
θ=0$ の場合、LTF は同次 (homogeneous) と呼ばれ、$f_w:=f_{w,0}$ と書く。
このような関数は、正および負の例を線形に識別するのに役立つため、機械学習において最も重要な対象の一つである。
1. 実ドメインクエリを作成できる、つまり、$f_{w,θ}(x)$を任意の$x\in\mathbb{R}^n$で計算できるとする。
我々は$f_{w,θ}$から$O(\log(n/ε))$メンバシップクエリと$\widetilde{O}(n)$他のゲートを用いてユークリッド誤差$ε$を学ぶ量子アルゴリズムを与える。
さらに、$f_{w,θ}$ up to error $O(ε)$ when $x$ is Gaussian も学んだ。
古典的なアルゴリズムには$Ω(n\log(1/ε))$クエリが必要である。
2 の同質 LTF $f_w$ on domain $\{-1,1\}^n$ ここで、$w$ は同じ値の 0 でないエントリの$k$ しか持たないのは、$w$ のサポート上のMajority 関数である。
Belovs氏は、隠れたサポートを正確に識別する境界付きエラー量子アルゴリズムを、$O(k^{1/4})$クエリを使って(従って$f_w$を学習する)。
我々は$O(\log k)$クエリを使って指数関数的に改善する。
3. ガウス測度の下で(離散化)量子例を生成できるユニタリ$U$が、$\int_x \sqrt{γ_n(x)}|x\rangle |f_w(x)\rangle dx$に対応すると仮定する。
これは、メンバシップクエリよりも弱いアクセスモデルです。
ガウス分布の下での誤差$ε$を学習するために、Jain et al の効率的な Hermite 変換に基づく量子アルゴリズムを、$O(n^{1/4}/\sqrtε)$$$U$および$U^\dagger$および$\widetilde{O}(n^2/ε^4)$他のゲートの応用を用いて与える。
関連論文リスト
- A Simple Algorithm for Best Separable State [5.5559749120901385]
本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。
古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
論文 参考訳（メタデータ） (2026-08-10T19:04:15Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals [5.7652356955571085]
i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。
我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
論文 参考訳（メタデータ） (2026-05-26T19:07:06Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳（メタデータ） (2025-09-25T07:39:25Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。