Tight one-parity information bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P77.tight_parity_boundLet . Fix an unrestricted joint unitary attack on the ideal two-level signals and a probe initially in a fixed pure basis state. Fix the preparation/measurement bases, a balanced test/information partition, and announced test strings whose probability is positive. Symmetrize the attack coherently by Eq. (2), then condition on this test outcome using its actual probability. Write for the resulting normalized information-register probe coefficients, with Alice's information bits uniform. These coefficients are constructed from the unitary, rather than postulated to have any Fourier or information property. The public classical channel is unjammable and Eve has access only to the quantum channel and the public transcript.
For an information input , put , , and . Dot products are modulo two and inner products conjugate the first argument.
Let be the binary linear code and let be the span of all disclosed parity rows. Equivalently the parity check matrix is a basis of , so is full rank. Fix an announced syndrome coset and use its uniform distribution, independently of the fixed public code choice. Let be the PA mask, put , and let be the supremum, over all finite POVMs, of mutual information in bits on the purified states about . Thus both parity classes are nonempty and equally likely. Disclosed other PA bits, when present, are included in .
For every real ,
The bound includes the announced syndrome and any other disclosed key bits. It avoids an exponential prefactor in the number of disclosed parity rows.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P77
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P77
open scoped BigOperators ComplexConjugate ComplexOrder
open QAlgorithms
-- The repair instruction authorizes imports of pinned accepted definitions.
-- These are definitions only; no imported paper theorem is used here.
open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)
open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon)
open QAlgorithms.Papers.Independent.Information100.P39 (pushLaw)
open QAlgorithms.Papers.Independent.Support50.P16 (trivialMeasurement)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- Lemma 3.3, PDF p.8, Eq.(6), restated as Lemma G.1, p.22, Eq.(28): tight
fair-parity information bound for the purified ensemble. C-perp includes every
disclosed ECC/other PA row;
i0+C is the uniform announced syndrome coset, not an arbitrary prior. -/
theorem tight_parity_bound {n d : ℕ} (hn : 1 ≤ n)
(U : Matrix.unitaryGroup (Fin d × Qubits (n + n)) ℂ) (e0 : Fin d)
(iT jT : Qubits n)
(hpos : 0 < testProbability (coherentBitSymmetrize (attackProbes U e0)) iT jT (fun _ => false))
(C : Submodule (ZMod 2) (Fin n → ZMod 2)) (i0 v : Fin n → ZMod 2)
(hv : v ∉ binDual C) (alpha : ℝ) (ha : 0 < alpha) :
parityInformation (conditionedSymmetric U e0 iT jT) C i0 v ≤
alpha + fourierTail (conditionedSymmetric U e0 iT jT)
(distanceToSpan (binDual C) v) / alpha := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P77
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let , , let be unitary on the basis , choose , and choose . Using bitwise XOR , concatenation , and , set
where are -bit strings, are -bit strings, and ; assume . Let be a linear subspace, let , and assume , where . For , let be the bit string corresponding to , define , and let be true exactly when in . Define as the real supremum, over every positive integer and every family of positive semidefinite matrices on the probe space satisfying , of the classical mutual information of the joint weights
Here mutual information means , with and . Put
For every real , with no upper restriction on ,
The tail includes equality at its threshold; the hypothesis excludes the zero code and makes .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.