Theorem 7.3 — linear quantum membership-query lower bound
OpenQVolKLS.Supplement.theorem_7_3There is a universal constant such that, in every dimension , every unrestricted finite quantum membership-query algorithm which estimates the volume of every promised origin-centered ellipsoid to relative error with probability at least makes at least membership queries. The promise is
Thus constant-relative-error volume estimation has worst-case quantum query complexity even on well-bounded ellipsoids, with arbitrary finite query precision and unrestricted computation between queries.
Formalization Note The algorithm is fixed before and may use arbitrary workspace, unitaries, deferred intermediate measurements, adaptivity, finitely many coordinate formats, and arbitrary real output decoding. Natural-number division is exactly .
Differences from the source:
- generalization: the printed conclusion is a worst-case lower bound → Lean states the explicit bound established in the proof on p.58; reason: this fixes the hidden lower-bound constant while directly implying the printed claim
- encoding: the source allows unrestricted computation and arbitrary finite query precision without a formal circuit syntax → Lean uses arbitrary input-independent unitaries, arbitrary workspace and output decoding, finitely many dyadic formats, and deferred measurement; reason: standard exact coherent-query encoding with the same algorithm class
import Definitions.Def_QVolKLS_Supplement_UnrestrictedMemAlgorithm set_option autoImplicit false
namespace QVolKLS.Supplement
open MeasureTheory
/-- R. Zhang, arXiv:2610.04987 (held version, sha256 eee7a45e…), **Theorem 7.3
(Linear quantum query lower bound)**, p.57 (proof through p.58).
There is one universal outer-radius constant `C > 0`. In every dimension `d ≥ 2`, any finite
quantum membership-query algorithm which, for every promised origin-centered ellipsoid, estimates
its volume to relative error `1/4` with probability at least `2/3`, uses at least `⌊d/2⌋` queries.
This is the explicit lower bound established by the proof and implies the printed `Ω(d)` claim.
**Formalization Note.** Algorithms may use any finite set of finite-precision coordinate formats,
arbitrary input-independent unitaries, arbitrary workspace, deferred intermediate measurements and
adaptive control, and arbitrary real output decoding. The body enters only through exact coherent
membership oracles, boundary included. The circuit is fixed before the promised body, so `queries`
is its worst-case query count over those bodies. The explicit `d / 2` is natural-number division,
equal to `⌊d/2⌋`, exactly as proved on p.58.
-/
theorem theorem_7_3 :
∃ C : ℝ, 0 < C ∧
∀ (d : ℕ), 2 ≤ d → ∀ A : UnrestrictedMemAlgorithm d,
(∀ K : Set (Euc d), OriginEllipsoidPromise C K →
2 / 3 ≤ A.outProb K (volumeRelativeError K (1 / 4))) →
d / 2 ≤ A.queries := by sorry
end QVolKLS.Supplement