論文の概要: Classical-Quantum Separations in Certain Classes of Boolean Functions--
Analysis using the Parity Decision Trees
- arxiv url: http://arxiv.org/abs/2004.12942v3
- Date: Fri, 4 Sep 2020 12:34:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 00:03:21.706908
- Title: Classical-Quantum Separations in Certain Classes of Boolean Functions--
Analysis using the Parity Decision Trees
- Title（参考訳）: ブール関数のある種のクラスにおける古典量子分離-パリティ決定木を用いた解析
- Authors: Chandra Sekhar Mukherjee and Subhamoy Maitra
- Abstract要約: まず、$n$変数上のQuery Friendly(QF)関数を、最小決定論的クエリ複雑性を持つ関数として定義します。
各$n$に対して、$D(f)=Q_E(f)$ となるような非分離QF関数のクラスが存在することを示す。
関連する取り組みとして,Maiorana McFarland (M-M) 型ベント関数についても検討する。
- 参考スコア（独自算出の注目度）: 3.652509571098291
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study the separation between the deterministic (classical)
query complexity ($D$) and the exact quantum query complexity ($Q_E$) of
several Boolean function classes using the parity decision tree method. We
first define the Query Friendly (QF) functions on $n$ variables as the ones
with minimum deterministic query complexity $(D(f))$. We observe that for each
$n$, there exists a non-separable class of QF functions such that
$D(f)=Q_E(f)$. Further, we show that for some values of $n$, all the QF
functions are non-separable. Then we present QF functions for certain other
values of $n$ where separation can be demonstrated, in particular,
$Q_E(f)=D(f)-1$. In a related effort, we also study the Maiorana McFarland
(M-M) type Bent functions. We show that while for any M-M Bent function $f$ on
$n$ variables $D(f) = n$, separation can be achieved as $\frac{n}{2} \leq
Q_E(f) \leq \lceil \frac{3n}{4} \rceil$. Our results highlight how different
classes of Boolean functions can be analyzed for classical-quantum separation
exploiting the parity decision tree method.
- Abstract（参考訳）: 本稿では、パリティ決定木法によるブール関数クラスの決定論的(古典的)クエリ複雑性(D$)と正確な量子クエリ複雑性(Q_E$)の分離について検討する。
まず、$n$変数上のクエリフレンドリ(qf)関数を最小決定論的クエリ複雑性$(d(f))$を持つ関数として定義します。
各$n$に対して、$D(f)=Q_E(f)$ となるような QF 関数の非分離類が存在することを観察する。
さらに、ある値$n$に対して、すべてのQF関数は非分離であることを示す。
次に、分離を実証できる$n$の他の値に対するQF関数、特に$Q_E(f)=D(f)-1$を示す。
関連する取り組みとして,Maiorana McFarland (M-M) 型ベント関数についても検討する。
任意の M-M ベント関数 $f$ on $n$ variables $D(f) = n$ に対して、分離は $\frac{n}{2} \leq Q_E(f) \leq \lceil \frac{3n}{4} \rceil$ として達成できることを示す。
本稿では,パリティ決定木法を応用した古典量子分離のためにブール関数の異なるクラスを解析できることを示す。
関連論文リスト
- Space-bounded quantum interactive proof systems [2.623117146922531]
空間有界量子対話型証明システムの2つのモデル、$sf QIPL$と$sf QIP_rm UL$を紹介する。
$sf QIP_rm UL$モデルは、検証動作をユニタリ回路に制限する。対照的に、$sf QIPL$は検証動作ごとに、対数的に多くの中間測定を可能にする。
論文 参考訳（メタデータ） (2024-10-31T14:11:08Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - On polynomially many queries to NP or QMA oracles [0.0]
本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。
まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。
次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
論文 参考訳（メタデータ） (2021-11-03T15:29:01Z) - Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文 参考訳（メタデータ） (2021-09-14T15:27:38Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳（メタデータ） (2021-04-17T08:22:04Z) - Inapproximability of Minimizing a Pair of DNFs or Binary Decision Trees
Defining a Partial Boolean Function [13.713089043895959]
一対のブール関数 $f, g colon 0,1J to 0,1$ で定義される部分ブール関数を考えると、$f cdot g = 0$ であり、$f$ と $g$ は可分正規形式または二分決定木で定義される。
論文 参考訳（メタデータ） (2021-02-09T08:46:50Z) - 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) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。