論文の概要: Quantum King-Ring Domination in Chess: A QAOA Approach

• arxiv url: http://arxiv.org/abs/2601.00318v1
• Date: Thu, 01 Jan 2026 11:59:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-05 15:04:33.374545
• Title: Quantum King-Ring Domination in Chess: A QAOA Approach
• Title（参考訳）: チェスにおける量子キングリング支配:QAOAアプローチ
• Authors: Gerhard Stenzel, Michael Kölle, Tobias Rohe, Julian Hager, Leo Sünkel, Maximilian Zorn, Claudia Linnhoff-Popien,
• Abstract要約: 量子キングリング・ドミネーション(Quantum King-Ring Domination、QKRD)は、チェスの戦術的位置から派生したNISQスケールのベンチマークである。 我々はQAOA設計選択を体系的に評価し、制約保存ミキサーが標準ミキサーよりも約13ステップ早く収束していることを見出した。 内在的検証では、QAOAはグリーディを12.6%、ランダム選択を80.1%上回っている。
• 参考スコア（独自算出の注目度）: 2.7474031534471384
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is extensively benchmarked on synthetic random instances such as MaxCut, TSP, and SAT problems, but these lack semantic structure and human interpretability, offering limited insight into performance on real-world problems with meaningful constraints. We introduce Quantum King-Ring Domination (QKRD), a NISQ-scale benchmark derived from chess tactical positions that provides 5,000 structured instances with one-hot constraints, spatial locality, and 10--40 qubit scale. The benchmark pairs human-interpretable coverage metrics with intrinsic validation against classical heuristics, enabling algorithmic conclusions without external oracles. Using QKRD, we systematically evaluate QAOA design choices and find that constraint-preserving mixers (XY, domain-wall) converge approximately 13 steps faster than standard mixers (p<10^{-7}, d\approx0.5) while eliminating penalty tuning, warm-start strategies reduce convergence by 45 steps (p<10^{-127}, d=3.35) with energy improvements exceeding d=8, and Conditional Value-at-Risk (CVaR) optimization yields an informative negative result with worse energy (p<10^{-40}, d=1.21) and no coverage benefit. Intrinsic validation shows QAOA outperforms greedy heuristics by 12.6\% and random selection by 80.1\%. Our results demonstrate that structured benchmarks reveal advantages of problem-informed QAOA techniques obscured in random instances. We release all code, data, and experimental artifacts for reproducible NISQ algorithm research.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、MaxCut、TSP、SAT問題などの合成ランダムインスタンスに対して広範囲にベンチマークされているが、これらは意味構造と人間の解釈性に欠けており、意味のある制約のある実世界の問題の性能について限られた洞察を与えている。 我々は,1ホット制約,空間的局所性,10-40キュービットスケールを備えた5,000の構造化インスタンスを提供する,チェスの戦術的位置から派生したNISQスケールベンチマークであるQuantum King-Ring Domination (QKRD)を紹介する。 このベンチマークは、人間の解釈可能なカバレッジメトリクスと、古典的ヒューリスティックスに対する本質的な検証を組み合わせ、外部のオラクルなしでアルゴリズムによる結論を可能にする。 QKRDを用いてQAOA設計選択を体系的に評価し、制約保存ミキサー(XY, ドメインウォール)が標準ミキサー(p<10^{-7}, d\approx0.5)よりも約13ステップ早く収束し、ペナルティチューニングを排除し、エネルギー効率がd=8を超える45ステップ(p<10^{-127}, d=3.35)の収束を減少させ、条件値-at-Risk(CVaR)最適化により、より悪いエネルギー(p<10^{-40}, d=1.21)の付加的な負の結果が得られ、カバレッジの利益が得られないことを見出した。 内在的検証は、QAOAが欲求的ヒューリスティックスを12.6\%、ランダム選択を80.1\%で上回ることを示している。 この結果から,構造化されたベンチマークにより,ランダムなインスタンスに隠れたQAOA手法の利点が示された。 我々は、再現可能なNISQアルゴリズム研究のためのコード、データ、実験的な成果物を全てリリースする。

関連論文リスト

• Benchmarking Lie-Algebraic Pretraining and Non-Variational QWOA for the MaxCut Problem [4.103893081207555]
  本稿では,トレーニング性向上を目的とした2つの戦略の比較性能解析を行う。 回路深さは200 Erds-Rényi および 200 3-正則グラフに対して 256$ である。 NV-QWOAはわずか60回で平均98.9%の近似比を獲得し、Lie-代数的事前訓練されたQWOAは500回で77.71%に改善された。
  論文  参考訳（メタデータ） (2025-12-28T09:42:02Z)
• Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case [3.4872784636892047]
  Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、量子最適化アルゴリズムであり、その性能は深さ$p$で単調に向上する。 無限大の極限においてSKモデルに適用されたQAOAを解析し、回路深さ$mathcalO(n/epsilon1.13)$の最適エネルギーに対して1-epsilon$の近似が得られるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2025-05-12T18:00:01Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。 ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。 満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
  論文  参考訳（メタデータ） (2024-11-28T21:39:58Z)
• Reducing Variance in Temporal-Difference Value Estimation via Ensemble of Deep Networks [109.59988683444986]
  MeanQは単純なアンサンブル法であり、ターゲット値をアンサンブル平均として推定する。 本稿では,Atari Learning Environmentベンチマークを用いた実験において,MeanQが顕著なサンプル効率を示すことを示す。
  論文  参考訳（メタデータ） (2022-09-16T01:47:36Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。 我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。 約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
  論文  参考訳（メタデータ） (2022-08-14T20:39:48Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  少数の敵対的攻撃は、数ピクセルを摂動するだけでディープ・ネットワーク(DNN)を騙すことができる。 近年の取り組みは、他の等級のl_infty摂動と組み合わせている。 本稿では,空間的・神経的摂動に対処するホモトピーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-10T20:11:36Z)
• Escaping Saddle Points in Distributed Newton's Method with Communication efficiency and Byzantine Resilience [49.379254729853756]
  我々は、ビザンチン機械の存在下で分散フレームワークにおける非正規化損失関数(サドルポイント付き)を最適化する問題を検討する。 キューブ正規化されたニュートンアルゴリズムを堅牢化し、サドルポイントと偽のローカルミニマを効率的に回避します。 提案手法は, (サブサンプリング) と hessian を含むいくつかの近似設定で理論的に保証される。
  論文  参考訳（メタデータ） (2021-03-17T03:53:58Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  本稿では,浮動小数点演算を除去するために,AQDと呼ばれる高精度な量子化オブジェクト検出ソリューションを提案する。 我々のAQDは、非常に低ビットのスキームの下での完全精度と比較して、同等またはそれ以上の性能を実現しています。
  論文  参考訳（メタデータ） (2020-07-14T09:07:29Z)

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

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