PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

arXiv:2609.05812v1quant-phcs.DS

TL;DR

Finding a Ramsey-guaranteed clique or independent set with adjacency-oracle queries has an open query-complexity question. This paper uses quantum search over implicitly represented candidate sets. It reports the first sublinear worst-case query algorithm and a polynomial separation on random graphs, while limiting its claims to query bounds.

  • Problem

    The query complexity of finding a clique or independent set of Ramsey-guaranteed order remains an open question across deterministic, randomized, and quantum models.

    Source: §1 · p. 1

  • Method

    The quantum algorithm represents recursive candidate sets by earlier pivots’ adjacency constraints and samples them using quantum search.

    Source: §1 · p. 1

  • Results

    The paper reports the first sublinear worst-case query algorithm for the Ramsey relation and a polynomial quantum–randomized separation on G(N, 1/2).

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    Whenever the algorithm reaches its final verified output, it is a K-clique or a K-vertex independent set.

    Source: §3.3 · p. 5

    The paper claims query bounds only, not gate complexity or hardware performance.

    Source: §6 · p. 8

Abstract

from arXiv · show

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\eta\right)$ edge queries with failure probability at most $\eta$. 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/\eta))$ 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 $\Omega(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 $\Omega(N^{1-1/\sqrt2})$ 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 $\widetilde O(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.

1 Introduction

The paper addresses the open query complexity of finding a Ramsey-guaranteed homogeneous set and presents a quantum approach that avoids explicitly constructing the recursive candidate sets. It gives worst-case and random-graph results, an estimation-free recursion, and a scale-aware sampling analysis.

1 Introduction

  • The paper studies the open query complexity of finding a clique or independent set of Ramsey-guaranteed order, for which the classical constructive recursion uses O(N) adjacency queries.The query complexity in deterministic, randomized, and quantum models is posed as an open question in [13, Section III].Source: §1 · p. 1

1.1 Our results

  • The quantum algorithm finds and verifies a clique or independent set of order K in the worst case, and the paper identifies it as the first sublinear worst-case query algorithm for the Ramsey relation.At N = 2^n, the stated target order is floor(n/2)+1.Source: §1.1 · p. 2
  • The estimation-free size-biased recursion completes with probability greater than 1/2 from 4K−1 vertices without majority estimation and extends to every fixed number of edge colours.It follows the colour of a uniformly sampled edge, selecting a colour class with probability proportional to its size.Source: §1.1 · p. 2
  • On G(N, 1/2), greedy quantum neighbourhood search uses eO(N^1/4) queries, and the distributional lower bound gives a polynomial separation from randomized query complexity.For M = 4K−1, the paper also transports the random-Painter weight estimate to the query model, including on G(M, 1/2).Source: §1.1 · pp. 2–3
  • The reported quantum lower bound is Ω(N^1/12), replacing a cited N^1−o(1) report that the paper says cannot hold at these parameters.The paper attributes the bound to the collision reduction and says the cited ingredients yield an exponent of at most 1/12, or 1/24 under the printed parameter condition.Source: §1.1 · p. 3

1.2 Techniques

  • Candidate sets are represented by the conjunction of earlier pivots’ adjacency constraints and sampled with capped quantum search, while estimation error is allocated according to the increasing cost of deeper levels.The scale-aware schedule doubles the allowed error every six levels; a product invariant keeps candidate sets within a constant factor of their ideal sizes.Source: §1 · p. 1, §1.2 · p. 3
  • At recursion depth j, common-neighbourhood density is about 2^-j, so greedy quantum search costs O(2^j/2) predicate evaluations at that depth.A union bound is used to show that every j-set has common neighbourhood of about that density.Source: §1.2 · p. 3

2 Oracle model and capped quantum sampling

The paper defines a coherent adjacency-oracle query model and gives a capped quantum sampler for implicitly represented marked sets. It also transfers the query upper bound to a standard Ramsey TFNP relation with arbitrary Boolean-circuit encodings.

2 Oracle model and capped quantum sampling

  • The coherent edge oracle returns the queried edge bit by XORing it into the answer register, and query complexity counts oracle calls while reversible vertex-label operations are free.Source: §2 · p. 3
  • The standard Ramsey TFNP relation with arbitrary Boolean-circuit encodings has the same O(2^K K log(K/η)) quantum-query upper bound as the main theorem.The relation accepts a local invalidity certificate or a locally verified homogeneous set.Source: §2 · p. 3
  • A capped quantum search block uses O(q/λ) edge queries, succeeds with constant probability, and returns an exactly uniform marked item conditional on verified success.The block has a predetermined cap even if the density promise is false or the marked set is empty.Source: §2 · p. 4
  • When the density promise holds, m independent uniform samples can be collected using a predetermined O(m + log(1/δ)) blocks, except with probability δ.Source: §2 · p. 4
  • Unlike the explicit classical recursion, which truncates a majority-colour neighbourhood, the quantum algorithms retain the selected colour class but access it implicitly.The classical recursion on M = 4K−1 vertices uses fewer than 2M queries in total.Source: §2 · p. 4

3 Implicit-set recursions and the main theorem

The section gives two quantum recursions over implicit candidate sets: an estimation-free size-biased version and a scale-aware majority-estimating version. Their analyses establish completion, query-cost, and exact-output guarantees.

3.1 An estimation-free size-biased recursion

  • The size-biased recursion completes with probability at least 1/2 + 1/M from M = 4K−1 vertices after r = 2K−3 steps.Sampling chooses the two colour classes with probabilities proportional to their sizes; charging each search failure probability 1/(100r) leaves completion probability at least 0.49.Source: §3.1 · p. 4
  • O(K^2 2^K log K log(1/η)) queries suffice for a verified homogeneous K-set with failure probability at most η in the estimation-free recursion.The recursion also extends to every fixed number of edge colours.Source: §3.1 · p. 4

3.2 Scale-aware approximate majorities

  • The scale-aware recursion represents each candidate set by prior pivot-edge constraints, estimates each pivot’s colour majority, and verifies its final homogeneous set directly.The allowed estimation error doubles every six levels to account for the increasing cost of sampling deeper sets.Source: §3.2 · p. 5

3.3 Analysis

  • Every returned witness is a K-clique or K-vertex independent set because the algorithm directly checks the induced edges before output.The direct check makes output correctness independent of earlier estimation errors.Source: §3.3 · p. 5
  • O(2^K K log(K/η)) queries suffice for the scale-aware recursion, with probability at least 1−η that searches and estimates succeed and the final candidate set is nonempty.The cost analysis combines the amplified searches and sampling batches across the recursion levels.Source: §3.3 · pp. 5–6

4 Lower bounds and a quantum speedup on random graphs

The section establishes a randomized query lower bound on uniformly random graphs, a quantum speedup on that distribution, and a quantum lower bound from collision finding. The random-graph separation is distributional; no worst-case separation is claimed.

4.1 A randomized classical lower bound

  • The randomized lower-bound estimate is transported from online Ramsey numbers and applies on the uniform distribution G(N, 1/2).The text explicitly does not claim a worst-case separation from the paper’s main theorem.Source: §4.1 · p. 6

4.2 A quantum speedup on random graphs

  • O(K 2^(K/2) log(K/η)) queries find a K-clique on G(M, 1/2) with probability at least 1−η−πK, using a greedy quantum search.With high probability, every smaller vertex set has many common neighbours, allowing capped search to grow the clique one vertex at a time.Source: §4.2 · p. 6
  • An O(N^(1/4) log N log(log N/η))-query quantum algorithm outputs a homogeneous K-set with probability at least 1−η−π_K; the stated randomized success probability is at most 5/8.For the Ramsey relation on G(N, 1/2), bounded-error quantum query complexity is polynomially smaller than bounded-error randomized query complexity.Source: §4.2 · pp. 6–7

4.3 A quantum lower bound from collision finding

  • The quantum collision reduction gives an Ω(N^(1/12)) query lower bound for finding a clique or independent set of order ⌊n/2⌋ on every N = 2^n vertex input.A sufficiently large homogeneous set in the constructed graph must contain two vertices with the same value under the reduced function, yielding a collision.Source: §4.3 · p. 7

5 Related work and the reported lower bound

The related-work discussion distinguishes this oracle-query setting from earlier quantum Ramsey approaches and situates constructive Ramsey search among proof-complexity and query-complexity questions. It also checks the parameter alignment and exponent of a reported quantum lower bound.

5 Related work and the reported lower bound

  • Earlier quantum Ramsey approaches search for colourings that establish or test Ramsey-number bounds, whereas this paper studies one fixed graph given by an oracle.The authors report no earlier implementation of the Erdős–Szekeres recursion over implicit sets in the adjacency-query model.Source: §5 · p. 7
  • Constructive Ramsey search connects to weak and structured pigeonhole principles, collision-resistant hashing, PLC, and the online Ramsey game.The online game is described as the deterministic version with an unbounded vertex set.Source: §5 · p. 7
  • The comparison aligns the reported lower-bound model and target with this paper’s: both use N = 2^n vertices and the default target order n/2.The passage says theorem 1.2 meets that target after discarding one vertex.Source: §5 · p. 8
  • Direct substitution of the cited multicollision bounds yields an exponent at most 1/12, not 1−o(1), for the reported quantum lower bound.The text says the theorem 4.5 bound is exactly the multiplicity-two case and that theorem 1.1 rules out an N^(1−o(1)) lower bound at these parameters.Source: §5 · p. 8

6 Discussion and open questions

The discussion leaves open whether quantum and randomized query complexities separate in the worst case and whether the quantum exponent is optimal. It also limits the paper’s claims to query complexity and specified contracts.

6 Discussion and open questions

  • Whether quantum and randomized query complexities separate in the worst case is posed as an open question; on N = 2n vertices, a randomized lower bound of N^(1/2+Ω(1)) would establish such a separation.Source: §6 · p. 8
  • The optimal quantum exponent remains unknown: the available bounds are Ω(N^(1/12)) and O(N log N log log N).At the final levels, constant-size sets are defined by O(log N) adjacency constraints within a universe of size Θ(N), so Grover optimality alone gives no lower bound for this relation.Source: §6 · p. 8
  • The distributional separation and multicolour bound hold under their stated contracts, and the paper claims query bounds—not gate complexity or hardware performance.The small experiments are sanity checks; the query bounds rest on proofs in the appendices.Source: §6 · p. 8

A Proofs of the sampler lemma and the encoding corollary

Capped unknown-solution search produces uniform samples from implicitly defined sets with bounded query cost. The proof also establishes completion guarantees for an estimation-free, size-biased recursion and verifies encoded witnesses.

A Proofs of the sampler lemma and the encoding corollary

  • A capped randomized-iteration search succeeds with probability p0 independent of M and λ, using O(1/λ) membership-predicate calls when marked density is at least λ.The iteration cap is fixed before oracle outcomes, so every block terminates.Source: A Proofs of the sampler lemma and the… · p. 11
  • Accepted search outputs are exactly uniform on the marked set, and independent blocks yield independent accepted outputs conditional on their success indicators.Permutation symmetry gives equal amplitudes to marked states for each iteration count and is preserved by randomizing that count.Source: A Proofs of the sampler lemma and the… · p. 11
  • For a circuit-defined graph, the canonical adjacency oracle uses O(1) circuit queries per graph query, and direct checks verify the returned homogeneous set.The verification checks diagonal entries and both ordered pairs; invalid loops or asymmetry provide local certificates, and its O(K^2) cost is absorbed by the theorem’s bound.Source: A Proofs of the sampler lemma and the… · p. 11

B.1 The size-biased recursion

  • The size-biased recursion completes with probability at least 0.49 per fixed-cap run, then repetition and exact verification raise success to 1−η.Its survival bound at (d, s)=(r, M) is 1/2+1/M; the sampling-cost argument uses O(log(1/η)) independent runs.Source: §B.1 · pp. 11–12
  • For nonempty subsets, capped sampling costs O(√M) membership tests, with O(log(2r)) repetitions reducing a block’s failure probability to O(1/r).At level i, the membership predicate costs O(i+1) edge queries.Source: §B.1 · p. 12

B.2 The scale-aware recursion

The scale-aware recursion allocates estimation and search failures across levels while keeping candidate sets implicit. The companion random-graph analysis uses a matching-based weight argument to bound fully exposed monochromatic sets.

B.2 The scale-aware recursion

  • The proof handles inaccurate completed batches by conditioning on the first bad level and union-bounding across levels, without requiring independence between levels.The batch cap uses O(mi) blocks under the stated schedule.Source: §B.2 · pp. 12–13
  • With probability at least 1−η, the scale-aware algorithm’s searches succeed, its completed estimates are accurate, and its final candidate set is nonempty and yields a verified homogeneous output.The output is directly verified, so every non-⊥ output is valid even outside the good event.Source: §B.2 · pp. 12–13
  • Candidate sets remain implicit: recorded pivots and colours define reversible membership predicates, costing O(i+1) edge queries at level i.A capped search block uses O(2^(i/2)) membership tests, and the algorithm samples from a fixed power-of-two universe.Source: §B.2 · p. 13

C.1 A weight bound for adaptive queries to a random graph

  • For adaptive queries to G(V,1/2), each new queried edge has an independent uniform colour, enabling a matching-number potential and a martingale weight argument.The matching argument removes a critical edge to recurse on a smaller vertex set; the weight has unchanged conditional expectation when an internal edge is queried.Source: §C.1 · p. 14
  • The random-graph weight analysis bounds the expected number of fully exposed monochromatic K-sets after adaptive queries, with the same bound for either colour.The proof canonicalizes vertex labels and extends the query sequence to a fixed length before applying the bound.Source: §C.1 · p. 15

C.2 Proof of the randomized lower bound √

The proof bounds success on G(N,1/2) by controlling fully exposed monochromatic sets and the chance of completing a partially exposed output. This distributional bound implies a query lower bound for algorithms required to succeed on every graph.

C.2 Proof of the randomized lower bound √

  • For at most T adaptive queries, the probability that queried pairs contain a fully exposed monochromatic K-set is at most 1/4 for K≥8.The argument applies the weight bound and Markov’s inequality to deterministic algorithms.Source: §C.2 · pp. 15–16
  • Outside that event, the conditional probability that an output K-set is homogeneous is at most 1/2, giving total success probability at most 5/8.The bound covers transcripts with both colours exposed, exactly one colour exposed, or no internal pairs exposed.Source: §C.2 · p. 16
  • Randomized algorithms also succeed with probability at most 5/8 on G(N,1/2) within T queries, so worst-case success of at least 2/3 requires more than T queries.The conclusion follows by averaging over deterministic algorithms in the randomized algorithm’s distribution.Source: §C.2 · p. 16

C.3 Proof of the random-graph speedup

The proof shows that random graphs have large common neighbourhoods for every relevant vertex set, allowing capped quantum searches to build a verified clique with high probability. It bounds the chance that the graph lacks the required expansion, making the guarantee especially strong for K ≥ 14.

C.3 Proof of the random-graph speedup

  • Expansion requires every j-set W to have at least M2^-j-1 common neighbours among vertices outside W.The common neighbourhood C(W) consists of vertices adjacent to every vertex in W.Source: §C.3 · p. 16
  • For G(M, 1/2), the probability of failing this expansion condition is at most πK, with πK < e^-100 for K ≥ 14.The proof bounds the common-neighbourhood size for each j-set using its binomial distribution and a Chernoff bound.Source: §C.3 · p. 16
  • At level j, the algorithm searches for a vertex adjacent to every vertex already in the clique, using density parameter λj = 2^-j-1.It repeats the capped search O(log(K/η)) times and returns failure if any search fails.Source: §C.3 · pp. 16–17
  • Every accepted output is a K-clique, and on an expanding graph all K searches succeed with probability at least 1 − η.Including the probability of non-expansion, success over G and the algorithm's randomness is at least 1 − η − πK; for K ≥ 14 and η = 1/4, it exceeds 2/3.Source: §C.3 · p. 17

C.4 Proof of the quantum lower bound

The lower bound encodes a collision-finding problem into a graph oracle. A homogeneous set returned by an algorithm on that graph yields a collision, forcing an Ω(N^1/12) quantum query lower bound.

C.4 Proof of the quantum lower bound

  • A hardwired graph A0 on H = 2m vertices has no homogeneous set of order 2m, and the constructed graph Ah uses one query to h per coherent graph query.The construction uses Erdős’s bound R(k, k) > 2^k/2 for k ≥ 3.Source: §C.4 · p. 17
  • Every homogeneous set of Ah of size at least 2m contains two vertices with the same h-value.If its image were a homogeneous set of distinct values in A0, it would contradict A0's lack of a homogeneous set of order 2m.Source: §C.4 · p. 17
  • An algorithm using q queries would find a collision in h with probability at least 2/3 using O(q + n) queries, implying q = Ω(N^1/12).The reduction invokes the Ω(H^1/3) quantum lower bound for collision finding in a uniformly random function [25] [18].Source: §C.4 · p. 17

D.1 A multicolour extension of size-biased survival

The multicolour extension uses a size-biased recursion and a survival bound to find monochromatic cliques with bounded error. Small-instance experiments illustrate the recursion and sampler, while the appendix also discloses the authors’ use of AI tools.

D.1 A multicolour extension of size-biased survival

  • For q colours, the corollary gives a bounded-error algorithm that finds a monochromatic K-clique in any q-edge-coloured complete graph on at least Lq vertices.The passage defines the query bound in terms of r, Br, and Lq, but its displayed expression is incomplete here.Source: §D.1 · p. 18
  • The recursion follows the colour of a uniformly sampled edge, survives r rounds from Lq ≥ 2Br with probability greater than 1/2, and yields a colour appearing at least K − 1 times among q recorded colours.Independent repetition and direct verification amplify success to 1 − η at an additional O(log(1/η)) factor.Source: §D.1 · p. 18

D.2 Small-instance numerical illustrations

  • All 5,000 small-instance trials returned homogeneous triples, with minimum final |S3| values of 13, 13, 6, 2, and 2 across the five graph families.The families were the complete graph, empty graph, balanced complete bipartite graph, one fixed G(16, 1/2) graph, and fresh G(16, 1/2) graphs.Source: §D.2 · pp. 18–19
  • For marked-set sizes 1, 2, 3, 4, 8, and 15, the isolated Grover sampler's marked-item probability ranged from 0.4026746749 to 0.5973253251.Conditional on a marked outcome, the largest deviation from uniformity over marked items was zero to machine precision.Source: §D.2 · p. 19
  • The finite split-tree minimum survival probabilities were approximately 0.5086135566 for nine binary levels from 1,024 candidates and 0.7155732457 for four ternary levels from 128.These exceed the respective analytic lower bounds 513/1024 and 88/127.Source: §D.2 · p. 19

D.3 AI Disclosure

  • The authors used ChatGPT and Claude for literature search, brainstorming, proof checking, drafting, editing, and experiment scripts, and take responsibility for the final paper.They state that they evaluated and revised all AI-assisted material.Source: §D.3 · p. 19
Loading 2609.05812v1…