nae_p_schedule
The least inductive relation on triples (d, θ, q), where d is a natural number and θ and q are real numbers, contains (0, π, 1) and is closed under: composition (d, θ, q) ↦ (d+1, arccos(1−(4/9)(1−cos θ)²), 2q); amplification (d, θ, q) ↦ (d, arccos(cos(cθ)), cq) for any positive natural number c, coerced to a real number; and relaxation (d, θ, q) ↦ (d, θ′, q) for any real θ′ with 0 ≤ θ′ ≤ θ. Here q is explicitly a real-valued scheduled query budget, not a lower bound on arbitrary quantum circuits.
Statement
inductive nae_p_schedule : ℕ → ℝ → ℝ → Prop | initial : nae_p_schedule 0 Real.pi 1 | compose {d : ℕ} {θ q : ℝ} : nae_p_schedule d θ q → nae_p_schedule (d + 1) (Real.arccos (1 - (4 / 9 : ℝ) * (1 - Real.cos θ) ^ 2)) (2 * q) | amplify {d : ℕ} {θ q : ℝ} (c : ℕ) : 0 < c → nae_p_schedule d θ q → nae_p_schedule d (Real.arccos (Real.cos ((c : ℝ) * θ))) ((c : ℝ) * q) | relax {d : ℕ} {θ q θ' : ℝ} : 0 ≤ θ' → θ' ≤ θ → nae_p_schedule d θ q → nae_p_schedule d θ' q
- Defined in
- arXiv:1211.0721, Section 3.3, Lemmas 1–3: abstract reachability encoding of their p-computation rules
- Verified
- 13 Nov 2026
- Axioms
- none listed
- Used by 6
- nae_p_schedule_lower_boundEvery triple (d, θ, q) reachable by the specified p-computation rule schedule with θ ≥ π/2 has scheduled query count q at least…
- nae_p_schedule_potential_strongFor every triple (d, θ, q) in nae_p_schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(5/12)^d.
- nae_p_schedule_no_uniform_adversary_rateFor any two real sequences θ and q, if for every natural d the triple (d, θ(d), q(d)) is in nae_p_schedule and θ(d) ≥ π/2, then no real C…
- nae_p_schedule_potentialFor every triple (d, θ, q) reachable by the specified p-computation rule schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(15/32)^d.
- nae_p_schedule_not_at_adversary_rateFor every real C there is a natural d such that every real θ and q satisfying nae_p_schedule d θ q and θ ≥ π/2 has q > C(3/√2)^d.
- nae_p_schedule_lower_bound_strongFor every natural number d and real numbers θ and q, if nae_p_schedule d θ q holds and θ ≥ π/2, then q ≥ (1/2)(12/5)^d. Here…
Read back from the Lean
An inductive predicate nae_p_schedule : ℕ → ℝ → ℝ → Prop inductively generated by four constructors:
1. initial: nae_p_schedule 0 Real.pi 1.
2. compose: for all d : ℕ and θ, q : ℝ, if nae_p_schedule d θ q holds, then nae_p_schedule (d + 1) (Real.arccos (1 - (4 / 9 : ℝ) * (1 - Real.cos θ) ^ 2)) (2 * q) holds.
3. amplify: for all d : ℕ, θ, q : ℝ, and c : ℕ, if 0 < c and nae_p_schedule d θ q holds, then nae_p_schedule d (Real.arccos (Real.cos ((c : ℝ) * θ))) ((c : ℝ) * q) holds.
4. relax: for all d : ℕ and θ, q, θ' : ℝ, if 0 ≤ θ', θ' ≤ θ, and nae_p_schedule d θ q holds, then nae_p_schedule d θ' q holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
inductive nae_p_schedule : ℕ → ℝ → ℝ → Prop | initial : nae_p_schedule 0 Real.pi 1 | compose {d : ℕ} {θ q : ℝ} : nae_p_schedule d θ q → nae_p_schedule (d + 1) (Real.arccos (1 - (4 / 9 : ℝ) * (1 - Real.cos θ) ^ 2)) (2 * q) | amplify {d : ℕ} {θ q : ℝ} (c : ℕ) : 0 < c → nae_p_schedule d θ q → nae_p_schedule d (Real.arccos (Real.cos ((c : ℝ) * θ))) ((c : ℝ) * q) | relax {d : ℕ} {θ q θ' : ℝ} : 0 ≤ θ' → θ' ≤ θ → nae_p_schedule d θ q → nae_p_schedule d θ' q