論文の概要: Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

• arxiv url: http://arxiv.org/abs/2604.11449v1
• Date: Mon, 13 Apr 2026 13:28:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.561546
• Title: Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems
• Title（参考訳）: 重み付きグラフ分割問題における量子アニールの不均一サンプリング
• Authors: Shunta Ide, Shu Tanaka,
• Abstract要約: ペナルティ法におけるペナルティ係数がサンプリングフェアネスに与える影響について検討した。 70%以上のインスタンスは、ペナルティ係数が増加するにつれて単調にサンプリングフェアネスが増加する。 これらの結果から, ペナルティ係数の増大は, 基底状態の確率を犠牲にして, サンプリングフェアネスを向上させることが示唆された。
• 参考スコア（独自算出の注目度）: 0.7519872646378835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum annealing (QA) is a promising approach for solving combinatorial optimization problems; however, it is known to exhibit unfair sampling, in which degenerate ground states are not sampled with equal probability even for sufficiently long annealing times. Fair sampling is important in applications such as solution diversity assessment and combinatorial counting, yet the mechanism of unfair sampling remains poorly understood, particularly in constrained combinatorial optimization problems. In this work, we investigate unfair sampling of QA in weighted graph bipartitioning problems (GBP), a representative constrained optimization problem. We study how the penalty coefficient in the penalty method affects sampling fairness. Through numerical simulations and experiments on the D-Wave Advantage2 system, we show that increasing the penalty coefficient reduces unfair sampling in a representative single instance, and that this qualitative behavior is also observed on actual hardware. A scaling analysis over randomly generated instances with up to 12 spins reveals that, while this trend does not hold universally, more than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases, even at the largest system size studied. These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability under practical annealing conditions, and call for a deeper theoretical understanding of unfair sampling in constrained optimization problems.
• Abstract（参考訳）: 量子アニール法(QA)は組合せ最適化問題を解く上で有望な手法であるが、十分な長時間のアニール時間においても、縮退した基底状態が同じ確率でサンプリングされない不公平なサンプリングを示すことが知られている。 フェアサンプリングは、解の多様性評価や組合せ数計算などの応用において重要であるが、不公平サンプリングのメカニズムは、特に制約付き組合せ最適化問題においてよく理解されていない。 本研究では,重み付きグラフ分割問題(GBP)におけるQAの不正サンプリングについて検討する。 ペナルティ法におけるペナルティ係数がサンプリングフェアネスに与える影響について検討した。 D-Wave Advantage2 システムの数値シミュレーションと実験により,ペナルティ係数の増大は代表的な単一インスタンスにおける不公平サンプリングを減少させ,この定性的挙動を実際のハードウェア上でも観察できることが示されている。 最大12本のスピンを持つランダムに生成されたインスタンスに対するスケーリング解析では、この傾向は普遍的には保たないが、最も大きなシステムサイズであっても、ペナルティ係数が増大するにつれて、70%以上のインスタンスがサンプリングフェアネスを単調に増加させることが示されている。 これらの結果から, ペナルティ係数の増大は, 実際のアニール条件下での基底状態の確率を犠牲にしてサンプリング公正性を向上させることを示し, 制約された最適化問題における不公平サンプリングの深い理論的理解を求める。

関連論文リスト

• Stratified Sampling for Quasi-Probability Decompositions [0.0]
  準確率分解(QPD)は多くの量子アルゴリズムやプロトコルにおいて必須であることが証明されている。 我々は,この分散を考慮し,低減するための幅広い枠組みを構築している。 典型的なQPDの数値シミュレーションは、全体分散の定数要素の減少を示す。
  論文  参考訳（メタデータ） (2026-02-11T17:46:40Z)
• Importance-Weighted Non-IID Sampling for Flow Matching Models [5.995277983968318]
  本研究では,フロー分布の多様で健全な領域をカバーするために,複数のサンプルを共同で描画する重要重み付き非IIDサンプリングフレームワークを提案する。 多様性と品質のバランスをとるために,多様性機構のためのスコアベースの正規化を導入する。 提案手法は,重要度と期待値の双方について,多種多様で高品質なサンプルと正確な推定値を生成する。
  論文  参考訳（メタデータ） (2025-11-21T22:05:56Z)
• Sample space filling analysis for boson sampling validation [0.0]
  ボソンサンプリング波動関数の本質的な性質から,その充填挙動は古典的シミュレートされた場合と計算的に区別できることを示す。 サンプル空間充填分析に基づく新しい検証プロトコルを提案し,400ドルのモード干渉計に最大20ドルの光子を注入する問題に対して検証を行う。
  論文  参考訳（メタデータ） (2024-11-21T12:39:37Z)
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA [1.0878040851638]
  逆フィールドミキサーQAOAとグローバーミキサーQAOAのフェアサンプリング特性を数値的に検討する。 いくつかの問題では、シャノンエントロピーが最大バイアス分布で0$と明確に飽和していることが示される。 他の問題の場合、任意の$p$ステップで最大シャノンエントロピー(ユニフォーム)から逸脱することはない。
  論文  参考訳（メタデータ） (2024-11-08T02:54:28Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。 サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。 格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
  論文  参考訳（メタデータ） (2022-12-12T15:06:32Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  コラボレーティブ・メトリック・ラーニング(CML)パラダイムはレコメンデーション・システム(RS)分野に広く関心を集めている。 負のサンプリングが一般化誤差のバイアス付き推定に繋がることがわかった。 そこで我々は,SFCML (textitSampling-Free Collaborative Metric Learning) という名前のCMLに対して,負のサンプリングを伴わない効率的な手法を提案する。
  論文  参考訳（メタデータ） (2022-06-23T08:50:22Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)

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

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