The low-degree sandwich #
Blueprint lem:ar-sandwich-support, the paper's lem:ld-sandwich (NW19's Fact 4.34 with the
measurements depending on an index). Alice holds a projective measurement A^x whose outcome is a
tuple (g_1, ..., g_k) of functions; Bob holds, for each coordinate, a projective measurement
G^{i,x} of that coordinate alone. If each coordinate of A, evaluated at a random point, agrees
with the evaluated G^{i,x}, then the whole tuple, evaluated, agrees with Bob's sandwich
C^x_{g_1, ..., g_k} = G^{k,x}_{g_k} ⋯ G^{2,x}_{g_2} G^{1,x}_{g_1} G^{2,x}_{g_2} ⋯ G^{k,x}_{g_k},
which is a POVM because each layer is conjugation by a projective measurement. It is the step that lets answer reduction replace a measurement of a whole proof tuple by the product of measurements of its pieces.
The chain #
The proof has three parts, and only the middle one is about sandwiches.
- From evaluations to outcomes. Two distinct functions of the family agree at a random point
with probability at most
ε. So when the evaluations disagree with probabilityδ, the outcomes themselves disagree with probabilityηsatisfyingη (1 - ε) ≤ δ, and sinceη ≤ 1this isη ≤ δ + εwith no case split (one_sub_sum_bornProb_le_eval). The only use of the independence of the point from the index is here: the Born probabilities do not see the point, so its average acts on the collision indicator alone. - One more layer of the sandwich (
sqrt_sum_xSqNorm_sandStep_le). Alice's joint element is the palindromeA_g A_o A_gof her two marginals, and three replacements move it to Bob'sG_g C_o G_g: the rightA_g, thenA_o, then the leftA_g. Each replacement multiplies a known deviation by a family whose squares sum to at most the identity, so it costs exactly that deviation (the paper'sfact:add-a-proj). The three costs are added as square roots, by Minkowski's inequality inℓ²over the index and the outcomes, and that is what keeps the error linear ink: the cruder(a + b + c)² ≤ 3 (a² + b² + c²)would multiply by three at every layer. - From a squared distance back to agreement. When Alice's measurement is projective,
1 - ∑_g ⟨A_g ⊗ C_g⟩ ≤ (∑_g ‖(A_g ⊗ 1 - 1 ⊗ C_g) ψ‖²)^{1/2}, whateverCis (one_sub_sum_bornProb_le_sqrt), and coarse-graining both sides by the evaluation map can only increase agreement (sum_bornProb_le_fibSum_of_nonneg).
The constant #
The paper states k (δ + ε)^{1/2} with an implicit constant. The one here is
2 √2 k (δ + ε)^{1/2}: the 2 √2 is the factor 2 of each layer (the new coordinate is replaced
twice) times the √2 of passing from agreement to squared distance for a single coordinate.
What the statement does not assume #
The paper's outcome set for A is 𝒢_1 × ⋯ × 𝒢_k; its consumer's measurement has function-valued
outcomes outside those families, and the paper's proof uses A only through its coordinate
coarse-grainings. The blueprint's answer is to extend each G^{i,x} by zero projectors to the full
alphabet, so here the outcome set of A is literally the product, and the families are arbitrary
finite types with an evaluation map. The point is drawn from an arbitrary distribution ν, not
necessarily uniform, and the collision bound is stated against it.
Minkowski's inequality for weighted sums of squares #
Minkowski's inequality for a weighted ℓ² sum: the square root of a weighted sum of squares
is a norm, so it satisfies the triangle inequality.
The three-term form for a weight on an index and an unweighted inner sum: the shape of every average over questions of a sum over outcomes.
One layer of the sandwich #
The algebra of one layer. In any ring, if a2 a1 = a, a a2 = a, and Bob's q, c
commute with Alice's a1, a2 as needed, then a - q c q is the sum of the three
replacements.
A projective element, on either factor, is a contraction.
A positive family on Bob's factor summing to the identity satisfies the hypothesis of
sum_snorm_sq_mul_le: C† C = C² ≤ C.
One layer, at a single index. The three families of squared deviations, each bounded by the deviation it multiplies.
The pointwise triangle inequality of one layer.
One layer of the sandwich, averaged over an index. Alice's joint projective measurement
A_{(o, g)} is compared with Bob's Q_g C_o Q_g, where C is any POVM and Q is projective. The
error is the marginal's distance to C plus twice the other marginal's distance to Q, added as
square roots.
The sandwich of k measurements #
The sandwich of k measurements,
M^{k}_{g_k} ⋯ M^{2}_{g_2} M^{1}_{g_1} M^{2}_{g_2} ⋯ M^{k}_{g_k}, with the last index outermost
as in the paper. The empty sandwich is the identity: the one-outcome POVM.
Equations
- MIPRE.sandK x_5 x_6 = 1
- MIPRE.sandK M g = M (Fin.last k) (g (Fin.last k)) * MIPRE.sandK (fun (i : Fin k) => M i.castSucc) (Fin.init g) * M (Fin.last k) (g (Fin.last k))
Instances For
A sandwich of projective measurements sums to the identity: summing the outermost layer
first, ∑_c M_c S M_c = ∑_c M_c² = 1 once the inner sandwich S has summed to the identity.
Coarse-graining along a bijection, a marginal, and a composite #
Coarse-graining does not see a relabelling of the outcomes by a bijection.
Coarse-graining a marginal is coarse-graining the joint family.
Coarse-graining twice is coarse-graining along the composite.
The k-fold sandwich, at the level of outcomes #
The k-fold sandwich, at the level of outcomes (NW19's Fact 4.33, averaged over an index,
in the squared-distance form). Alice's projective measurement of a k-tuple is compared with Bob's
sandwich of his k projective measurements: the error, as a square root, is at most twice the sum
of the square roots of the k coordinate errors. Induction on k, peeling the outermost layer with
sqrt_sum_xSqNorm_sandStep_le.
From agreement to squared distance and back #
The Born probabilities of two families that each sum to the identity add up to one.
A squared distance to a projective measurement bounds the disagreement, whatever the other
family is (NW19's Fact 4.14, item 3, with constant one). The mass 1 = ∑_a ‖(P_a ⊗ 1) ψ‖² minus
the agreement is a sum of cross terms ⟨(P_a ⊗ 1) ψ, (P_a ⊗ 1 - 1 ⊗ C_a) ψ⟩, and one
Cauchy--Schwarz over the outcomes bounds it.
Coarse-graining two positive families the same way only adds agreement. The added terms are
Born probabilities of positive operators; no projectivity is needed, unlike
sum_bornProb_le_fibSum.
From evaluations to outcomes. Two projective measurements with the same outcome set, whose
outcomes are separated by an evaluation map at a point drawn from ν (distinct outcomes collide
with probability at most ε): their disagreement is at most the average disagreement of the
evaluated measurements, plus ε.
With η the disagreement of the outcomes, the evaluated disagreement is at least (1 - ε) η,
because the Born probabilities do not depend on the point and every disagreeing pair of outcomes is
separated with probability at least 1 - ε. Since η ≤ 1, this gives η ≤ δ + ε.
The low-degree sandwich #
The low-degree sandwich (blueprint lem:ar-sandwich-support; the paper's lem:ld-sandwich;
NW19's Fact 4.34 with an index).
An index x is drawn from μ and a point y from ν, independently. Alice measures A^x,
projective, with outcome a tuple g whose i-th coordinate lies in a finite family G i; Bob has,
for each i, a projective measurement M i x of the i-th coordinate. The families are separated
by their evaluation maps ev i y: distinct members collide at y ∼ ν with probability at most ε.
If, for every coordinate, Alice's evaluated coordinate disagrees with Bob's evaluated measurement
with probability at most δ, then Alice's evaluated tuple disagrees with the evaluated sandwich
sandK (M · x) with probability at most 2 √2 k (δ + ε)^{1/2}.