論文の概要: Characterization of QUBO reformulations for the maximum $k$-colorable
subgraph problem
- arxiv url: http://arxiv.org/abs/2101.09462v1
- Date: Sat, 23 Jan 2021 09:28:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 04:23:07.408492
- Title: Characterization of QUBO reformulations for the maximum $k$-colorable
subgraph problem
- Title（参考訳）: 最大$k$-colorable部分グラフ問題に対するQUBO再構成のキャラクタリゼーション
- Authors: Rodolfo Quintero, David Bernal, Tam\'as Terlaky, and Luis F. Zuluaga
- Abstract要約: 量子デバイスは制約最適化(COPT)の問題を解決するために使用できる。
本稿では,$k$-colorable サブグラフの抽出を目的とした重要な制約付き COPT 問題について考察する。
我々は、M$k$CS問題に対する2つのQUBO改革法を導出し、QUBO改革法で使用可能なペナルティパラメータの範囲を完全に特徴づける。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum devices can be used to solve constrained combinatorial optimization
(COPT) problems thanks to the use of penalization methods to embed the COPT
problem's constraints in its objective to obtain a quadratic unconstrained
binary optimization (QUBO) reformulation of the COPT. However, the particular
way in which this penalization is carried out, affects the value of the penalty
parameters, as well as the number of additional binary variables that are
needed to obtain the desired QUBO reformulation. In turn, these factors
substantially affect the ability of quantum computers to efficiently solve
these constrained COPT problems. This efficiency is key towards the goal of
using quantum computers to solve constrained COPT problems more efficiently
than with classical computers. Along these lines, we consider an important
constrained COPT problem; namely, the maximum $k$-colorable subgraph (M$k$CS)
problem, in which the aim is to find an induced $k$-colorable subgraph with
maximum cardinality in a given graph. This problem arises in channel assignment
in spectrum sharing networks, VLSI design, human genetic research, and
cybersecurity. We derive two QUBO reformulations for the M$k$CS problem, and
fully characterize the range of the penalty parameters that can be used in the
QUBO reformulations. Further, one of the QUBO reformulations of the M$k$CS
problem is obtained without the need to introduce additional binary variables.
To illustrate the benefits of obtaining and characterizing these QUBO
reformulations, we benchmark different QUBO reformulations of the M$k$CS
problem by performing numerical tests on D-Wave's quantum annealing devices.
These tests also illustrate the numerical power gained by using the latest
D-Wave's quantum annealing device.
- Abstract（参考訳）: 量子デバイスは、COPTの2次非制約バイナリ最適化(QUBO)の修正を得るために、COPT問題の制約を埋め込むためにペナライズ法を用いることにより、制約付き組合せ最適化(COPT)問題を解決するために使用できる。
しかし、この罰則が適用される特定の方法は、所望のQUBO改定を得るために必要となる追加のバイナリ変数の数だけでなく、ペナルティパラメータの値にも影響を及ぼす。
これらの要因は、量子コンピュータがこれらの制約されたCOPT問題を効率的に解く能力に大きく影響する。
この効率性は、量子コンピュータを用いて制約されたCOPT問題を従来のコンピュータよりも効率的に解くという目標に向かっている。
これらの線に沿って、重要な制約付きCOPT問題、すなわち最大$k$-colorable subgraph (M$k$CS)問題を考える。
この問題は、スペクトル共有ネットワーク、VLSI設計、ヒト遺伝研究、サイバーセキュリティにおけるチャネル割り当てに発生する。
我々は、M$k$CS問題に対する2つのQUBO改革法を導出し、QUBO改革法で使用可能なペナルティパラメータの範囲を完全に特徴づける。
さらに、M$k$CS問題のQUBO再構成の1つは、追加のバイナリ変数を導入することなく得られる。
D-Waveの量子アニーリングデバイス上で数値実験を行うことにより、これらのQUBO再構成の利点を実証するために、M$k$CS問題の異なるQUBO再構成をベンチマークする。
これらのテストはまた、最新のD-Waveの量子アニールデバイスを用いて得られる数値パワーも示している。
関連論文リスト
- Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
量子デバイスからの全ての出力が有効な経路にマッピングされるため、設計上、ペナルティ項は存在しない。
ボソンサンプルを用いて研究を行ったが、この新しい定式化は他の量子デバイスと関係があると信じている。
論文 参考訳（メタデータ） (2024-06-20T12:25:00Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳（メタデータ） (2022-11-25T06:05:18Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - 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) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
論文 参考訳（メタデータ） (2022-03-23T18:00:03Z) - Testing a QUBO Formulation of Core-periphery Partitioning on a Quantum
Annealer [3.093890460224435]
本稿では,非指向ネットワークにおけるコア周辺パーティションを演算するタスクの成功を定量化する新しいカーネルを提案する。
関連する最適分割を見つけることは、二次的制約のない二項最適化問題の形で表すことができる。
このアプローチを,既存のコア周辺分割手法と比較する。
論文 参考訳（メタデータ） (2022-01-05T11:08:09Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - 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) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳（メタデータ） (2021-01-19T17:51:02Z) - An Ensemble Approach for Compressive Sensing with Quantum [1.8477401359673713]
統計的アンサンブルのアイデアを活用して、量子アニールに基づくバイナリ圧縮センシングの品質を向上させる。
D-Wave 2000Q量子プロセッサを用いた実験により,提案したアンサンブル方式はペナルティパラメータの校正に敏感でないことが明らかとなった。
論文 参考訳（メタデータ） (2020-06-08T15:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。