論文の概要: Quantum Hypergraph Partitioning

• arxiv url: http://arxiv.org/abs/2605.10623v1
• Date: Mon, 11 May 2026 14:16:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.885172
• Title: Quantum Hypergraph Partitioning
• Title（参考訳）: 量子ハイパーグラフ分割
• Authors: Cameron Ibrahim, Bao G. Bach, Jad Salem, Reuben Tate, Kien X. Nguyen, Stephan Eidenbenz, Ilya Safro,
• Abstract要約: 所望の出力が分割上の確率分布であるハイパーグラフ分割問題について検討する。 極小目的と極小目的に動機づけられた超グラフ分割の分布的視点を導入する。 これらの目的がQAOAによって生成された測定分布とどのように自然に一致しているかを示す。
• 参考スコア（独自算出の注目度）: 2.861738681021997
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum optimization algorithms are inherently probabilistic, yet they are most often used to search for a single high-quality solution. In this paper, we instead study hypergraph partitioning problems in which the desired output is itself a probability distribution over partitions. We introduce a distributional perspective on hypergraph partitioning motivated by maximin and minimax objectives such as Fair Cut Cover, and we show how these objectives align naturally with the measurement distribution produced by QAOA. To motivate the formulation, we introduce a workforce-scheduling-inspired toy problem, the Greatest Expected Imbalance problem, in which the goal is to minimize the worst expected imbalance across hyperedges. We then develop QAOA-based quantum solvers that represent distributional solutions natively through quantum states, together with quadratic hypergraph objectives suitable for standard and multi-objective QAOA. These formulations connect balanced hypergraph partitioning, polarized community discovery, and distributional fairness under a unified quantum optimization framework. For comparison, we provide optimal polynomial-time classical approximation algorithms based on semidefinite programming and hyperplane rounding. Experiments on real-world and synthetic hypergraphs demonstrate that low-depth multi-angle QAOA can outperform these classical approximation baselines on the proposed objectives, highlighting the potential of quantum algorithms for optimization problems where the solution is a distribution rather than a single partition.
• Abstract（参考訳）: 量子最適化アルゴリズムは本質的に確率的であるが、1つの高品質な解を探すのによく用いられる。 そこで本研究では,所望の出力が分割上の確率分布である超グラフ分割問題について検討する。 本研究は,Fair Cut Cover などの最大値と最小値の目的値によって動機付けられたハイパーグラフ分割の分布的視点を導入し,これらの目的値がQAOA が生成する測定分布とどのように自然に一致しているかを示す。 定式化の動機付けとして,労働スケジュールにインスパイアされた玩具問題である,最大予測不均衡問題を導入し,ハイパーエッジ間の最悪の不均衡を最小化することを目的とする。 次に、QAOAをベースとした量子解法を開発し、量子状態を通して分散解をネイティブに表現し、標準および多目的QAOAに適した2次ハイパーグラフの目的を定式化する。 これらの定式化は、バランスの取れたハイパーグラフ分割、偏極化されたコミュニティ発見、および統一された量子最適化フレームワークの下での分布フェアネスを結合する。 比較のために,半定値プログラミングと超平面ラウンドリングに基づく多項式時間古典近似アルゴリズムを提案する。 実世界および合成ハイパーグラフの実験により、低深さのマルチ角QAOAは、提案した目的に基づいてこれらの古典的な近似ベースラインを上回り、解が単一パーティションではなく分布であるような最適化問題に対する量子アルゴリズムの可能性を強調した。

関連論文リスト

• Learning Cut Distributions with Quantum Optimization [0.3113876454957647]
  本稿では,分散最適化問題に対する量子的アプローチを提案する。 有限層の層で、ビットストリング上の任意の分布を捉えるためにQAOAアンサッツを構築することができる。 提案アルゴリズムは,グラフ構造上の古典的近似よりも有意に優れていることを示す。
  論文  参考訳（メタデータ） (2026-04-15T19:55:14Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  本稿では、量子ハードウェア上でのユニタリ結合クラスタ波関数の最適化のための射影量子固有解法(PQE)アプローチについて検討する。 我々は、ハミルトニアンの外部対角係数(残差)とアルゴリズムのエネルギー誤差と得られた波動関数によって達成された重なり関係を導出する。
  論文  参考訳（メタデータ） (2024-10-19T15:03:59Z)
• Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
  量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。 量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。 本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
  論文  参考訳（メタデータ） (2023-10-08T08:07:11Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  本稿では,非支配解と結合累積分布関数の極端量子化との自然な関係を示す。 このリンクにより、我々はPareto対応CDFインジケータと関連する取得関数BOtiedを提案する。 種々の合成および実世界の問題に対する実験により,BOtied は最先端MOBO 取得関数より優れていることが示された。
  論文  参考訳（メタデータ） (2023-06-01T04:50:06Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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