Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
Abstract
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4K−1, finds and verifies a homogeneous K-set using O (2K KlogK/η) edge queries with failure probability at most η. At the Ramsey scale N=2n, this yields a homogeneous set of order ⌊ n/2⌋+1 using O(√Nlog Nlog(log N/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12) quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/√2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only Õ(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
Related
- Quantum Uncertainty and Particle Trajectories: From Heisenberg and Schrödinger to Constructive Dynamical Models
- No off-diagonal quantum focusing for Rényi divergences
- The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound
- Robust Diamond Quantum Sensing in Double-Quantum 4-Ramsey Interferometry by Dual-Feedback Scheme
- Quantum field theory treatment of the spin-flavor precession of Dirac neutrinos with diagonal magnetic moments
BibTeX
@misc{xin2026quantum,
title = {{Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem}},
author = {Cheng Xin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05812},
eprint = {2609.05812},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05812},
}
RIS
TY - UNPB
TI - Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
AU - Cheng Xin
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.05812
UR - https://arxiv.org/abs/2609.05812
AB - The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4^K−1, finds and verifies a homogeneous K-set using O (2^K KlogK/η) edge queries with failure probability at most η. At the Ramsey scale N=2^n, this yields a homogeneous set of order ⌊ n/2⌋+1 using O(√Nlog Nlog(log N/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N^1/12) quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N^1−1/√2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only Õ(N^1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
ER -