Lemma 3 (Robust one-shot decoupling)
ProvedQAlgorithms.Papers.Independent.Gap48.P38.lemma3_robustDecouplingLet be nonempty finite complex registers. Let be density matrices, let , and suppose , using the full trace norm. Fix a unitary identification , and put . Let , where is normalized Haar probability on . With and actual partial traces,
This is exactly the printed norm-of-average estimate. It does not assert the stronger average-of-norms bound used informally later in the paper. Finite-dimensional continuous integrands on the compact unitary group ensure integrability.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P38
noncomputable section
open MeasureTheory
open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise
attribute [local instance] Classical.propDecidable Classical.decEq
namespace QAlgorithms.Papers.Independent.Gap48.P38
/-- Lemma 3 (robust one-shot decoupling), PDF p.6, eq.(16), appendix pp.11--12.
The norm is OUTSIDE the Haar average, as printed, not the average of norms.
The matrix integral uses the finite elementwise norm; all integrands are
continuous on compact U(c), hence Bochner integrable;
no unproved integrability assumption is added to the source's hypotheses. -/
theorem lemma3_robustDecoupling
(c s b e : ℕ) (hc : 0 < c) (hs : 0 < s) (hb : 0 < b) (he : 0 < e)
(psi phi : Matrix (Fin c × Fin e) (Fin c × Fin e) ℂ)
(hpsi : IsDensityMatrix psi) (hphi : IsDensityMatrix phi)
(epsilon : ℝ) (hepsilon : 0 < epsilon) (hclose : traceNorm (psi - phi) ≤ epsilon)
(W : Matrix (Fin s × Fin b) (Fin c) ℂ)
(hW : Wᴴ * W = 1 ∧ W * Wᴴ = 1) :
traceNorm ((∫ U : Matrix.unitaryGroup (Fin c) ℂ,
decouplingMarginal W psi U ∂Schur.unitaryHaar c) -
Matrix.kronecker (QAlgorithms.Papers.Independent.Information100.P08.maximallyMixed b) (traceLeft psi)) ≤
2 * epsilon + Real.sqrt ((c : ℝ) * (Matrix.rank (traceLeft phi) : ℝ) *
frobNorm phi ^ 2 / (s : ℝ) ^ 2) := by sorry
end QAlgorithms.Papers.Independent.Gap48.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For positive natural numbers , let be positive semidefinite complex matrices of trace one on , let , and suppose . Let satisfy both and ; these conditions require , so there is no such when these dimensions differ. Write , and define
Then, for normalized Haar probability measure on the unitary matrices,
Here , with the square root defined by continuous functional calculus, and . The trace norm on the left is taken after integrating the matrices.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.