論文の概要: Graphical and algebraic methods for Boolean factoring
- arxiv url: http://arxiv.org/abs/2606.04038v1
- Date: Tue, 02 Jun 2026 02:57:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-04 20:44:18.258741
- Title: Graphical and algebraic methods for Boolean factoring
- Title（参考訳）: ブール分解のグラフ的および代数的方法
- Abstract要約: 我々はESOPとSOPの両表現を分解する新しいアルゴリズムを開発した。
ANDカウントは古典回路や量子回路で可逆関数を実装するのに必要な AND と Toffoli の数を決定する上で重要な役割を果たしている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The problem of factoring Boolean polynomials has significant applications in both classical and quantum computing technology. In this paper we have developed novel algorithms for factoring both ESOP and SOP expressions. Our aim is to optimize the AND-count. The AND-count plays a key role in determining the number of AND and Toffoli gates required to implement a reversible function with classical and quantum circuits, respectively. The first type of algorithms that we develop, are graphical. We reduce the problem of Boolean factoring to covering a bipartite graph with bicliques, and so optimizing the number of bicliques required to cover the bipartite graph, leads to reduced number of factors, and hence AND-count. The second type of algorithm is algebraic, and is derived from multivariate Horner method. We have compared the performances of our algorithms with existing popular methods like EXORCISM-4 and EPOEM2, on random functions of up to 12 variables. We have observed that our multivariate Horner method is substantially faster, while our biclique-based method achieves the maximum AND-count reduction. In fact, compared to EXORCISM-4 our biclique based method achieves up to 5 times reduction in AND-count.
- Abstract（参考訳）: ブール多項式を分解する問題は、古典的および量子コンピューティング技術の両方に重要な応用をもたらす。
本稿では,ESOP表現とSOP表現の両方を分解する新しいアルゴリズムを開発した。
我々の目標は、and-countを最適化することです。
ANDカウントは古典回路と量子回路でそれぞれ可逆関数を実装するのに必要な AND ゲート数と Toffoli ゲート数を決定する上で重要な役割を果たしている。
最初に開発したアルゴリズムはグラフィカルです。
ブール分解の問題を二進グラフを二進グラフで覆うように減らし、二進グラフを被覆するのに要する双進グラフの数を最適化し、因子数を減らし、従ってANDカウントする。
第2のアルゴリズムは代数的であり、多変量ホーナー法から導かれる。
最大12変数のランダム関数に対して,EXORCISM-4 や EPOEM2 などの既存手法と比較した。
我々は,多変量ホーナー法が著しく高速であるのに対して,バイクリッド法は最大値と最大値の削減を実現することを観察した。
実際、EXORCISM-4と比較して、我々の斜め法は最大で5倍のアンドカウントを減少させる。
関連論文リスト
- Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
フェデレーション行列の2レベル最適化は、機械学習に広く応用されているため、近年積極的に研究されている。
既存のフェデレートされた双レベル最適化アルゴリズムは、二階ヘッセン行列とヤコビ行列の計算を必要とする。
本稿では,一階オーラクルのみに依存する新しいフェデレーション収束分散誘導二段降下アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-14T21:12:59Z) - Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics [11.53912933736867]
BMFは与えられたバイナリ入力行列を2つのより小さなバイナリ要素の積として近似する。
標準的な算術に基づく二項行列分解とは異なり、BMFはブールORと行列積の演算を用いる。
役割マイニングやコンピュータビジョンにも用いられている。
論文 参考訳（メタデータ） (2025-12-03T13:55:54Z) - Qubit-count optimization using ZX-calculus [3.129187821625805]
非クリフォードゲート数を保存しながら量子回路内の量子ビット数を最適化する方法を示す。
我々のアプローチの1つは、いくつかの$T$-countsで使用される手続きである、アダマール門のガジェット化を反転させることである。
また、この手法を用いて、量子回路における量子ビットの数をZX計算を中間表現として効率的に最適化する方法について述べる。
論文 参考訳（メタデータ） (2024-07-14T11:58:53Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
BMFの1因子行列におけるサブプロブレムを解くための交互最適化(AO)戦略を提案する。
BMFの複数の解が、他のIPを用いて最適に組み合わせられるかを示す。
実験の結果,我々のアルゴリズムは中規模問題における技術状況よりも優れていた。
論文 参考訳（メタデータ） (2023-05-17T13:09:23Z) - An Application of a Multivariate Estimation of Distribution Algorithm to
Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。
より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。
我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文 参考訳（メタデータ） (2022-05-17T15:28:46Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Mean Field Approximation for solving QUBO problems [0.0]
平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。
提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
論文 参考訳（メタデータ） (2021-06-06T20:35:28Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。