論文の概要: Weighted Context-Free-Language Ordered Binary Decision Diagrams
- arxiv url: http://arxiv.org/abs/2305.13610v2
- Date: Wed, 28 Aug 2024 19:06:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 19:48:14.670416
- Title: Weighted Context-Free-Language Ordered Binary Decision Diagrams
- Title(参考訳): 重み付き文脈自由言語順序付き二項決定図
- Authors: Meghana Sistla, Swarat Chaudhuri, Thomas Reps,
- Abstract要約: 本稿では,emphWeighted Context-Free-Language Ordered BDDs(WCFLOBDDs)と呼ばれる新しいデータ構造を提案する。
一部の関数では、WCFLOBDDはWBDDよりも指数関数的に簡潔である。
我々は、量子回路シミュレーションにWCFLOBDDを適用し、特定のベンチマークでWBDDよりも優れた性能を発揮することを発見した。
- 参考スコア(独自算出の注目度): 9.483290784772011
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a new data structure, called \emph{Weighted Context-Free-Language Ordered BDDs} (WCFLOBDDs), which are a hierarchically structured decision diagram, akin to Weighted BDDs (WBDDs) enhanced with a procedure-call mechanism. For some functions, WCFLOBDDs are exponentially more succinct than WBDDs. They are potentially beneficial for representing functions of type $\mathbb{B}^n \rightarrow D$, when a function's image $V \subseteq D$ has many different values. We apply WCFLOBDDs in quantum-circuit simulation, and find that they perform better than WBDDs on certain benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is 1-64$\times$ that of WBDDs (and 1-128$\times$ that of CFLOBDDs, which are an unweighted version of WCFLOBDDs). These results support the conclusion that for this application -- from the standpoint of problem size, measured as the number of qubits -- WCFLOBDDs provide the best of both worlds: performance roughly matches whichever of WBDDs and CFLOBDDs is better. (From the standpoint of running time, the results are more nuanced.)
- Abstract(参考訳): 本稿では,階層的に構造化された決定図である 'emph{Weighted Context-Free-Language Ordered BDDs} (WCFLOBDDs) と呼ばれる新しいデータ構造について述べる。
一部の関数では、WCFLOBDDはWBDDよりも指数関数的に簡潔である。
関数のイメージ $V \subseteq D$ が多くの異なる値を持つとき、型 $\mathbb{B}^n \rightarrow D$ の関数を表現することは潜在的に有益である。
我々は、量子回路シミュレーションにWCFLOBDDを適用し、特定のベンチマークでWBDDよりも優れた性能を発揮することを発見した。
15分間のタイムアウトで、WCFLOBDDsで処理できるキュービットの数は、WBDDsの1-64$\times$(1-128$\times$CFLOBDDsの1-28$\times$)となる。
これらの結果は、このアプリケーション -- キュービットの数として測定される問題のサイズの観点から言えば -- に対して、WCFLOBDDは両方の世界のベストを提供する、という結論を支持します。
(実行時の立場からすると、結果はより微妙である。)
関連論文リスト
- WDD: Weighted Delta Debugging [6.393194328016689]
Delta Weighted Delta (WDD)は、デルタデバッグアルゴリズムが制限を克服するのに役立つ新しいコンセプトである。
WDDはリスト内の各要素をそのサイズに応じて重み付けし、分割中の重みに基づいて異なる要素を区別する。
我々は2つの言語にわたる62のベンチマークで、WDDを2つの代表的アプリケーション(HDDとPerses)で広範囲に評価した。
論文 参考訳(メタデータ) (2024-11-28T23:31:33Z) - Exploiting Pre-trained Models for Drug Target Affinity Prediction with Nearest Neighbors [58.661454334877256]
薬物-標的結合親和性(DTA)予測は、薬物発見に不可欠である。
DTA予測へのディープラーニング手法の適用にもかかわらず、達成された精度は依然として準最適である。
事前学習したDTA予測モデルに適用した非表現埋め込みに基づく検索手法である$k$NN-DTAを提案する。
論文 参考訳(メタデータ) (2024-07-21T15:49:05Z) - Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models [65.48185395952788]
Buffer of Thoughts (BoT) は、斬新で多目的な思考補足的推論手法である。
そこで我々はメタバッファーを提案し,一連の情報的高レベルの思考を記憶する。
各問題に対して、関連する思考タイミングを検索し、特定の推論構造で適応的にインスタンス化する。
論文 参考訳(メタデータ) (2024-06-06T17:22:08Z) - Variants of Tagged Sentential Decision Diagrams [6.891570850234007]
最近提案されたブール関数の標準形式、すなわちタグ付き逐次決定図(TSDD)は、標準およびゼロ抑圧トリミングルールの両方を利用する。
本稿では,トリミング規則の順序を逆転することで,標準TSDD(STSDD)と呼ぶTSDDの変種について述べる。
次に、STSDDの正準性を証明し、TSDD上でのバイナリ演算のアルゴリズムを示す。
論文 参考訳(メタデータ) (2023-11-16T12:29:25Z) - Exploiting Asymmetry in Logic Puzzles: Using ZDDs for Symbolic Model
Checking Dynamic Epistemic Logic [0.0]
我々は、動的疫学論理で使用されるクリプキモデルを象徴的に符号化するためにZDDを使用する。
BDDを適切なZDDに置き換えることで、メモリ使用量を大幅に削減できることを示す。
これはZDDがマルチエージェントシステムのモデル検査に有用なツールであることを示唆している。
論文 参考訳(メタデータ) (2023-07-11T07:13:09Z) - Direct Diffusion Bridge using Data Consistency for Inverse Problems [65.04689839117692]
拡散モデルに基づく逆問題解法は優れた性能を示したが、速度は制限されている。
いくつかの最近の研究は、拡散プロセスを構築し、クリーンで破損したものを直接ブリッジすることでこの問題を緩和しようと試みている。
微調整を必要とせずにデータの一貫性を強制する改良された推論手順を提案する。
論文 参考訳(メタデータ) (2023-05-31T12:51:10Z) - Belief Revision in Sentential Decision Diagrams [126.94029917018733]
本研究では,Dalリビジョンの構文的特徴化に基づくSDDの一般的なリビジョンアルゴリズムを開発する。
ランダムに生成した知識ベースを用いた予備実験は、SDDフォーマリズム内で直接リビジョンを行う利点を示している。
論文 参考訳(メタデータ) (2022-01-20T11:01:41Z) - ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical
Decoupling [3.2505361717998227]
キュービットはアイドル状態にあり、アクティブな操作を行わないときに発生するアイドルエラーの影響を受けやすい。
既存の動的デカップリングプロトコルは主に個々の量子ビットに対して研究されている。
本稿では,各キュービットの組み合わせに対するDDの有効性を推定するソフトウェアフレームワークであるAdaptive Dynamical Decoupling (ADAPT)を提案する。
論文 参考訳(メタデータ) (2021-09-11T16:15:24Z) - Double Forward Propagation for Memorized Batch Normalization [68.34268180871416]
バッチ正規化(BN)は、ディープニューラルネットワーク(DNN)の設計における標準コンポーネントである。
より正確でロバストな統計値を得るために,複数の最近のバッチを考慮に入れた記憶型バッチ正規化(MBN)を提案する。
関連する手法と比較して、提案したMBNはトレーニングと推論の両方において一貫した振る舞いを示す。
論文 参考訳(メタデータ) (2020-10-10T08:48:41Z) - DynaBERT: Dynamic BERT with Adaptive Width and Depth [55.18269622415814]
我々は新しい動的BERTモデル(DynaBERTと略される)を提案する。
適応的な幅と深さを選択することで、サイズとレイテンシを柔軟に調整できる。
既存のBERT圧縮手法よりずっと優れています。
論文 参考訳(メタデータ) (2020-04-08T15:06:28Z) - Variable Shift SDD: A More Succinct Sentential Decision Diagram [10.91026094237478]
Sentential Decision Diagram (SDD) はブール関数の抽出可能な表現である。
可変シフトSDD(VS-SDD)という,より簡潔なSDD変種を提案する。
我々は,VS-SDDがSDDよりも大きくなることはなく,VS-SDDのサイズがSDDよりも指数関数的に小さいケースがあることを示した。
論文 参考訳(メタデータ) (2020-04-06T09:18:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。