論文の概要: Quantum Sabotage Complexity
- arxiv url: http://arxiv.org/abs/2408.12595v1
- Date: Thu, 22 Aug 2024 17:57:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-23 12:52:30.677628
- Title: Quantum Sabotage Complexity
- Title（参考訳）: 量子サボタージュ複雑性
- Authors: Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro,
- Abstract要約: ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
- 参考スコア（独自算出の注目度）: 0.7812210699650152
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a Boolean function $f:\{0,1\}^n\to\{0,1\}$, the goal in the usual query model is to compute $f$ on an unknown input $x \in \{0,1\}^n$ while minimizing the number of queries to $x$. One can also consider a "distinguishing" problem denoted by $f_{\mathsf{sab}}$: given an input $x \in f^{-1}(0)$ and an input $y \in f^{-1}(1)$, either all differing locations are replaced by a $*$, or all differing locations are replaced by $\dagger$, and an algorithm's goal is to identify which of these is the case while minimizing the number of queries. Ben-David and Kothari [ToC'18] introduced the notion of randomized sabotage complexity of a Boolean function to be the zero-error randomized query complexity of $f_{\mathsf{sab}}$. A natural follow-up question is to understand $\mathsf{Q}(f_{\mathsf{sab}})$, the quantum query complexity of $f_{\mathsf{sab}}$. In this paper, we initiate a systematic study of this. The following are our main results: $\bullet\;\;$ If we have additional query access to $x$ and $y$, then $\mathsf{Q}(f_{\mathsf{sab}})=O(\min\{\mathsf{Q}(f),\sqrt{n}\})$. $\bullet\;\;$ If an algorithm is also required to output a differing index of a 0-input and a 1-input, then $\mathsf{Q}(f_{\mathsf{sab}})=O(\min\{\mathsf{Q}(f)^{1.5},\sqrt{n}\})$. $\bullet\;\;$ $\mathsf{Q}(f_{\mathsf{sab}}) = \Omega(\sqrt{\mathsf{fbs}(f)})$, where $\mathsf{fbs}(f)$ denotes the fractional block sensitivity of $f$. By known results, along with the results in the previous bullets, this implies that $\mathsf{Q}(f_{\mathsf{sab}})$ is polynomially related to $\mathsf{Q}(f)$. $\bullet\;\;$ The bound above is easily seen to be tight for standard functions such as And, Or, Majority and Parity. We show that when $f$ is the Indexing function, $\mathsf{Q}(f_{\mathsf{sab}})=\Theta(\mathsf{fbs}(f))$, ruling out the possibility that $\mathsf{Q}(f_{\mathsf{sab}})=\Theta(\sqrt{\mathsf{fbs}(f)})$ for all $f$.
- Abstract（参考訳）: Boolean 関数 $f:\{0,1\}^n\to\{0,1\}$ が与えられた場合、通常のクエリモデルのゴールは、未知の入力 $x \in \{0,1\}^n$ に対して$f$ を計算し、クエリの数を$x$ に最小化することである。
f_{\mathsf{sab}}$: 入力$x \in f^{-1}(0)$と入力$y \in f^{-1}(1)$が与えられた場合、すべての異なる場所が$*$に置き換えられるか、またはすべての異なる場所が$\dagger$に置き換えられるか、アルゴリズムの目標は、クエリの数を最小限にしながら、どれがどのケースであるかを特定することである。
Ben-David と Kothari [ToC'18] は、Boolean 関数のランダム化サボタージュ複雑性を $f_{\mathsf{sab}}$ のゼロエラーランダム化クエリ複雑性として導入した。
自然なフォローアップ質問は、$\mathsf{Q}(f_{\mathsf{sab}})$、$f_{\mathsf{sab}}$の量子クエリ複雑性を理解することである。
本稿では,これを体系的に研究する。
$\bullet\;\;$$$$x$と$y$に追加のクエリアクセスがあるなら、$\mathsf{Q}(f_{\mathsf{sab}})=O(\min\{\mathsf{Q}(f),\sqrt{n}\})$.sqrt{n}\})。
$\bullet\;\;$ アルゴリズムが 0-入力と 1-入力の異なる指数を出力する必要があるなら、$\mathsf{Q}(f_{\mathsf{sab}})=O(\min\{\mathsf{Q}(f)^{1.5},\sqrt{n}\})$ である。
$\bullet\;\;$ $\mathsf{Q}(f_{\mathsf{sab}}) = \Omega(\sqrt{\mathsf{fbs}(f)})$, $\mathsf{fbs}(f)$は$f$の分数ブロック感度を表す。
既知の結果から、以前の弾丸の結果とともに、$\mathsf{Q}(f_{\mathsf{sab}})$が$\mathsf{Q}(f)$と多項式的に関連していることを意味する。
$\bullet\;\;$ 上のバウンドは、And、Or、Majority、Parityといった標準関数に対してタイトである。
f$がインデックス関数であるとき、$\mathsf{Q}(f_{\mathsf{sab}})=\Theta(\mathsf{fbs}(f))$は、すべての$f$に対して$\mathsf{Q}(f_{\mathsf{sab}})=\Theta(\sqrt{\mathsf{fbs}(f)})$である可能性を除外する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する
私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。
我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
論文 参考訳（メタデータ） (2024-01-08T10:55:41Z) - Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。
我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
論文 参考訳（メタデータ） (2023-09-07T19:37:52Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - On relating one-way classical and quantum communication complexities [6.316693022958221]
通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。
量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
論文 参考訳（メタデータ） (2021-07-24T14:35:09Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - StoqMA meets distribution testing [0.0]
We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。
いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。
我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
論文 参考訳（メタデータ） (2020-11-11T12:30:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。