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

• arxiv url: http://arxiv.org/abs/2301.09833v2
• Date: Thu, 18 May 2023 02:46:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-19 20:11:18.625422
• 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ソルバを用いた適切な言語でのエンコーディングは,制約付きマッチングベンチマークにおいて,多くの競合手法よりもかなり優れていることがわかった。 本研究は,強力な汎用制約ソルバを適用する際に問題固有のエンコーディングを設計する必要性を明らかにした。

関連論文リスト

• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
  NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。 分解法の性能を古典的・量子的メタヒューリスティックスで評価する。 提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
  論文  参考訳（メタデータ） (2023-10-04T12:14:56Z)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  我々は、ニューラルネットワークに厳しい制約を課すための一連のアプローチを開発する。 制約は、ニューラルネットワークとそのデリバティブに適用される線形作用素として指定することができる。 私たちのアプローチは、広範囲の現実世界のアプリケーションで実証されています。
  論文  参考訳（メタデータ） (2023-06-15T08:33:52Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。 これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
  論文  参考訳（メタデータ） (2023-05-14T03:49:10Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
  我々はデータからQUBOフォームを導出するのではなく、勾配のバックプロパゲーションを通して学習する。 本稿では,グラフマッチングや2次元点雲のアライメント,3次元回転推定といった多種多様な問題に対する学習QUBOの利点を示す。
  論文  参考訳（メタデータ） (2022-10-13T17:59:46Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。 学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。 また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
  論文  参考訳（メタデータ） (2021-05-14T11:31:14Z)
• 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)

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

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