論文の概要: Testing Boolean Functions Properties
- arxiv url: http://arxiv.org/abs/2109.06763v2
- Date: Tue, 9 Nov 2021 13:05:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 03:15:34.233484
- Title: Testing Boolean Functions Properties
- Title（参考訳）: ブール関数特性のテスト
- Authors: Zhengwei Xie, Daowen Qiu, Guangya Cai, Jozef Gruska, Paulo Mateus
- Abstract要約: 関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
- 参考スコア（独自算出の注目度）: 1.5924410290166868
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The goal in the area of functions property testing is to determine whether a
given black-box Boolean function has a particular given property or is
$\varepsilon$-far from having that property. We investigate here several types
of properties testing for Boolean functions (identity, correlations and
balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J)
problem) and also the amplitude amplification technique.
At first, we study here a particular testing problem: namely whether a given
Boolean function $f$, of $n$ variables, is identical with a given function $g$
or is $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We
present a one-sided error quantum algorithm to deal with this problem that has
the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that
our quantum algorithm is optimal. Afterwards we show that the classical
randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$.
Secondly, we consider the D-J problem from the perspective of functional
correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose
an exact quantum algorithm for making distinction between
$|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical
deterministic query complexity for this problem is $\Theta(2^{n})$ queries.
Finally, we propose a one-sided error quantum query algorithm for testing
whether one Boolean function is balanced versus $\varepsilon$-far balanced
using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum
algorithm for balancedness testing is optimal. At the same time, for this
balancedness testing problem we present a classical randomized algorithm with
query complexity of $O(1/\varepsilon^{2})$. Also this randomized algorithm is
optimal. Besides, we link the problems considered here together and generalize
them to the general case.
- Abstract（参考訳）: 関数の領域における特性テストの目的は、与えられたブラックボックスブール関数が特定のプロパティを持つかどうか、またはそのプロパティを持つから$\varepsilon$-farであるかどうかを決定することである。
本稿では、Deutsch-Jozsaアルゴリズム(Deutsch-Jozsa (D-J)問題)と振幅増幅法を用いてブール関数(同一性、相関性、平衡性)のいくつかの特性試験を行う。
例えば、ある Boolean 関数 $f$, of $n$ 変数が与えられた関数 $g$ と同一であるか、あるいは $g$ から $\varepsilon$-far か、$\varepsilon$ がパラメータである。
我々は、クエリの複雑性$o(\frac{1}{\sqrt{\varepsilon}})$を持つこの問題に対処するために、片側誤差量子アルゴリズムを提案する。
さらに,量子アルゴリズムが最適であることを示す。
その後、この問題の古典的ランダム化クエリ複雑性は$\Theta(\frac{1}{\varepsilon})$であることを示す。
次に、関数相関の観点からD-J問題を考察し、$C(f,g)$に$f$と$g$の相関を示す。
6つのクエリを用いて$|c(f,g)|=\varepsilon$と$|c(f,g)|=1$を区別するための厳密な量子アルゴリズムを提案する。
最後に,一方のboolean関数が$o(\frac{1}{\varepsilon})$クエリを使用して$\varepsilon$-farバランスであるかどうかをテストするための片面誤差量子クエリアルゴリズムを提案する。
また、バランス性テストのための量子アルゴリズムが最適であることを示す。
同時に、このバランス性テスト問題に対して、クエリ複雑性が$O(1/\varepsilon^{2})$の古典的ランダム化アルゴリズムを提案する。
また、このランダム化アルゴリズムは最適である。
さらに、ここで考慮した問題を結びつけ、一般的なケースに一般化します。
関連論文リスト
- The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - 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) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。
ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。
本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文 参考訳（メタデータ） (2019-12-31T14:52:36Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。