Fugu-MT 論文翻訳(概要): Uniformity testing when you have the source code

論文の概要: Uniformity testing when you have the source code

arxiv url: http://arxiv.org/abs/2411.04972v1
Date: Thu, 07 Nov 2024 18:48:29 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-08 19:35:34.570904
Title: Uniformity testing when you have the source code
Title（参考訳）: ソースコードがあるときの一様テスト
Authors: Clément L. Canonne, Robin Kothari, Ryan O'Donnell,
Abstract要約: 古典回路や量子回路の出力確率分布の特性を検証するための量子アルゴリズムについて検討する。出力分布が全変動距離から$[d]$または$epsilon$-farで均一であるかどうかを決定する。
参考スコア（独自算出の注目度）: 16.232881331802687
License:
Abstract: We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $\epsilon$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $\epsilon$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/\epsilon^{2},d^{1/2}/\epsilon\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/\epsilon^{4/3}, d^{1/2}/\epsilon\})$, which we conjecture is optimal.
Abstract（参考訳）: 本稿では,古典回路や量子回路の出力確率分布の特性を検証するための量子アルゴリズムについて検討する。出力分布が$[d]$または$\epsilon$-farで均一であるかどうかを全変動距離で決定する。より一般的には、出力分布が既知の仮説分布と等しいか、あるいはそれから$\epsilon$-farであるかどうかを決定するタスクであるアイデンティティテストを考える。どちらの問題に対しても、以前の最もよく知られた上限は$O(\min\{d^{1/3}/\epsilon^{2},d^{1/2}/\epsilon\})$である。ここでは、上限を$O(\min\{d^{1/3}/\epsilon^{4/3}, d^{1/2}/\epsilon\})$に改善する。

関連論文リスト

Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文参考訳（メタデータ） (2024-10-21T19:37:35Z)
Replicable Uniformity Testing [1.5883812630616523]
この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
論文参考訳（メタデータ） (2024-10-12T02:55:17Z)
Out-of-Distribution Detection using Maximum Entropy Coding [4.7768369720936255]
離散分布について、決定的な答えは原理的にはランダムネスのコルモゴロフ=マルティン=Lによって与えられる。我々は、双方向生成ネットワークを用いて、データを潜在空間の標準分布に変換し、そこで最大エントロピー符号化を使用する。
論文参考訳（メタデータ） (2024-04-25T20:28:43Z)
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)
Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文参考訳（メタデータ） (2023-02-21T17:52:23Z)
Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。 1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文参考訳（メタデータ） (2022-06-21T20:43:53Z)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文参考訳（メタデータ） (2021-11-29T19:26:28Z)
The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文参考訳（メタデータ） (2020-12-31T18:24:41Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文参考訳（メタデータ） (2020-02-21T18:30:48Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。