TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Classical randomized Simon search needs exponential queries

Statement

Let $n \geq 8$ , $N = 2^{n}$ , and $m \geq n - 1$ . Consider algorithms that know $n, m$ and receive only classical query access to the promised oracle $f$ ; no truth table, description, or other information depending on $f$ is supplied. Every randomized algorithm in this model that outputs the unique nonzero Simon mask with success probability at least $2 / 3$ on every promised oracle must use more than $⌊ 2^{n / 2} / 4 ⌋$ queries in the worst case. Consequently the classical randomized query complexity in this oracle-only model is $Ω (2^{n / 2})$ . This is a query lower bound; no classical bit-time lower bound is asserted.

Facts & Assumptions

Given: The random Simon-oracle distribution, a randomized classical query algorithm with worst-case query bound $q$ , $n \geq 8$ , and output width $m \geq n - 1$ .

[F1]

Random Simon-oracle distribution for a classical lower bound: $s$ is uniform among nonzero masks and coset labels are assigned uniformly by an injection into the $m$ -bit outputs.

[F2]

Classical query algorithm: fixing the finite random tape gives a deterministic adaptive query procedure. Under the oracle-only convention in the Statement, its address choices may depend on $n, m$ and earlier replies, but receive no additional $f$ -dependent input.

[F3]

Finite probability spaces, outcome weights, events, and event probabilities: all hidden masks, label injections, and finite random tapes are sampled in finite probability spaces.

Proof

1.1givenassume-contraalgebra

Assume, for contradiction, that $q \leq ⌊ \sqrt{N} / 4 ⌋$ . Put $S = N - 1$ and $B = (\binom{q}{2})$ .

2.1givenF2F3step 1.1algebra

Fix one finite random tape, making the algorithm deterministic. Repeated addresses can be answered from the earlier reply and removed without changing the output, so the resulting at most $q$ queries are distinct.

2.2givenstep 1.1algebra

The assumption in step 1.1 gives $B \leq q^{2} / 2 \leq N / 32$ . Hence $S - B \geq 31 N / 32 - 1 > 0$ , since $N = 2^{n} \geq 256$ .

3.1givenF1F2step 2.1step 2.2algebra

Consider a collision-free transcript of $t \leq q$ queries. A mask is inconsistent with it only if it is the XOR difference of a pair of queried addresses, so at most $(\binom{t}{2}) \leq B$ masks are excluded and at least $S - B$ remain. For each remaining $s$ , the queried addresses lie in distinct $s$ -cosets. Write $(L)_{t} = L (L - 1) \dots (L - t + 1)$ , where $L = 2^{m}$ and $C = 2^{n - 1}$ . For a specified ordered list of $t$ distinct replies, the number of injections extending those assignments is $(L - t)_{C - t}$ out of $(L)_{C}$ total injections, giving likelihood $1 / (L)_{t}$ , independent of $s$ . Because the deterministic query addresses are functions of earlier replies, the transcript has the same likelihood for every consistent mask. The posterior on those masks is therefore uniform.

4.1step 3.1algebra

At the $j$ th fresh query, a collision with a previous address $x_{i}$ requires $s = x_{j} \oplus x_{i}$ . There are at most $j - 1$ candidate masks, and after any collision-free transcript at least $S - B$ masks remain equally likely by step 3.1. Thus the probability that the first collision occurs at query $j$ is at most $(j - 1) / (S - B)$ . Summing over $j = 2, \dots, q$ bounds the total collision probability by $\sum_{j = 2}^{q} (j - 1) / (S - B) = B / (S - B)$ .

5.1F1step 3.1step 4.1algebra

On a collision-free transcript, the deterministic final guess is correct with probability at most $1 / (S - B)$ , since at least that many masks remain equally likely. On transcripts with a collision, success is at most one. Therefore average success under [F1] is at most $B / (S - B) + 1 / (S - B) = (B + 1) / (S - B)$ .

6.1givenF3step 2.2step 5.1algebra

By steps 1.1 and 2.2, with $S - B > 0$ , $(B + 1) / (S - B) \leq (N / 32 + 1) / (31 N / 32 - 1) < 2 / 3$ . The strict inequality is equivalent to $5 < 59 N / 32$ , which holds because $N \geq 256$ . Thus every fixed random tape has average success strictly below $2 / 3$ under the finite oracle distribution.

7.1givenF1F3step 6.1discharge-contradiction∎

Averaging over the algorithm's finite random tapes keeps its average success below $2 / 3$ . But success at least $2 / 3$ on every promised function implies average success at least $2 / 3$ under [F1], since every function in that distribution is promised. This contradiction proves $q > ⌊ \sqrt{N} / 4 ⌋$ and hence the stated $Ω (2^{n / 2})$ lower bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415v6, 2026) (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)