論文の概要: Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints

• arxiv url: http://arxiv.org/abs/2301.09833v1
• Date: Tue, 24 Jan 2023 06:14:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-25 14:19:47.669840
• Title: Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints
• Title（参考訳）: tutteの定理に基づくハイブリッドブール制約による量子インスパイアされた完全マッチング問題を解く
• Authors: Moshe Y. Vardi and Zhiwei Zhang
• Abstract要約: 量子コンピューティングで発生するハイブリッドブール制約の新しい応用について検討する。 この問題は、エッジカラーグラフにおける制約付き完全マッチングに関連している。 本稿では,ハイブリッド制約による制約マッチング問題の直接符号化が不十分であり,特殊な手法が依然として必要であることを示す。
• 参考スコア（独自算出の注目度）: 39.96302127802424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Determining the satisfiability of Boolean constraint-satisfaction problems with different types of constraints, that is hybrid constraints, is a well-studied problem with important applications. We study here a new application of hybrid Boolean constraints, which arises in quantum computing. The problem relates to constrained perfect matching in edge-colored graphs. While general-purpose hybrid constraint solvers can be powerful, we show that direct encodings of the constrained-matching problem as hybrid constraints scale poorly and special techniques are still needed. We propose a novel encoding based on Tutte's Theorem in graph theory as well as optimization techniques. Empirical results demonstrate that our encoding, in suitable languages with advanced SAT solvers, scales significantly better than a number of competing approaches on constrained-matching benchmarks. Our study identifies the necessity of designing problem-specific encodings when applying powerful general-purpose constraint solvers.
• Abstract（参考訳）: 異なるタイプの制約を持つブール制約-満足問題(ハイブリッド制約)の満足度を決定することは、重要なアプリケーションにおいてよく研究される問題である。 ここでは,量子コンピューティングにおけるハイブリッドブール制約の新しい応用について検討する。 この問題は、エッジカラーグラフにおける制約付き完全マッチングに関連している。 汎用ハイブリッド制約ソルバは強力であるが,ハイブリッド制約がスケールしにくいため,制約マッチング問題の直接エンコーディングが依然として必要であることを示す。 本稿では,グラフ理論におけるtutteの定理に基づく新しい符号化法と最適化手法を提案する。 実験の結果,satソルバを用いた適切な言語でのエンコーディングは,制約付きマッチングベンチマークにおいて,多くの競合手法よりもかなり優れていることがわかった。 本研究は,強力な汎用制約ソルバを適用する際に問題固有のエンコーディングを設計する必要性を明らかにした。

関連論文リスト

• QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
  我々はデータからQUBOフォームを導出するのではなく、勾配のバックプロパゲーションを通して学習する。 本稿では,グラフマッチングや2次元点雲のアライメント,3次元回転推定といった多種多様な問題に対する学習QUBOの利点を示す。
  論文  参考訳（メタデータ） (2022-10-13T17:59:46Z)
• An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints [0.0]
  表の制約はおそらく最も重要であり、最もよく研究され、有限変数上で定義された他の制約をエンコードする能力を持つ。 空間と時間の複雑さを減らすために、研究者は様々な種類の圧縮に焦点を当ててきた。 本稿では,テーブル制約の圧縮に関連する最大頻繁な項目セットを列挙するための,最大頻繁な項目セット手法と面積尺度に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2022-03-21T08:41:15Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  エネルギーシステムの最適化問題は、強い非線形系の挙動と複数の競合する目的のために複雑である。 場合によっては、提案された最適解は、物理的性質や安全クリティカルな操作条件に関連する明示的な入力制約に従う必要がある。 本稿では,ブラックボックス問題に対する制約付き多目的最適化のためのツリーアンサンブルを用いた新しいデータ駆動戦略を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:18:55Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。 ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
  論文  参考訳（メタデータ） (2021-02-17T19:55:42Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Encoding Linear Constraints into SAT [0.0]
  複数値決定ダイアグラムとソートネットワークに基づく新しいSATエンコーディングを定義する。 線形整数解法 (MIP) よりも優れており, 適切な問題に対して LCG や SMT より優れている場合もある。
  論文  参考訳（メタデータ） (2020-05-05T11:37:43Z)
• A Constraint Driven Solution Model for Discrete Domains with a Case Study of Exam Timetabling Problems [6.788217433800101]
  知的制約処理進化アルゴリズム (ICHEA) のバリエーションは, ベンチマーク試験の時間変化問題を解決するために実証されている。 ICHEAはまず、与えられた制約をすべて段階的に満たすために結婚間クロスオーバー演算子を使用し、その後、ソリューションを最適化するために従来の演算子と拡張演算子の組み合わせを使用する。
  論文  参考訳（メタデータ） (2020-02-08T06:53:38Z)

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

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