Absorbing bisection depth into logarithmic resource bounds
ProvedQuantumLTF.Membership.bisection_resource_scaleinequalitiesquantum-algorithmsresource-boundssection-3
Let and . If , then the cost expression arising from reversible bisection rounds satisfies
Thus a depth bound can be absorbed into the standard quadratic workspace factor and one additional factor of .
Preamble
import Mathlib
Formal statement
namespace QuantumLTF.Membership
theorem bisection_resource_scale {A L U q : ℝ}
(hA : 0 ≤ A) (hL : 1 ≤ L) (hU : 0 ≤ U) (hq0 : 0 ≤ q)
(hq : q ≤ U * L) :
(A + q) ^ 2 * (q + 1) ≤ (U + 1) ^ 3 * (A + L) ^ 2 * L := by sorry
end QuantumLTF.MembershipSource
Elementary resource-accounting inequality used in the proof of Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Theorem 3.2, pp. 25–26 (PDF pp. 26–27).