論文の概要: Optimal Locality and Parameter Tradeoffs for Subsystem Codes

• arxiv url: http://arxiv.org/abs/2503.22651v1
• Date: Fri, 28 Mar 2025 17:38:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-31 15:30:52.714749
• Title: Optimal Locality and Parameter Tradeoffs for Subsystem Codes
• Title（参考訳）: サブシステム符号の最適局所性とパラメータトレードオフ
• Authors: Samuel Dai, Ray Li, Eugene Tang,
• Abstract要約: サブシステムコードの$D$次元埋め込みにおいて、相互作用の数と長さの両方の低い境界を証明します。 具体的には、パラメータ $[n,k,d] のサブシステムコードの $[n,k,d] を $mathbbRD$ に埋め込むには、少なくとも$M*$ の長さの相互作用が少なくとも$ell*$ でなければならないことを示す。
• 参考スコア（独自算出の注目度）: 7.783262415147655
• License:
• Abstract: We study the tradeoffs between the locality and parameters of subsystem codes. We prove lower bounds on both the number and lengths of interactions in any $D$-dimensional embedding of a subsystem code. Specifically, we show that any embedding of a subsystem code with parameters $[[n,k,d]]$ into $\mathbb{R}^D$ must have at least $M^*$ interactions of length at least $\ell^*$, where \[ M^* = \Omega(\max(k,d)), \quad\text{and}\quad \ell^* = \Omega\bigg(\max\bigg(\frac{d}{n^\frac{D-1}{D}}, \bigg(\frac{kd^\frac{1}{D-1}}{n}\bigg)^\frac{D-1}{D}\bigg)\bigg). \] We also give tradeoffs between the locality and parameters of commuting projector codes in $D$-dimensions, generalizing a result of Dai and Li. We provide explicit constructions of embedded codes that show our bounds are optimal in both the interaction count and interaction length.
• Abstract（参考訳）: サブシステムコードの局所性とパラメータ間のトレードオフについて検討する。 サブシステムコードの$D$次元埋め込みにおいて、相互作用の数と長さの両方の低い境界を証明します。 具体的には、パラメータ $[[n,k,d]]$ から $\mathbb{R}^D$ へのサブシステムコードの埋め込みは、少なくとも$M^*$ の長さの相互作用が少なくとも$\ell^*$ であることを示し、そこで \[M^* = \Omega(\max(k,d)), \quad\text{and}\quad \ell^* = \Omega\bigg(\max\bigg(\frac{d}{n^\frac{D-1}{D}}), \bigg(\frac{kd^\frac{1}{D-1}}{n}\bigg)^\frac{D-1}{D}\bigg)\bigg である。 また、通勤プロジェクタ符号の局所性とパラメータのトレードオフを$D$-dimensionsで示し、DaiとLiの結果を一般化する。 我々は、相互作用数と相互作用長の両方において、境界が最適であることを示す埋め込み符号の明示的な構成を提供する。

関連論文リスト

• A Variant of the Bravyi-Terhal Bound for Arbitrary Boundary Conditions [10.560637835517094]
  商 $mathbbZD/Lambda$ of $mathbbZD$ of cardinality $n$ on a $D$-dimensional lattice quotient を考える。 すべての安定化器ジェネレータが半径$rho$の範囲内にある量子ビットに作用すると、コードの最小距離$d$は$d leq msqrtgamma_D(sqrtD + 4rho)nfracD-1D$である。
  論文  参考訳（メタデータ） (2025-02-07T15:18:40Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk [12.842909157175582]
  我々は、$d$-dimensional log-concave distribution $pi(theta) propto exp(-f(theta))$ for $L$-Lipschitz $f$を考える。 本稿では,各繰り返しにおける障壁関数のヘシアンに対するスペクトル近似を計算するインプロバストサンプリングフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-08T05:32:51Z)
• Locality vs Quantum Codes [8.747606955991708]
  量子符号は量子フォールトトレランスへの有望な道を提供するが、局所性の実践的な制約はそれらの品質を制限している。 本稿では,量子誤り訂正符号の局所性とパラメータ間の最適トレードオフを証明した。
  論文  参考訳（メタデータ） (2024-09-23T16:50:21Z)
• Block Circulant Codes with Application to Decentralized Systems [12.014314088945968]
  我々は,分散消去復号化をサポートするブロック循環符号のファミリ[n,k,d]を開発する。 このコードは、ブロックチェーンネットワークのデータ可用性問題に対処するプロトコルで使用するのに理想的だ。
  論文  参考訳（メタデータ） (2024-06-18T00:22:20Z)
• Area law for the maximally mixed ground state in degenerate 1D gapped systems [5.088702935364181]
  我々は、最大混合状態$Omega$に対する対数補正を伴う領域法則を、1Dギャップ化された局所ハミルトニアン$H$の(縮退した)基底空間で示す。 また、$mathrmI(L:R)_Omega leq O(log |L|)$という形の相互情報に対して面積法則を得る。
  論文  参考訳（メタデータ） (2023-10-29T14:36:30Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。