Linearity in the two combining coefficients (lem:qld-global-linear) #
An outcome g of the global measurement is a polynomial on F^{4m}; read at the padded point
u = (x, z, α, β, w) it is a polynomial in (α, β) whose coefficients are polynomials in the other
coordinates. The good outcomes are those of the form g = α g₁(x, z) + β g₂(x, z): linear in
(α, β) with no constant term and no other monomial. This file bounds the weight of the others
(IsLinAB fails) from the ordered-product estimate of lem:qld-global-products for the order
X_a Z_b.
The polynomial side #
LowIndDegPoly.coef g T t is the coefficient vector, in the variables outside T, of the
monomial pattern t on the coordinates T (eval_eq_sum_coef): g(u) = ∑_t u^t_T · coef(u).
Those generic facts are in MIPRE/Background/LIDT/Coefficients.lean.
With T = {aIdx, bIdx} the patterns are pairs (i, j), and pAB g u₀ is the bivariate
polynomial (α, β) ↦ g(setAB u₀ α β) as a coefficient vector on Fin 2 (eval_pAB). If g is
not of the good form, some coefficient G_{i₀ j₀} with (i₀, j₀) ∉ {(1, 0), (0, 1)} is a nonzero
polynomial, so by Schwartz--Zippel it vanishes at a uniform u₀ with probability at most
4md/q (sum_uniform_eval_eq_zero_le); where it does not vanish, pAB g u₀ differs from every
linear form α a + β b (pAB_ne_linAB), so they agree at a uniform (α, β) with probability at
most 2d/q (sum_agree_two_le).
The operator side #
For β ≠ 0 the fibre {αa + βb = c} has one b per a, so
‖(G_g ⊗ ∑_{fibre} X_a Z_b) Φ‖² = ∑_{fibre} ‖(G_g ⊗ X_a Z_b) Φ‖² (Pythagoras, the X_a being
orthogonal projectors), and the weights W_g(a, b) = ‖(G_g ⊗ X_a Z_b) Φ‖² do not depend on
(α, β) and sum to ⟨G_g⟩. Averaging over (α, β) and then over the other coordinates
(sum_uniform_setAB reads the uniform padded point as a uniform base point with a fresh uniform
pair), an outcome that is not of the good form has E_u ‖(G_g ⊗ B_u(g(u))) Φ‖² ≤ η ⟨G_g⟩ with
η = (1 + 2d + 4md)/q (sum_uniform_snorm_sq_ordComb_le_of_not_isLinAB). On the other hand
⟨G_g⟩ ≤ 2 ‖(G_g ⊗ B_u) Φ‖² + 2 ‖(G_g ⊗ (1 - B_u)) Φ‖² for every u, and the second terms are
what the product estimate bounds by Δ in total; hence
(1 - 2η) · (weight of the bad outcomes) ≤ 2Δ (sum_bad_linear_mass_le). This is the linear
bound the paper's cnote at eq:qld-g-prime-bound describes, rather than the displayed √Δ.
Stated in a bipartite model #
Stated in a bipartite model (Phase 5 of planning/mipco-track.md). The state is that of a
bipartite model K (the model in which the low individual degree test is applied, padModel,
or any other); the outcome G_g is a projection of the first player's algebra and the families
X, Z projective measurements of the second player's, so G_g ⊗ D is
K.πA (G.op g) * K.πB D and its squared state norm K.snorm (…) ^ 2. Pythagoras over the
orthogonal X_a is the state model's orthogonality lemma
(StateModel.snorm_sq_sum_orthogonal', on the images K.πB (X_a)), and the weight of an
outcome is the Born probability K.bornProb (G.op g) 1. The polynomial half is unchanged.
The polynomial in the two combining coefficients #
The two combining coordinates.
Equations
Instances For
The outcome read at (α, β), with the other coordinates fixed at those of u₀: a
polynomial in two variables, as a coefficient vector.
Equations
- MIPRE.QLD.pAB g u₀ t2 = (g.coef MIPRE.QLD.abSet (MIPRE.QLD.patAB (t2 0) (t2 1))).eval u₀
Instances For
The coefficient vectors on abSet do not read α, β.
Linear forms in the two combining coefficients #
The linear form α a + β b, as a coefficient vector on two variables.
Equations
- MIPRE.QLD.linAB hd a b t2 = if t2 = MIPRE.QLD.e10 hd then a else if t2 = MIPRE.QLD.e01 hd then b else 0
Instances For
Schwartz--Zippel on two variables: two different coefficient vectors agree at a uniform
pair with probability at most 2d/q.
The linear outcomes and the two probability bounds #
Linear in (α, β): every monomial of g has exponents (1, 0) or (0, 1) on the two
combining coordinates, so g = α g₁ + β g₂ with g₁, g₂ not reading α, β.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- One or more equations did not get rendered due to their size.
An outcome that is not linear in (α, β) has a nonzero coefficient vector at a non-linear
pattern.
Where a non-linear coefficient does not vanish, the outcome read at (α, β) differs from every
linear form.
The bad base points: a nonzero coefficient vector vanishes at a uniform padded point with
probability at most 4md/q.
The operator side: the fibre weights #
The pairs with β = 0 number q.
The weights sum to the outcome's mass: ∑_{a,b} ‖(S ⊗ X_a Z_b) Φ‖² = ⟨S ⊗ 1⟩.
Pythagoras on the fibre: for β ≠ 0 the fibre has one b per a, and the X_a are
orthogonal projections.
The fibre weights over β ≠ 0, exchanged: each pair (a, b) is counted once for every
(α, β) that puts it on the sampled fibre {αa + βb = v(α, β)}.
The combination is a contraction: ‖(S ⊗ B) Φ‖² ≤ ⟨S ⊗ 1⟩ for every (α, β, c).
Reading a padded point as a base point and a fresh combining pair #
The map (u₀, α, β) ↦ setAB u₀ α β is q²-to-one.
The uniform padded point is a uniform base point with a fresh uniform combining pair.
The two averages and the assembly #
A good base point: where a non-linear coefficient of g does not vanish, the average over
the combining pair (α, β) of ‖(S ⊗ B_{α,β}(g(setAB u₀ α β))) Φ‖² is at most
(1 + 2d)/q · ⟨S ⊗ 1⟩: the pairs with β = 0 contribute 1/q, and for β ≠ 0 each weight
W(a, b) is counted with the probability, at most 2d/q, that (α, β) puts (a, b) on the
sampled fibre.
A bad outcome carries little of its own weight through B_u: if g is not linear in
(α, β), then E_u ‖(S ⊗ B_u(g(u))) Φ‖² ≤ (1 + 2d + 4md)/q · ⟨S ⊗ 1⟩, the 4md/q being the
probability that the witnessing non-linear coefficient vanishes at the base point.
lem:qld-global-linear, abstract form. If the global measurement G satisfies the
X_a Z_b products estimate ∑_g E_u ‖(G_g ⊗ (1 - B_u(g(u)))) Φ‖² ≤ Δ, then the outcomes that
are not linear in the combining coordinates (α, β) have total weight
W ≤ 2Δ / (1 - 2η), η = (1 + 2d + 4md)/q: for each of them
⟨G_g⟩ ≤ 2 ‖(G_g ⊗ B_u) Φ‖² + 2 ‖(G_g ⊗ (1 - B_u)) Φ‖², and the first term averages to at most
2η ⟨G_g⟩.