Dyadic coin precision suffices for QMA threshold centering
ProvedShiQMACenteredGap.exists_dyadic_centeringamplificationcenteringqmaquantum-complexity
For completeness and soundness thresholds in [0,1] separated by inverse gap q, a coin with coinBits(q) fair bits approximates the ideal centering probability within one quarter of the gap.
Preamble
import Definitions.Def_ShiQMACenteredGapScalarCentering import Theorems.Thm_ShiQMACenteredGap_exists_dyadic_coin import Mathlib.Data.Real.Archimedean import Mathlib.Data.Nat.Log set_option autoImplicit false
Formal statement
theorem ShiQMACenteredGap.exists_dyadic_centering {a b : ℝ}
(ha₀ : 0 ≤ a) (ha₁ : a ≤ 1) (hb₀ : 0 ≤ b) (hb₁ : b ≤ 1)
(hab : b ≤ a) (q : Nat) (hgap : (1 : ℝ) ≤ (q : ℝ) * (a - b)) :
∃ j : Nat, j ≤ 2 ^ coinBits q ∧
|(j : ℝ) / (2 : ℝ) ^ coinBits q - centeringCoin a b| ≤ (a - b) / 4 := by
sorrySource