論文の概要: Quantum algorithms for the Goldreich-Levin learning problem
- arxiv url: http://arxiv.org/abs/2001.00014v1
- Date: Tue, 31 Dec 2019 14:52:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 21:10:55.293852
- Title: Quantum algorithms for the Goldreich-Levin learning problem
- Title（参考訳）: goldreich-levin学習問題の量子アルゴリズム
- Authors: Hongwei Li
- Abstract要約: Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。
ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。
本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
- 参考スコア（独自算出の注目度）: 3.8849433921565284
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Goldreich-Levin algorithm was originally proposed for a cryptographic
purpose and then applied to learning. The algorithm is to find some larger
Walsh coefficients of an $n$ variable Boolean function. Roughly speaking, it
takes a $poly(n,\frac{1}{\epsilon}\log\frac{1}{\delta})$ time to output the
vectors $w$ with Walsh coefficients $S(w)\geq\epsilon$ with probability at
least $1-\delta$. However, in this paper, a quantum algorithm for this problem
is given with query complexity $O(\frac{\log\frac{1}{\delta}}{\epsilon^4})$,
which is independent of $n$. Furthermore, the quantum algorithm is generalized
to apply for an $n$ variable $m$ output Boolean function $F$ with query
complexity $O(2^m\frac{\log\frac{1}{\delta}}{\epsilon^4})$.
- Abstract（参考訳）: goldreich-levinアルゴリズムはもともと暗号目的で提案され、その後学習に応用された。
アルゴリズムは、$n$可変ブール関数のより大きなウォルシュ係数を見つけることである。
大まかに言えば、$poly(n,\frac{1}{\epsilon}\log\frac{1}{\delta})$ ベクターをウォルシュ係数$s(w)\geq\epsilon$ で出力するには、少なくとも 1-\delta$ で$s(w)\geq\epsilon$ がかかる。
しかし、本論文では、この問題に対する量子アルゴリズムは、クエリ複雑性 $o(\frac{\log\frac{1}{\delta}}{\epsilon^4})$ で与えられる。
さらに、量子アルゴリズムは、クエリ複雑性$o(2^m\frac{\log\frac{1}{\delta}}{\epsilon^4})$を持つ$n$変数$m$出力ブール関数$f$に適用するように一般化される。
関連論文リスト
- Learning low-degree quantum objects [5.2373060530454625]
低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。
我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
論文 参考訳（メタデータ） (2024-05-17T17:36:44Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文 参考訳（メタデータ） (2021-09-14T15:27:38Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。