論文の概要: Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing

• arxiv url: http://arxiv.org/abs/2511.01108v1
• Date: Sun, 02 Nov 2025 22:49:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 20:56:29.058847
• Title: Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing
• Title（参考訳）: 量子コンピューティングにおけるMax-k-Cut問題のQUBO再構成の特徴付け
• Authors: Adrian Harkness, Hamidreza Validi, Ramin Fakhimi, Illya V. Hicks, Tamás Terlaky, Luis F. Zuluaga,
• Abstract要約: 量子コンピューティングは、古典的コンピュータの到達範囲を超えているNP重み付き(最適化)問題を解く大きな可能性を秘めている。 この可能性を活用する方法の1つは、2次非制約バイナリ最適化(QUBO)問題として問題を再構成することである。 最大$k$-cut問題の2つの異なるQUBO再構成に対する厳格なペナルティ係数の閉形式的特徴について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing offers significant potential for solving NP-hard combinatorial (optimization) problems that are beyond the reach of classical computers. One way to tap into this potential is by reformulating combinatorial problems as a quadratic unconstrained binary optimization (QUBO) problem. The solution of the QUBO reformulation can then be addressed using adiabatic quantum computing devices or appropriate quantum computing algorithms on gate-based quantum computing devices. In general, QUBO reformulations of combinatorial problems can be readily obtained by properly penalizing the violation of the problem's constraints in the original problem's objective. However, characterizing tight (i.e., minimal but sufficient) penalty coefficients for this purpose is critical for enabling the solution of the resulting QUBO in current and near-term quantum computing devices. Along these lines, we here focus on the (weighted) max $k$-cut problem, a fundamental combinatorial problem with wide-ranging applications that generalizes the well-known max cut problem. We present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem whose values depend on the (weighted) degree of the vertices of the graph defining the problem. These findings contribute to the ongoing effort to make quantum computing a viable tool for solving combinatorial problems at scale. We support our theoretical results with illustrative examples. Further, we benchmark the proposed QUBO reformulations to solve the max $k$-cut problem on a quantum computer simulator.
• Abstract（参考訳）: 量子コンピューティングは、古典的なコンピュータの到達範囲を超えたNPハード組合せ(最適化)問題を解く大きな可能性を秘めている。 この可能性を利用する1つの方法は、組合せ問題を2次非制約バイナリ最適化(QUBO)問題として再構成することである。 QUBO改革の解決策は、ゲートベースの量子コンピューティングデバイス上で、断熱型量子コンピューティングデバイスまたは適切な量子コンピューティングアルゴリズムを使用して解決することができる。 一般に、QUBOの組合せ問題修正は、元の問題の目的における問題の制約違反を適切に罰することにより容易に得ることができる。 しかし、この目的のために厳密な(最小限だが十分な)ペナルティ係数を特徴付けることは、現在の量子コンピューティングデバイスと短期量子コンピューティングデバイスにおける結果のQUBOの解を可能にするために重要である。 これらの線に沿って、よく知られた最大カット問題を一般化する広帯域アプリケーションに対する基本的な組合せ問題である(重み付けされた)最大$k$-cut問題に焦点を当てる。 問題を定義するグラフの頂点の(重み付けされた)次数に依存する最大$k$-cut問題の2つの異なるQUBO修正に対する厳格なペナルティ係数の閉形式的特徴付けを示す。 これらの発見は、量子コンピューティングを大規模な組合せ問題を解くための実行可能なツールにするための継続的な努力に寄与している。 実証的な例で理論結果を支持する。 さらに,量子計算機シミュレータ上での最大$k$-cut問題を解くため,提案したQUBO再構成をベンチマークした。

関連論文リスト

• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。 D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-04-26T21:29:42Z)
• Quantum-based Distributed Algorithms for Edge Node Placement and Workload Allocation [8.937905773981702]
  最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。 既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。 数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
  論文  参考訳（メタデータ） (2023-06-01T21:33:08Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• 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)
• Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem [0.0]
  量子デバイスは制約最適化(COPT)の問題を解決するために使用できる。 本稿では,$k$-colorable サブグラフの抽出を目的とした重要な制約付き COPT 問題について考察する。 我々は、M$k$CS問題に対する2つのQUBO改革法を導出し、QUBO改革法で使用可能なペナルティパラメータの範囲を完全に特徴づける。
  論文  参考訳（メタデータ） (2021-01-23T09:28:33Z)

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

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