論文の概要: Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group

• arxiv url: http://arxiv.org/abs/2609.35271v1
• Date: Mon, 28 Sep 2026 14:27:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-02 06:59:37.743548
• Title: Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group
• Title（参考訳）: 一般化LIMDD:決定ダイアグラムの付加性と正準性
• Abstract要約: 函数 $0,1ntomathbbC$ と $G$ に対して、パウリ群は局所可逆写像決定図形である。 函数 $0,1ntomathbbC$ と $G$ に対して、パウリ群は局所可逆写像決定図形である。
• 参考スコア（独自算出の注目度）: 5.302303646066551
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A reduced ordered decision diagram is the minimal automaton of a function on words of fixed length: its nodes are the residuals, and reduction is the Myhill--Nerode quotient. We study what happens when that quotient is coarsened by a group. Fix a group $G$ acting on residuals, merge two nodes when their residuals lie in one $G$-orbit, and record the group element on the edge. For functions $\{0,1\}^n\to\mathbb{C}$ and $G$ the Pauli group this is the Local Invertible Map Decision Diagram. We take $G$ from the two-parameter family generated by $C^{\leq k}R_q$, the phase rotation of order $q$ with up to $k$ control qubits, with and without the bit flip $X$. We show that this gives exponential succinctness improvements compared to Pauli-LIMDD, and we determine the succinctness order of the family completely. The separating objects are hypergraph states, which can always be efficiently represented by some member of the family. We settle the tractability of five queries and eight transformations, which is invariant across the family, and shows the same behavior as Pauli-LIMDD. We give a five-rule reduction system whose normal forms are unique for every member of the family, and we show that this canonical form is computable in polynomial time in the size of the LIMDD. We show that, when coarsening beyond the (anti-)diagonal groups, the calculation of a minimal sized normal form turns out to be non-local and it might to rebuild the whole diagram.
• Abstract（参考訳）: 縮小順序決定図は固定長の単語上の関数の最小オートマトンであり、そのノードは残基であり、還元はミヒル-ネローデ商である。 我々は、その商がグループによって粗められたときに何が起こるかを研究する。 残基に作用する群$G$を固定し、残基が1つの$G$-orbitにあるときに2つのノードをマージし、グループ要素をエッジに記録する。 函数 ${0,1\}^n\to\mathbb{C}$ と $G$ に対して、パウリ群は局所可逆写像決定図形である。 我々は、$C^{\leq k}R_q$で生成される2パラメータファミリーから$G$を取る。 パウリ-LIMDDと比較して指数的簡潔さが向上することを示し、家族の簡潔さの順序を完全に決定する。 分離されたオブジェクトはハイパーグラフ状態であり、常に家族のメンバーによって効率的に表現される。 5つのクエリと8つの変換のトラクタビリティは、家族間で不変であり、Pauli-LIMDDと同じ振る舞いを示す。 LIMDD の大きさの多項式時間で計算可能であることを示すため,家族全員に正規形が一意な5ルール還元システムを提案する。 反対角群を超えて粗くすると、最小サイズの正規形式の計算は非局所であることが判明し、図形全体を再構築する可能性があることを示す。

関連論文リスト

• Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization [2.1248439796866228]
  正規化実現は行確率遷移行列と終端効果を用いて宣言された根語応答を再現する。 独立局所現実化、独立クエリ効果を持つ静的共有キャリア、時系列共有現実化の3つの実化複雑性を比較した。 明示的に列挙された有理メニューでは、正確な共有実現性は$existsmathbbR$-completeであり、逆多項式とゼロ欠陥を区別する約束問題は$mathsfPromiseNP$-completeである。
  論文  参考訳（メタデータ） (2026-09-17T05:01:32Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• A Gap Between Decision Trees and Neural Networks [2.4140387101794283]
  ここでは、解釈可能性の概念として用いられる決定境界の幾何学的単純さが、浅いニューラルネットワークによる軸整列決定木の正確な近似と矛盾する場合について検討する。 分類するために、有限$mathrmRmathrmTV$で滑らかな障壁スコア$S_A$を構築し、その固定しきい値$=1$がボックスを正確に回復する。 長方形の合成結合の実験は、結果として生じる精度-複雑さのトレードオフを示している。
  論文  参考訳（メタデータ） (2026-01-07T13:40:30Z)
• A General Framework for Robust G-Invariance in G-Equivariant Networks [5.227502964814928]
  群同変畳み込みニューラルネットワーク(G$-CNN)におけるロバストなグループ不変性を実現するための一般的な方法を提案する。 三重相関の完全性は、強い強靭性を持つ$G$-TC層を与える。 この手法の利点を可換群と非可換群の両方に示す。
  論文  参考訳（メタデータ） (2023-10-28T02:27:34Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)

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

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