Fugu-MT 論文翻訳(概要): QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems

論文の概要: QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems

arxiv url: http://arxiv.org/abs/2409.04476v1
Date: Thu, 5 Sep 2024 16:10:16 GMT
ステータス: 処理完了
システム内更新日: 2024-09-10 22:45:53.457702
Title: QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems
Title（参考訳）: Snake-in-the-box問題のQUBO定式化とCoil-in-the-box問題
Authors: Federico Fuidio, Eduardo Canale, Rafael Sotelo,
Abstract要約: 本稿では,Snake-in-the-box(SITB)問題とCoil-in-the-box(CITB)問題に対するQUBOの定式化について述べる。どちらの定式化も、最大誘導路と最大誘導路のNP-Hard問題を解くことができる。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This paper present the first QUBO formulations for the Snake-in-the-box (SITB) and Coil-in-the-box (CITB) problems. Both formulations are also capable of solving the NP-Hard problems of Maximum induced path and Maximum induced cylce respectively. In the process we also found a new QUBO formulation for the Maximum Common Induced Sub-graph problem. We proved the correctness of our formulations for the SITB, CITB and Maximum Common Sub-graph problem, and tested the formulations of the SITB and CITB in both classical and quantum solvers, being able to get the best solution for up to 5 dimensions.
Abstract（参考訳）: 本稿では,Snake-in-the-box(SITB)問題とCoil-in-the-box(CITB)問題に対するQUBOの定式化について述べる。どちらの定式化も最大誘導路と最大誘導路のNP-Hard問題をそれぞれ解くことができる。この過程で、最大共通誘導部分グラフ問題に対する新しいQUBOの定式化が発見された。 SITB, CITB, 最大共通部分グラフ問題の定式化の正しさを証明し, SITB, CITBの定式化を古典的および量子的解法の両方で検証し, 最大5次元の解を得ることができた。

関連論文リスト

A QUBO Formulation for the Generalized LinkedIn Queens Game [49.1574468325115]
本稿では、LinkedIn Queens ゲームの一連の一般化を解決するために設計された QUBO の定式化について述べる。この定式化は、変数の数と相互作用を最適化しようと試みることで、問題の特定のケースに適応する。また,カラーチェスピース問題 (Coloured Chess Piece Problem) とマックスチェスピース問題 (Max Chess Pieces Problem) という2種類の新しい問題を,対応するQUBOの定式化とともに提示する。
論文参考訳（メタデータ） (2024-10-08T23:54:54Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems [0.4972323953932129]
最適化のための量子コンピューティング指向ベンチマークを提案する。このベンチマークはQOPTLibと呼ばれ、4つのよく知られた問題を均等に分散した40のインスタンスで構成されている。本稿では,量子アニールに基づく2つの解法を用いたQOPTLibの完全解法について紹介する。
論文参考訳（メタデータ） (2024-04-24T13:02:33Z)
Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文参考訳（メタデータ） (2023-10-09T03:10:42Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文参考訳（メタデータ） (2022-12-06T22:01:49Z)
Hybrid Quantum-Classical General Benders Decomposition Algorithm for Unit Commitment with Multiple Networked Microgrids [5.6035987109587895]
マルチネットワークマイクログリッド(UCMNM)によるユニットコミットは、典型的な混合整数非線形プログラミング問題である。一般化ベンダー分解アルゴリズム(GBDA)フレームワークに量子コンピューティングを導入する。プライバシー保護と独立意思決定のために、HQC-GBDAはUCMNM問題をマスター問題と一連のサブプロブレムに分解する。
論文参考訳（メタデータ） (2022-10-13T02:26:27Z)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文参考訳（メタデータ） (2022-05-24T03:49:10Z)
GPS: A new TSP formulation for its generalizations type QUBO [0.0]
旅行セールスマン問題(TSP)の新しい2次非拘束バイナリ最適化(QUBO)を提案する。必要な変数の最小数の観点から、車両ルーティング問題(VRP)の最良の定式化を克服する。最後に,QUBO問題解法に入力することで定式化の正しさを検証した。
論文参考訳（メタデータ） (2021-10-23T07:10:24Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文参考訳（メタデータ） (2021-05-06T17:59:38Z)

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