Quantum King-Ring Domination in Chess: A QAOA Approach

• URL: http://arxiv.org/abs/2601.00318v1
• Date: Thu, 01 Jan 2026 11:59:40 GMT
• Title: Quantum King-Ring Domination in Chess: A QAOA Approach
• Authors: Gerhard Stenzel, Michael Kölle, Tobias Rohe, Julian Hager, Leo Sünkel, Maximilian Zorn, Claudia Linnhoff-Popien,
• Abstract summary: Quantum King-Ring Domination (QKRD) is a NISQ-scale benchmark derived from chess tactical positions.<n>We systematically evaluate QAOA design choices and find that constraint-preserving mixers converge approximately 13 steps faster than standard mixers.<n>Intrinsic validation shows QAOA outperforms greedys by 12.6% and random selection by 80.1%.
• Score: 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.

Related papers

• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• Benchmarking Lie-Algebraic Pretraining and Non-Variational QWOA for the MaxCut Problem [4.103893081207555]
  This paper provides a comparative performance analysis of two strategies designed to improve trainability.<n>We benchmark both methods on the unweighted Maxcut problem using a circuit depth of $p = 256$ across 200 Erds-Rényi and 200 3-regular graphs.<n>Both approaches significantly improve upon the standard randomly QWOA. NV-QWOA attains a mean approximation ratio of 98.9% in just 60 iterations, while the Lie-algebraic pretrained QWOA improves to 77.71% after 500 iterations.
  arXiv  Detail & Related papers  (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) model serves as a foundational framework for understanding disordered systems.<n>Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$.<n>We analyze QAOA applied to the SK model in the infinite-size limit and provide numerical evidence that it obtains a $(1-epsilon)$ approximation to the optimal energy with circuit depth $mathcalO(n/epsilon1.13)$ in the average case.
  arXiv  Detail & Related papers  (2025-05-12T18:00:01Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  The ability of the Quantum Approximate Optimization Algorithm to deliver a quantum advantage on optimization problems is still unclear.<n>We analyze the QAOA's performance on random Max-$k$XOR as a function of $k$ and the clause-to-variable ratio.<n>We find that reaching high levels of satisfaction would require extremely large $p$, which must be considered rather difficult both in the variational context and on near-term devices.
  arXiv  Detail & Related papers  (2024-11-28T21:39:58Z)
• Reducing Variance in Temporal-Difference Value Estimation via Ensemble of Deep Networks [109.59988683444986]
  MeanQ is a simple ensemble method that estimates target values as ensemble means. We show that MeanQ shows remarkable sample efficiency in experiments on the Atari Learning Environment benchmark.
  arXiv  Detail & Related papers  (2022-09-16T01:47:36Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  We study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to quantum computing problems. We develop analytic bounds on the average success probability of QAOA over random formulae at the satisfiability threshold. We find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver.
  arXiv  Detail & Related papers  (2022-08-14T20:39:48Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  Sparse adversarial attacks can fool deep networks (DNNs) by only perturbing a few pixels. Recent efforts combine it with another l_infty perturbation on magnitudes. We propose a homotopy algorithm to tackle the sparsity and neural perturbation framework.
  arXiv  Detail & Related papers  (2021-06-10T20:11:36Z)
• Escaping Saddle Points in Distributed Newton's Method with Communication efficiency and Byzantine Resilience [49.379254729853756]
  We consider the problem of optimizing a non-regularized loss function (with saddle points) in a distributed framework in the presence of Byzantine machines. We robustify the cubic-regularized Newton algorithm such that it avoids the saddle points and the fake local minimas efficiently. We obtain theoretical guarantees for our proposed scheme under several approximate settings including (sub-sampled) and Hessians.
  arXiv  Detail & Related papers  (2021-03-17T03:53:58Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  We propose an Accurate Quantized object Detection solution, termed AQD, to get rid of floating-point computation. Our AQD achieves comparable or even better performance compared with the full-precision counterpart under extremely low-bit schemes.
  arXiv  Detail & Related papers  (2020-07-14T09:07:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.