Fugu-MT 論文翻訳(概要): More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

論文の概要: More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

arxiv url: http://arxiv.org/abs/2406.08499v1
Date: Wed, 8 May 2024 22:38:35 GMT
ステータス: 処理完了
システム内更新日: 2024-07-01 07:50:27.612285
Title: More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Title（参考訳）: 対数ソボレフ不等式によるランダム可逆回路からのより効率的な$k$-wise独立置換
Authors: Lucas Gretta, William He, Angelos Pelecanos,
Abstract要約: 我々は、$tildeO(nkcdot log (1/varepsilon))$ random $3$-bit gates is $varepsilon$-aqua $k$-wise independentという可逆回路によって計算された置換が証明される。私たちのバウンダリは、近似エラー$varepsilon$が小さすぎる場合に、政権内の現在知られているバウンダリを改善します。
参考スコア（独自算出の注目度）: 0.10241134756773229
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove that the permutation computed by a reversible circuit with $\tilde{O}(nk\cdot \log(1/\varepsilon))$ random $3$-bit gates is $\varepsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $\varepsilon$ is not too small. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.
Abstract（参考訳）: 我々は、$\tilde{O}(nk\cdot \log(1/\varepsilon))$ランダムな$3$-bitゲートが$\varepsilon$-aqua $k$-wise独立な可逆回路によって計算された置換が証明される。私たちの境界は、近似誤差が$\varepsilon$が小さすぎる場合に、政権で現在知られている境界を改善します。スペクトルギャップではなく,適切なマルコフ鎖の対数ソボレフ定数を解析して得られた。

関連論文リスト

Quantum state preparation with optimal T-count [2.1386090295255333]
任意の$n$-qubit量子状態を誤差$varepsilon$に近似するために、Tゲートがいくつ必要かを示す。また、これは任意の対角線$n$-qubitユニタリをエラー$varepsilon$に実装するための最適なTカウントであることを示す。
論文参考訳（メタデータ） (2024-11-07T15:29:33Z)
Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。 2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文参考訳（メタデータ） (2024-10-31T13:51:59Z)
Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
論文参考訳（メタデータ） (2024-10-30T10:09:05Z)
Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。誤差$varepsilon$を全変動距離で学習できることが示される。また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
論文参考訳（メタデータ） (2024-10-21T09:39:20Z)
Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文参考訳（メタデータ） (2024-10-10T06:15:42Z)
A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文参考訳（メタデータ） (2024-06-17T20:54:11Z)
Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文参考訳（メタデータ） (2024-06-11T17:23:16Z)
A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文参考訳（メタデータ） (2022-02-23T16:10:23Z)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文参考訳（メタデータ） (2021-11-29T19:26:28Z)
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)

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