Fugu-MT 論文翻訳(概要): Determining the Multiplicative Complexity of Boolean Functions using SAT

論文の概要: Determining the Multiplicative Complexity of Boolean Functions using SAT

arxiv url: http://arxiv.org/abs/2005.01778v1
Date: Mon, 4 May 2020 18:29:48 GMT
ステータス: 処理完了
システム内更新日: 2023-05-21 05:04:54.304468
Title: Determining the Multiplicative Complexity of Boolean Functions using SAT
Title（参考訳）: SATを用いたブール関数の乗法複雑性の決定
Authors: Mathias Soeken
Abstract要約: ブール関数の乗法的複雑性を決定するための構築的SATアルゴリズムを提案する。提案アルゴリズムは,全5入力アフィン等価クラスの代表に対して最適XAGを求めることができる。
参考スコア（独自算出の注目度）: 1.4902915966744057
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present a constructive SAT-based algorithm to determine the multiplicative complexity of a Boolean function, i.e., the smallest number of AND gates in any logic network that consists of 2-input AND gates, 2-input XOR gates, and inverters. In order to speed-up solving time, we make use of several symmetry breaking constraints; these exploit properties of XAGs that may be useful beyond the proposed SAT-based algorithm. We further propose a heuristic post-optimization algorithm to reduce the number of XOR gates once the optimum number of AND gates has been obtained, which also makes use of SAT solvers. Our algorithm is capable to find all optimum XAGs for representatives of all 5-input affine-equivalent classes, and for a set of frequently occurring 6-input functions.
Abstract（参考訳）: 本稿では,論理ネットワークにおいて,論理関数の乗算複雑性,すなわち2入出力ゲート,2入出力XORゲート,インバータから構成される最小数のANDゲートを決定するための構築型SATアルゴリズムを提案する。解時間を高速化するために、我々はいくつかの対称性の破れ制約を利用し、これらのXAGの悪用特性は、提案したSATアルゴリズムを超えて有用である。さらに,最適なANDゲート数が得られると,XORゲート数が減少するヒューリスティックなポスト最適化アルゴリズムを提案し,SATソルバも活用する。本アルゴリズムは,5入力アフィン同値クラスと6入力関数を代表として,すべての最適xagを求めることができる。

関連論文リスト

Multi-qubit circuit synthesis and Hermitian lattices [0.0]
我々は,複数ビットのユニタリと等距離の正確な合成のための,新しい最適および合成アルゴリズムを提案する。最適なアルゴリズムは、グラフのための新しいデータ構造と新しい一貫した関数でインスタンス化されたA*探索である。
論文参考訳（メタデータ） (2024-05-29T17:27:50Z)
General Method for Solving Four Types of SAT Problems [12.28597116379225]
既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
論文参考訳（メタデータ） (2023-12-27T06:09:48Z)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
並列量子SATソルバは,線形時間 O(m) から定数時間 O(1) までの繰り返しの時間複雑性を,余分な絡み合った量子ビットを用いて低減する。我々は、我々のアプローチの正しさを証明し、シミュレーションでそれらを実証した。
論文参考訳（メタデータ） (2023-08-07T06:52:06Z)
Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds [0.2302001830524133]
固定されたマルチキュービットイジング型相互作用と単一キュービットXゲートは、グローバルZZゲートの合成に利用できる。このような時間最適な量子ゲートの合成はNPハードであることが示される。我々は任意の GZZ ゲートが n 個の量子ビットの時間 O(n) で実行可能であると推測する。
論文参考訳（メタデータ） (2023-07-20T18:00:05Z)
Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
論文参考訳（メタデータ） (2022-10-04T09:19:13Z)
Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文参考訳（メタデータ） (2022-03-11T17:19:26Z)
Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文参考訳（メタデータ） (2021-07-15T04:47:35Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
Introducing Structure to Expedite Quantum Search [0.0]
本稿では,非構造化探索問題を1つの有意な要素で解くための新しい量子アルゴリズムを提案する。我々のアルゴリズムは乗算定数までの基本ゲートの総数で最適である。本稿では,複数要素を持つ非構造化探索問題の解法に必要な基本ゲートの数をトータルに削減する方法を示す。
論文参考訳（メタデータ） (2020-06-10T13:29:47Z)

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