(131), p. 34 — if 2ℓ + 1 < d⊥ then ⟨s^(m,ℓ)⟩_opt/m = ρ + √(ρ(1 − ρ)) λ_max^(m,ℓ,d)/m
ProvedDQI.Semicircle.eq_131decoded-quantum-interferometryeigenvaluesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be prime, with , and for all with ; put and . If , then the optimal expected number of satisfied constraints over normalized DQI states with satisfies
where is the largest eigenvalue of .
This is the exact finite-size form of Theorem 4.1: the asymptotics reduce to those of .
Preamble
import Mathlib import Definitions.Def_DQI_Semicircle_Setting
Formal statement
namespace DQI.Semicircle
/-- (131), p. 34: `⟨s^{(m,ℓ)}⟩_opt / m = ρ + √(ρ(1−ρ)) λ_max^{(m,ℓ,d)} / m`, `ρ = r/p`. -/
theorem eq_131 (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) (ℓ : ℕ) (hdist : DistGt B (2 * ℓ + 1)) :
optSat B F ℓ / m =
(r : ℝ) / p + Real.sqrt ((r : ℝ) / p * (1 - (r : ℝ) / p)) * lamMax (Atri m ℓ (dparOf p r)) / m := by sorry
end DQI.Semicircle
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, p. 34, §9.4, (131)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.