{"id":"arxiv/2609.05812","url":"https://arxiv.org/abs/2609.05812","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem","domain":"quant-ph","source":"arxiv","authors":["Cheng Xin"],"reviews":0,"subject":"quant-ph","summary":"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\\ge2$ and $N\\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\\!\\left(2^K K\\log\\frac Kη\\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\\lfloor n/2\\rfloor+1$ using $O(\\sqrt N\\log N\\log(\\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-05","reactions":{}}