nae_p_schedule_lower_bound_strong
For 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 nae_p_schedule is the least relation containing (0, π, 1) and closed under: composition to (d+1, arccos(1−(4/9)(1−cos θ)²), 2q); amplification to (d, arccos(cos(cθ)), cq) for positive natural c; and relaxation to (d, θ′, q) for real 0 ≤ θ′ ≤ θ. The quantity q is the budget prescribed by these operations, not a lower bound on arbitrary quantum circuits.
Statement
theorem nae_p_schedule_lower_bound_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q)
(hθ : Real.pi / 2 ≤ θ) :
(1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d ≤ q- Related work
- arXiv:1211.0721, Section 3.3, p-computation rule analysis
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nae_p_scheduleThe least inductive relation on triples (d, θ, q), where d is a natural number and θ and q are real numbers, contains (0, π, 1) and is…
- nae_p_schedule_potential_strongFor every triple (d, θ, q) in nae_p_schedule, 0 ≤ θ ≤ π, q ≥ 0, and θ ≤ πq(5/12)^d.
- nae_p_rule_strong_base_exceeds_adversary_baseThe explicit base 12/5 is strictly greater than 3/√2.
- Used by 1
- 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.
Read back from the Lean
For any natural number d and any real numbers θ and q, if nae_p_schedule d θ q holds and θ ≥ π / 2, then (1 / 2) * (12 / 5) ^ d ≤ q.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The schedule potential invariant provides an upper bound on θ in terms of the budget q, namely θ ≤ π * q * (5 / 12)^d. Combining this with the hypothesis θ ≥ π / 2 yields π / 2 ≤ π * q * (5 / 12)^d. Multiplying both sides by (12 / 5)^d cancels the factor (5 / 12)^d, resulting in (π / 2) * (12 / 5)^d ≤ π * q. Dividing through by π > 0 concludes that q ≥ (1 / 2) * (12 / 5)^d.
(π / 2) * (12 / 5)^d ≤ (π * q * (5 / 12)^d) * (12 / 5)^d
The schedule invariant (nae_p_schedule_potential_strong) bounds the angle by θ ≤ π * q * (5 / 12)^d. Combining this with the assumption π / 2 ≤ θ (hθ) by transitivity (le_trans) yields π / 2 ≤ π * q * (5 / 12)^d. Since (12 / 5)^d > 0 (by positivity), multiplying both sides by this positive factor preserves the inequality (mul_le_mul_of_nonneg_right).
uses
nae_p_schedule_potential_strong,le_trans,mul_le_mul_of_nonneg_righthave hp := (nae_p_schedule_potential_strong h).2.2.2 have hrpos : 0 < (12 / 5 : ℝ) ^ d := by positivity have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le
(5 / 12)^d * (12 / 5)^d = 1
Distributing the exponent across multiplication (mul_pow) rewrites the product as ((5 / 12) * (12 / 5))^d. The base simplifies to 1, and 1^d = 1.
uses
mul_powhave hcancel : (5 / 12 : ℝ) ^ d * (12 / 5 : ℝ) ^ d = 1 := by rw [← mul_pow] norm_num
(π / 2) * (12 / 5)^d ≤ π * q
Regrouping factors on the right-hand side using associativity (mul_assoc) yields π * q * ((5 / 12)^d * (12 / 5)^d), which simplifies to π * q * 1 and thus π * q (mul_one). Replacing the right-hand side in the earlier inequality gives (π / 2) * (12 / 5)^d ≤ π * q.
uses
mul_assoc,mul_onehave hprod : (Real.pi * q * (5 / 12 : ℝ) ^ d) * (12 / 5 : ℝ) ^ d = Real.pi * q := by rw [mul_assoc, hcancel, mul_one] rw [hprod] at hmul
(1 / 2) * (12 / 5)^d ≤ q
Since π > 0 (Real.pi_pos), dividing both sides of (π / 2) * (12 / 5)^d ≤ π * q by π yields the desired lower bound (1 / 2) * (12 / 5)^d ≤ q.
uses
Real.pi_posnlinarith [Real.pi_pos]
nae_p_schedule_potential_strong- for any valid schedule (d, θ, q), the bound θ ≤ π * q * (5 / 12)^d holds along with 0 ≤ θ ≤ π and 0 ≤ q
mul_le_mul_of_nonneg_right- multiplying both sides of an inequality by a non-negative value preserves the inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * a
le_trans- the transitive relation for inequalities: if a ≤ b and b ≤ c, then a ≤ c
mul_pow- a power of a product is the product of the powers: (a * b)^n = a^n * b^n
mul_assoc- multiplication is associative: (a * b) * c = a * (b * c)
mul_one- multiplying any value by 1 leaves it unchanged: a * 1 = a
Real.pi_pos- the constant π is strictly positive: 0 < π
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem nae_p_schedule_lower_bound_strong {d : ℕ} {θ q : ℝ} (h : nae_p_schedule d θ q) (hθ : Real.pi / 2 ≤ θ) : (1 / 2 : ℝ) * (12 / 5 : ℝ) ^ d ≤ q := by have hp := (nae_p_schedule_potential_strong h).2.2.2 have hrpos : 0 < (12 / 5 : ℝ) ^ d := by positivity have hmul := mul_le_mul_of_nonneg_right (le_trans hθ hp) hrpos.le have hcancel : (5 / 12 : ℝ) ^ d * (12 / 5 : ℝ) ^ d = 1 := by rw [← mul_pow] norm_num have hprod : (Real.pi * q * (5 / 12 : ℝ) ^ d) * (12 / 5 : ℝ) ^ d = Real.pi * q := by rw [mul_assoc, hcancel, mul_one] rw [hprod] at hmul nlinarith [Real.pi_pos]