論文の概要: A Matrix Product State Representation of Boolean Functions

• arxiv url: http://arxiv.org/abs/2505.01930v2
• Date: Sun, 11 May 2025 15:03:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-13 12:10:05.914341
• Title: A Matrix Product State Representation of Boolean Functions
• Title（参考訳）: ブール関数の行列積状態表現
• Authors: Umut Eren Usturali, Claudio Chamon, Andrei E. Ruckenstein, Eduardo R. Mucciolo,
• Abstract要約: 本稿では、二項行列の積の観点でブール関数の新たな正規形式表現を導入し、以下、二項行列積(BMP)表現と呼ぶ。 BMPは、それぞれ応用数学や量子多体物理学で使用される発明されたTrains(TT)とMatrix Product States(MPS)に類似している。 本稿では,BMPをBDD(Bibinary Decision Diagram)へ直接的かつ自然な翻訳を行い,BMPを操作・結合するための基本的な操作セットを導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel normal form representation of Boolean functions in terms of products of binary matrices, hereafter referred to as the Binary Matrix Product (BMP) representation. BMPs are analogous to the Tensor-Trains (TT) and Matrix Product States (MPS) used, respectively, in applied mathematics and in quantum many-body physics to accelerate computations that are usually inaccessible by more traditional approaches. BMPs turn out to be closely related to Binary Decision Diagrams (BDDs), a powerful compressed representation of Boolean functions invented in the late 80s by Bryant that has found a broad range of applications in many areas of computer science and engineering. We present a direct and natural translation of BMPs into Binary Decision Diagrams (BDDs), and derive an elementary set of operations used to manipulate and combine BMPs that are analogous to those introduced by Bryant for BDDs. Both BDDs and BMPs are practical tools when the complexity of these representations, as measured by the maximum bond dimension of a BMP (or the accumulated bond dimension across the BMP matrix train) and the number of nodes of a BDD, remains polynomial in the number of bits, $n$. In both cases, controlling the complexity hinges on optimizing the order of the Boolean variables. BMPs offer the advantage that their construction and manipulation rely on simple linear algebra -- a compelling feature that can facilitate the development of open-source libraries that are both more flexible and easier to use than those currently available for BDDs. An initial implementation of a BMP library is available on GitHub, with the expectation that the close conceptual connection to TT and MPS techniques will motivate further development of BMP methods by researchers in these fields, potentially enabling novel applications to classical and quantum computing.
• Abstract（参考訳）: 本稿では、二項行列の積の観点でブール関数の新たな正規形式表現を導入し、以下、二項行列積(BMP)表現と呼ぶ。 BMPは、それぞれ応用数学や量子多体物理学で使われるTensor-Trains (TT) とMatrix Product States (MPS) に類似しており、より伝統的なアプローチではアクセスできない計算を加速する。 BMPは、Bryantによって80年代後半に発明されたブール関数の強力な圧縮表現であるBinary Decision Diagrams (BDDs)と密接に関連していることが判明した。 本稿では,BMPを2値決定図(BDD)へ直接的かつ自然な変換し,BryantがBDDに導入したものと類似したBMPを操作・結合するための基本的な操作セットを導出する。 BDD と BMP はどちらも、BMP の最大結合次元(または BMP 行列列全体の累積結合次元)と BDD のノード数によって測定されたこれらの表現の複雑さが、ビット数の多項式である$n$ であるときの実用的なツールである。 どちらの場合も、複雑性を制御することはブール変数の順序を最適化することに集中する。 BMPは、その構成と操作が単純な線形代数に依存しているという利点を提供する。これは、BDDで現在利用できるものよりも柔軟で使いやすく、オープンソースのライブラリの開発を容易にする魅力的な機能である。 BMPライブラリの初期実装はGitHubで利用可能であり、TTとMPS技術との密接な概念的つながりは、これらの分野の研究者によるBMPメソッドのさらなる開発を動機付け、古典的および量子コンピューティングへの新しい応用を可能にする可能性があると期待されている。

関連論文リスト

• Fast Homomorphic Linear Algebra with BLAS [11.269481520748839]
  ホモモルフィック暗号化は、プライバシ保護データ操作、特にAIに幅広いアプリケーションを開く。 これらの応用の多くは、重要な線型代数計算(行列 x ベクトル積、行列 x 行列積)を必要とする。 線型代数計算のこの中心的な役割は、準同型代数をはるかに超え、科学計算のほとんどの分野に適用できる。 CKKSをベースとした暗号化正方行列乗算と倍精度浮動小数点行列乗算との効率損失は、正確な状況に応じて4-12因子であることを示す。
  論文  参考訳（メタデータ） (2025-03-20T12:19:47Z)
• BiMaCoSR: Binary One-Step Diffusion Model Leveraging Flexible Matrix Compression for Real Super-Resolution [63.777210548110425]
  本稿では,バイナライゼーションと1段階蒸留を組み合わせたBiMaCoSRを提案する。 BiMaCoSRはFPに比べて23.8倍圧縮率と27.4倍スピードアップ比を達成した。
  論文  参考訳（メタデータ） (2025-02-01T06:34:55Z)
• Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices [88.33936714942996]
  アインシュタイン和を通じて表現可能なすべての線形作用素の探索を可能にする統一フレームワークを提案する。 計算-最適スケーリング法則の違いは主に少数の変数によって支配されていることを示す。 そこで,Mixture-of-Experts (MoE) は,注目ブロックの投影を含む,モデルのすべての線形層におけるMoEを学習する。
  論文  参考訳（メタデータ） (2024-10-03T00:44:50Z)
• OMPar: Automatic Parallelization with AI-Driven Source-to-Source Compilation [4.266086505323998]
  本稿では,OpenMP pragmasを用いたC/C++コードの並列化を自動化するAI駆動型ツールであるOMParを紹介する。 OMParは、ループ並列化ポテンシャルを評価するOMPifyと、正確なOpenMPパグマを生成する新しい微調整モデルであるMonoCoder-OMPの2つの主要なコンポーネントを通じて、LLM(Large Language Models)を統合している。
  論文  参考訳（メタデータ） (2024-09-23T07:39:01Z)
• DB-LLM: Accurate Dual-Binarization for Efficient LLMs [83.70686728471547]
  大規模言語モデル(LLM)は自然言語処理の分野を著しく進歩させてきた。 既存の超低ビット量子化は、常に深刻な精度低下を引き起こす。 本稿では,LLM,すなわちDB-LLMのための新しいデュアルバイナライズ手法を提案する。
  論文  参考訳（メタデータ） (2024-02-19T09:04:30Z)
• Extreme Compression of Large Language Models via Additive Quantization [59.3122859349777]
  我々のアルゴリズムは、AQLMと呼ばれ、情報検索のための古典的な加算量子化(AQ)アプローチを一般化する。 トークン生成のためのAQLMの高速GPUおよびCPU実装を提供しており、最適化されたFP16実装を高速にマッチングまたは性能良くすることができる。
  論文  参考訳（メタデータ） (2024-01-11T18:54:44Z)
• Advising OpenMP Parallelization via a Graph-Based Approach with Transformers [2.393682571484038]
  我々は,OpenMPのプラグマと共有メモリ属性を並列コードで検出し,予測する,OMPifyと呼ばれる新しい手法を提案する。 OMPifyは、ソースコードのグラフベースの表現を利用するTransformerベースのモデルに基づいている。 以上の結果から,OMPifyは汎用および人気の高いChatGPTやPragFormerモデルなど,既存のアプローチよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-05-16T16:56:10Z)
• Compacting Binary Neural Networks by Sparse Kernel Selection [58.84313343190488]
  本稿は,BNNにおけるバイナリカーネルの分散化がほぼ不可能であることを示すものである。 我々は、選択過程をエンドツーエンドに最適化するだけでなく、選択したコードワードの非反復的占有を維持できる置換ストレートスルー推定器(PSTE)を開発した。 実験により,提案手法はモデルサイズとビット幅の計算コストの両方を削減し,同等の予算下での最先端のBNNと比較して精度の向上を実現する。
  論文  参考訳（メタデータ） (2023-03-25T13:53:02Z)
• Towards Accurate Binary Neural Networks via Modeling Contextual Dependencies [52.691032025163175]
  既存のバイナリニューラルネットワーク(BNN)は主にバイナライズ機能を備えた局所畳み込みで動作する。 本稿では,二元系ニューラルモジュールの設計を新たに提案し,二元系ニューラルモジュールを大きなマージンで導く。
  論文  参考訳（メタデータ） (2022-09-03T11:51:04Z)
• Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice [3.658952625899939]
  我々は$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発した。 EPTAS for BMFは純粋に理論上の進歩である。 また、この戦略を用いて、関連する$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-07-25T06:05:12Z)
• Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
  ランク-k二元行列分解問題(k-BMF)に対するコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案する。 コンパクトIPはLP緩和が弱いのに対し,指数サイズのLPはLP緩和が強いことを示す。
  論文  参考訳（メタデータ） (2021-06-25T05:17:51Z)

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

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