Theorem 5.21 — one-query growth: , also for the controlled query
OpenTightQLB.Supplement.theorem_5_21haar-random-stateslinear-cross-entropyp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-query-complexity
Let with , let be a space containing the query register , and let the canonical oracle act as pointwise in . For every and every ,
and the same holds for the controlled query . Here is the progress measure and .
The paper states the theorem with "an absolute constant " and its proof gives . This is the growth half of Theorem 5.6: each query raises the progress measure by .
Formalization Note For the plain query ; for the controlled query and the operator is the base mission's queryOn. is an arbitrary finite type.
Differences from the source:
- generalization: "There is an absolute constant c0" → c0 = 54; reason: the proof gives c0 = 54 (p. 44, PDF p. 47), and the explicit value implies the existential statement
- encoding: a space V containing Q, "V = W ⊗ Q after reordering" → Q × W for the plain query and (C × Q) × W for the controlled one, W any finite type; reason: same spaces up to reordering
- encoding: F ∈ P_{≤d}(V), a polynomial of degree at most d in α, ᾱ, unit vector in L²(Haar) → IsPoly d F (a polynomial representative on unit vectors) and E_ϕ‖F(ϕ)‖² = 1, V the coordinate space of a finite type; reason: same objects
- encoding: λ(F) = (Σ_k k‖P_k F‖²)^{1/2} with P_k the projection onto the level-k blocks → progress F, with ‖P_k F‖ the supremum of |⟨G, F⟩| over unit-ball elements G of the span of the level-k blocks and a tsum over k; reason: this is the norm of the orthogonal projection onto the closed span, and the blocks are pairwise orthogonal, so it agrees with the projection inside P_{≤d}(V)
- encoding: Dir(a), density ∝ Π p_i^{a_i−1} with respect to the uniform measure on the simplex → weight Π p_i^{a_i−1} against the (N−1)-dimensional Hausdorff measure restricted to the simplex, divided by its total weight; reason: the normalization of the uniform measure cancels
- encoding: a Haar-random unit vector of C^N → the published haarTargetLaw (the standard Gaussian on C^N normalized); reason: the same law on unit vectors
Preamble
import Mathlib import Definitions.Def_TightQLB_Supplement_Level open QAlgorithms set_option autoImplicit false
Formal statement
namespace TightQLB.Supplement
/-- **Theorem 5.21 (One-query growth)**, p.43 (PDF p.46), with the constant of its proof.
Bhateja, Esmaili, Mantri, *Tight Query Lower Bounds for Quantum Sampling, with an Application to
Certified Randomness*, arXiv:2610.06721 (version of sha256 00a999f1…).
"There is an absolute constant `c₀` such that for all `F ∈ P_{≤d}(V)`,
`λ(O_ϕ F) ≤ λ(F) + c₀ √((d + 1)/N) ‖F‖`, and the same holds for the controlled query `O^c_ϕ`."
"The proof gives `c₀ = 54`" (p.44, PDF p.47).
**Formalization Note.**
* Stated with `c₀ = 54`, which implies the existential form.
* Plain query: `V = Q ⊗ W` with `Q = C|⊥⟩ ⊕ C^N` (`Option (Qubits n)`) and an arbitrary finite `W`
("Let `W` be the space of all registers other than the query register `Q`, so that `V = W ⊗ Q`
after reordering", p.41); `O_ϕ` acts as `O_ϕ ⊗ I_W` pointwise in `ϕ`.
* Controlled query: `V = (C × Q) × W`, and `O^c_ϕ` is the published `TightQLB.queryOn (O_ϕ) W`.
* `λ` is `progress`, `‖F‖ = (E_ϕ‖F(ϕ)‖²)^{1/2}` is `hnorm`; `n ≥ 1` (§3.1). -/
theorem theorem_5_21 {n : ℕ} (hn : 1 ≤ n) {W : Type} [Fintype W] [DecidableEq W] (d : ℕ) :
(∀ F : Fn n (Option (Qubits n) × W), IsPoly d F →
progress (pointwise (fun ϕ => Matrix.kronecker (canonOracle ϕ) (1 : Matrix W W ℂ)) F) ≤
progress F + c0 * Real.sqrt (((d : ℝ) + 1) / (2 : ℝ) ^ n) * hnorm F) ∧
∀ F : Fn n (Reg (Option (Qubits n)) W), IsPoly d F →
progress (pointwise (fun ϕ => queryOn (canonOracle ϕ) W) F) ≤
progress F + c0 * Real.sqrt (((d : ℝ) + 1) / (2 : ℝ) ^ n) * hnorm F := by sorry
end TightQLB.Supplement
Source
Bhateja, Esmaili, Mantri, Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness, arXiv:2610.06721 (version of sha256 00a999f1…), Theorem 5.21, p. 43 (PDF p. 46); c0 = 54, p. 44 (PDF p. 47)