Lemma 9.2, pp. 26–27 — if 2ℓ + 1 < d⊥ then ⟨s^(m,ℓ)⟩ = mr/p + (√(r(p − r))/p) wᵀA^(m,ℓ,d)w
ProvedDQI.Semicircle.lemma_9_2Let be prime, , , and for all with . Let and , and consider the DQI state with amplitudes
normalized so that . If , the expected number of satisfied constraints upon measuring this state is
where is the tridiagonal matrix with diagonal and off-diagonal .
This reduces the optimization over polynomials to a Rayleigh quotient of an explicit matrix.
Formalization Note The page writes the decomposition as ; with this normalization the variables must be the rescaled of (44)–(46), §8.2.1 (with the the formula is false for ), and the statement uses the . The polynomial enters only through , so the statement quantifies over ; every such state is for a degree- polynomial and conversely (Lemma A.1).
import Mathlib import Definitions.Def_DQI_Semicircle_Setting
namespace DQI.Semicircle
/-- Lemma 9.2, pp. 26–27, (69)–(70), with the decomposition in the `g_i` of (44)–(46). -/
theorem lemma_9_2 (p : ℕ) [Fact p.Prime] (m n : ℕ) (B : Matrix (Fin m) (Fin n) (ZMod p))
(F : Fin m → Finset (ZMod p)) (r : ℕ) (hF : ∀ i, (F i).card = r) (hr : 1 ≤ r) (hrp : r < p)
(hnm : n < m) (hn : 0 < n) (ℓ : ℕ) (w : Fin (ℓ + 1) → ℝ)
(hnorm : ∑ x, ampl B F ℓ w x ^ 2 = 1) (hdist : DistGt B (2 * ℓ + 1)) :
expSat B F (ampl B F ℓ w) =
(m : ℝ) * r / p + Real.sqrt (r * ((p : ℝ) - r)) / p * (w ⬝ᵥ (Atri m ℓ (dparOf p r)).mulVec w) := by sorry
end DQI.Semicircle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.