TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

OR has a square-root approximate-degree lower bound and corresponding query lower bounds

Statement

For $N \geq 1$ , define ${O R}_{N} (x) = 0$ at $x = 0^{N}$ and $1$ at every other Boolean vector. For $0 \leq ϵ < 1 / 2$ and $d = {\overset{}{\deg}}_{ϵ} ({O R}_{N}; {0, 1}^{N})$ , $d^{2} \geq \frac{1 - 2 ϵ}{2} N .$ Consequently every local bit-query algorithm computing OR with error at most $ϵ$ has at least $⌈ d / 2 ⌉$ queries, and $Q_{ϵ}^{b i t} ({O R}_{N}; {0, 1}^{N}) \geq ⌈ \frac{1}{2} \sqrt{\frac{1 - 2 ϵ}{2} N} ⌉ .$

Facts & Assumptions

Given: An integer $N \geq 1$ , an error $0 \leq ϵ < 1 / 2$ , and the full-cube OR function.

[F1]

Acceptance polynomials and approximate degree on Boolean domains: approximate degree is attained by a polynomial that approximates on the promise domain.

[F2]

Symmetrizing a Boolean-cube polynomial gives a Hamming-weight polynomial: symmetrization preserves approximation and yields a polynomial in Hamming weight with no larger degree.

[F3]

Finite-grid Markov derivative inequality: if a degree-at-most- $d$ polynomial has values in $[0, 1]$ on $0, 1, \dots, N$ , then $D : = \max_{[0, N]} ∣ q^{'} ∣ \leq (d^{2} / N) h$ , where $h$ is its continuous range height; with Bounded integer-grid values control excursions by the derivative, $h \leq 1 + D$ .

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : for a polynomial on $[0, 1]$ , some derivative value equals the difference of endpoint values.

[F5]

A T-query bit algorithm has an acceptance polynomial of degree at most 2T: for the local oracle-only model, $Q_{ϵ}^{b i t} (f; D) \geq ⌈ {\overset{}{\deg}}_{ϵ} (f; D) / 2 ⌉$ .

[F6]

The reals form a totally ordered field: $R$ has field arithmetic compatible with a total order, so positive denominators can be multiplied or divided in inequalities.

Proof

1.1givenF1F2constructalgebra

Choose an $ϵ$ -approximating polynomial of degree at most $d$ from [F1]. Apply [F2] to obtain a univariate polynomial $q (t)$ of degree at most $d$ whose values at integer $k$ approximate ${O R}_{N}$ on the weight- $k$ layer. Define $r (t) : = (q (t) + ϵ) / (1 + 2 ϵ)$ and $c : = (1 - 2 ϵ) / (1 + 2 ϵ)$ . At $k = 0$ , $q (0) \in [- ϵ, ϵ]$ , so $r (0) \in [0, 2 ϵ / (1 + 2 ϵ)]$ ; at each $1 \leq k \leq N$ , $q (k) \in [1 - ϵ, 1 + ϵ]$ , so $r (k) \in [1 / (1 + 2 ϵ), 1]$ . Thus all grid values lie in $[0, 1]$ and $r (1) - r (0) \geq c > 0$ .

2.1step 1.1F3F4F6algebra

Let $h = \max_{[0, N]} r - \min_{[0, N]} r$ and $D = \max_{[0, N]} ∣ r^{'} ∣$ . By [F4] on $[0, 1]$ , $D \geq r (1) - r (0) \geq c$ . By [F3], $D \leq a h$ with $a : = d^{2} / N$ , and $h \leq 1 + D$ . If $a \geq 1$ , then $a \geq c / (1 + c)$ since $0 < c \leq 1$ . If $a < 1$ , then $D \leq a (1 + D)$ , so $(1 - a) D \leq a$ and $D \leq a / (1 - a)$ . Combining $c \leq D \leq a / (1 - a)$ gives $a \geq c / (1 + c)$ . In both cases $a \geq c / (1 + c) = (1 - 2 ϵ) / 2$ , proving $d^{2} \geq (1 - 2 ϵ) N / 2$ by ordered-field algebra [F6].

3.1step 2.1F5algebra∎

The local query lower bound follows from [F5]. Since $d \geq \sqrt{(1 - 2 ϵ) N / 2}$ by step 2.1, monotonicity of the ceiling gives the displayed explicit query estimate.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

34 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

Andrew M. Childs, Lecture Notes on Quantum Algorithms (2025), §21.6 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415), §11.2 (standard reference, not scraped)
N. L. Carothers, A Short Course on Approximation Theory (1998), Chapter 5 (standard reference, not scraped)