論文の概要: Solving the MAX-$k$-CUT problem for hypergraphs with quantum computing

• arxiv url: http://arxiv.org/abs/2610.41678v1
• Date: Fri, 30 Oct 2026 12:46:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.70925
• Title: Solving the MAX-$k$-CUT problem for hypergraphs with quantum computing
• Title（参考訳）: 量子コンピューティングを用いたハイパーグラフにおけるMAX-$k$-CUT問題の解法
• Abstract要約: ハイパーグラフ上のMAX-$k$-CUT問題について,Ising相互作用を持つスピン系として表現することで検討する。 ハイパーグラフ上のMAX-$k$-CUT問題に対する対応するコストハミルトニアンは、ペアの相互作用を持つイジング・ハミルトニアンに還元される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the MAX-$k$-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-$k$-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-$k$-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-$k$-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.
• Abstract（参考訳）: ハイパーグラフ上のMAX-$k$-CUT問題について,Ising相互作用を持つスピン系として表現することで検討する。 ハイパーグラフ上のMAX-$k$-CUT問題に対する対応するコストハミルトニアンは、ペアの相互作用を持つイジング・ハミルトニアンに還元される。 この還元は量子コンピューティングを用いたMAX-$k$-CUT問題の解を単純化する。 例を挙げると、3ユニフォームのタイトスターハイパーグラフとサンフラワーハイパーグラフが考えられる。 対応するハミルトニアンは構成され、MAX-$k$-CUT問題の量子プロトコルが提示される。 MAX-3-CUT と MAX-4-CUT のインスタンスは、IBM の Qiskit AerSimulator 上の量子コンピューティングを用いて、 (p=2) から (p=15) までの量子近似最適化アルゴリズム (QAOA) の層数を変化させることで、これらのハイパーグラフに対して検討される。

関連論文リスト

• Three-uniform edge-ordered hypergraph quantum states: entanglement and its relation to hypergraph properties [0.0]
  ハイパーグラフ量子状態の絡み合いを解析的に、量子コンピューティングを用いて研究する。 これらの結果は、量子プログラミングによるハイパーグラフ特性の研究の可能性を開く。
  論文  参考訳（メタデータ） (2026-09-24T18:04:35Z)
• The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem [0.0]
  我々は,量子ハイパーグラフのMax-Cut問題に対する近似の平均ケース硬さを解析する。 弱硬度の結果を示し、任意のリプシッツ定数$L$に対して、$L$stableアルゴリズムが最適解を近似できないような$k$が存在することを示す。
  論文  参考訳（メタデータ） (2026-09-09T21:18:05Z)
• Quantum Max Cut for complete tripartite graphs [0.0]
  量子マックス=$d$-Cut(d$-QMC)問題は、局所的なハミルトン問題の特別な例である。 この記事では、小さな局所次元に対する完全三部グラフに対する$d$-QMC問題を、$d le 3$で解決する。
  論文  参考訳（メタデータ） (2025-12-03T12:37:48Z)
• Quantum Speedup for Hypergraph Sparsification [3.5293335880819483]
  Apers and de Wolf(FOCS'20)によるオープン問題に対処する,ハイパーグラフスカラー化のための最初の量子アルゴリズムを提案する。 n$頂点、$m$ハイパーエッジ、およびランク$r$の重み付きハイパーグラフに対して、我々のアルゴリズムは、時間$widetilde O(rsqrtmn/varepsilon)$で、ほぼ直線サイズの$varepsilon$-spectral sparsifierを出力する。 このアルゴリズムは定数$r$の量子ローバウンドと一致し、状態と比較した場合の量子スピードアップを示す。
  論文  参考訳（メタデータ） (2025-05-03T09:33:46Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• 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 Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA [0.0]
  本稿では、ノイズのある中間スケール量子(NISQ)デバイス上で量子近似最適化アルゴリズム(QAOA)を実行するのに適した重み付きMAX k-CUTの定式化について述べる。 新しい定式化は、|V|log_2(k) 量子ビットのみを必要とするバイナリエンコーディングを使用する。
  論文  参考訳（メタデータ） (2020-09-02T14:15:55Z)

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

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