Definitions for A Proof of the Security of Quantum Key Distribution
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P77The objects the formalized statements of A Proof of the Security of Quantum Key Distribution (arXiv:quant-ph/9912053) are stated in. Each was checked against the paper by a blind read-back and a moderator.
classicalMutualInfo: PDF p.24: classical mutual information.given: PDF p.24: conditional weights. Null outcomes give zero weights and are used only with zero multiplier or excluded by positive probability.mutualAt: PDF p.24: information in one conditional experiment.averagedConditionalInfo: PDF p.24: averaged conditional information.JointIndependent: PDF p.24: joint independence, with possibly different finite alphabets.previous: PDF p.24: coordinates preceding i.others: PDF pp.24--25: all coordinates except i.finiteMax: PDF p.24: finite maximum. The empty default is excluded in applications by m>=1 and a normalized source law.coordinateMaximum: PDF p.24: maximum of averaged conditional coordinate information.disclosureMaximum: PDF p.24: maximum over positive-probability disclosures only.measuredWeights: PDF p.25: Born-rule joint weights of source label and measurement output.ensembleAccessibleInfo: PDF p.25, Eq.(31): accessible information about a function of the label. For the normalized ensembles used below the value set is nonempty (identity POVM) and bounded by the label entropy. No maximum attainment is assumed.conditionalAccessible: PDF p.25: accessible information after one positive disclosure.quantumDisclosureMaximum: PDF p.25, Eq.(33): maximum of separately optimized conditional values.Probes: PDF p.5: probe coefficient vectors, not normalized states individually.character: PDF pp.5--6: binary character as a complex sign.attackProbes: PDF p.14, Eq.(12): probes computed from U and a fixed initial probe state. The attack is fixed before Alice's input.coherentBitSymmetrize: PDF pp.5,14, Eqs.(2),(13): coherent symmetrization with a retained mask. Alice's input is uniform; Bob's output is not assumed uniform.testProbability: PDF pp.14--15: the actual probability of the test outcome. A fixed basis and partition are absorbed into U's coordinates, with test positions first.conditionOnTest: PDF p.15, Eq.(17): normalization computed from the same attack using zero as reference information input. Used only at positive-probability transcripts.conditionedSymmetric: PDF pp.5--6,14--15: the specific conditional symmetrized probes from U.probeDensity: PDF p.6, Section 3.1: Eve's mixed state after tracing Bob out.errorPurification: PDF p.6, Section 3.2: the specific error-labelled purification, c=i+j.probeFourierComponent: PDF p.6, Definition 3.1: Fourier coefficient 2^(-n); no eta-hat for zero eta.fourierWeight: PDF p.6: squared Fourier-component norm.conjugateProbes: PDF p.17, Appendix E: change both information input and output bases of this same conditional map; test bases stay fixed.probeErrorProbability: PDF p.7: error probabilities averaged over Alice's uniform inputs.distanceToSpan: PDF p.8: minimum distance to a disclosed span, which contains zero.fourierTail: PDF pp.8,19: boundary-inclusive tail; doubled integer weights avoid truncated division at odd distance.conjugateTail: PDF p.8, Eq.(7): conjugate-basis error tail, with equality included.codeLaw: PDF pp.17--18: uniform coset i0+C, parametrized bijectively by c in C. A basis of C-perp gives exactly the source's full-rank parity check matrix.codeStates: PDF pp.7,18,21: the source's purified states on the fixed syndrome coset. The error register is retained: rho_i = |phi_i><phi_i| in Section 3.4 and Appendix G, not the less informative mixed marginal probeDensity from Section 3.1.maskParity: PDF pp.7,17: binary parity dot product.parityInformation: PDF pp.8,18,22: accessible parity information in the error-labelled purification, with disclosed C-perp and syndrome. v outside C-perp ensures a fair, nonempty pair of parity classes.disclosedSpan: PDF p.8: ECC rows and all other PA rows disclosed for bit j.IndependentPA: PDF pp.3,8: joint PA independence modulo the ECC rows.keyDistance: PDF pp.8--9: minimum distance over key bits with all others disclosed. Only m>=1 is used below, excluding the syntactic empty default.wholeKeyInformation: PDF p.9, Eq.(8): whole-key accessible information in the error-labelled purification on the uniform syndrome coset; ECC and PA are fixed independently of the unknown coset element. This also upper-bounds the actual mixed probes.BalancedPartition: PDF pp.10,27: all balanced choices of information positions.informationErrors: PDF p.27: errors in the information positions.testErrors: PDF p.27: errors in the complementary test positions.samplingDeviation: PDF pp.10,27--28: joint deviation under any full-error-string law at fixed basis, and an independent uniform balanced partition.PassWeights: PDF p.28: subnormalized joint pass/transcript weights.luckyProbability: PDF pp.28--29: joint probability of passing and information >= a.testOnlyConditioned: PDF p.15, immediately before Eq.(18): symmetrize only the test mask, with the common normalization from the full symmetrization. Individual rows need not be normalized before information symmetrization; their uniform average is.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Defs_QECC
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P47
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P04
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P27
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P39
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P16
/-! Statements from quant-ph/9912053v1. Page numbers are PDF pages.
Local conditional experiments are constructed from a unitary, never postulated
to satisfy the desired information bound. Deferred nodes are in HARD.md. -/
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
/-- PDF p.24: classical mutual information. -/
def classicalMutualInfo {Omega X Y : Type} [Fintype Omega] [Fintype X] [Fintype Y]
(p : Omega → ℝ) (Xvar : Omega → X) (Yvar : Omega → Y) : ℝ :=
shannon (pushLaw p Xvar) + shannon (pushLaw p Yvar) -
shannon (pushLaw p (fun w => (Xvar w, Yvar w)))
/-- PDF p.24: conditional weights. Null outcomes give zero weights and are
used only with zero multiplier or excluded by positive probability. -/
def given {Omega Z : Type} [Fintype Omega] (p : Omega → ℝ)
(Zvar : Omega → Z) (z : Z) : Omega → ℝ :=
fun w => if Zvar w = z then p w / pushLaw p Zvar z else 0
/-- PDF p.24: information in one conditional experiment. -/
def mutualAt {Omega X Y Z : Type} [Fintype Omega] [Fintype X] [Fintype Y]
(p : Omega → ℝ) (Xvar : Omega → X) (Yvar : Omega → Y)
(Zvar : Omega → Z) (z : Z) : ℝ :=
classicalMutualInfo (given p Zvar z) Xvar Yvar
/-- PDF p.24: averaged conditional information. -/
def averagedConditionalInfo {Omega X Y Z : Type} [Fintype Omega] [Fintype X]
[Fintype Y] [Fintype Z] (p : Omega → ℝ) (Xvar : Omega → X)
(Yvar : Omega → Y) (Zvar : Omega → Z) : ℝ :=
∑ z, pushLaw p Zvar z * mutualAt p Xvar Yvar Zvar z
/-- PDF p.24: joint independence, with possibly different finite alphabets. -/
def JointIndependent {Omega : Type} [Fintype Omega] {m : ℕ}
{A : Fin m → Type} [∀ i, Fintype (A i)] (p : Omega → ℝ)
(key : (i : Fin m) → Omega → A i) : Prop :=
∀ a : (i : Fin m) → A i,
pushLaw p (fun w i => key i w) a = ∏ i, pushLaw p (key i) (a i)
/-- PDF p.24: coordinates preceding i. -/
def previous {Omega : Type} {m : ℕ} {A : Fin m → Type}
(key : (i : Fin m) → Omega → A i) (i : Fin m) (w : Omega) :
(j : {j : Fin m // j < i}) → A j.val := fun j => key j.val w
/-- PDF pp.24--25: all coordinates except i. -/
def others {Omega : Type} {m : ℕ} {A : Fin m → Type}
(key : (i : Fin m) → Omega → A i) (i : Fin m) (w : Omega) :
(j : {j : Fin m // j ≠ i}) → A j.val := fun j => key j.val w
/-- PDF p.24: finite maximum. The empty default is excluded in applications by
m>=1 and a normalized source law. -/
def finiteMax (s : Finset ℝ) : ℝ := if h : s.Nonempty then s.max' h else 0
/-- PDF p.24: maximum of averaged conditional coordinate information. -/
def coordinateMaximum {Omega E : Type} [Fintype Omega] [Fintype E]
{m : ℕ} {A : Fin m → Type} [∀ i, Fintype (A i)]
(p : Omega → ℝ) (key : (i : Fin m) → Omega → A i) (eve : Omega → E) : ℝ :=
finiteMax (Finset.univ.image fun i : Fin m =>
averagedConditionalInfo p (key i) eve (others key i))
/-- PDF p.24: maximum over positive-probability disclosures only. -/
def disclosureMaximum {Omega E : Type} [Fintype Omega] [Fintype E]
{m : ℕ} {A : Fin m → Type} [∀ i, Fintype (A i)]
(p : Omega → ℝ) (key : (i : Fin m) → Omega → A i) (eve : Omega → E) : ℝ :=
finiteMax (Finset.univ.biUnion fun i : Fin m =>
((Finset.univ.filter fun a => 0 < pushLaw p (others key i) a).image
fun a => mutualAt p (key i) eve (others key i) a))
/-- PDF p.25: Born-rule joint weights of source label and measurement output. -/
def measuredWeights {X Q : Type} [Fintype X] [Fintype Q] [DecidableEq Q]
(p : X → ℝ) (rho : X → Matrix Q Q ℂ) (M : Measurement Q) :
X × Fin M.outcomes → ℝ :=
fun z => p z.1 * effectProb (M.effect z.2) (rho z.1)
/-- PDF p.25, Eq.(31): accessible information about a function of the label.
For the normalized ensembles used below the value set is nonempty (identity
POVM) and bounded by the label entropy. No maximum attainment is assumed. -/
def ensembleAccessibleInfo {X K Q : Type} [Fintype X] [Fintype K] [Fintype Q]
[DecidableEq Q] (p : X → ℝ) (rho : X → Matrix Q Q ℂ) (key : X → K) : ℝ :=
sSup {v | ∃ M : Measurement Q,
v = classicalMutualInfo (measuredWeights p rho M) (fun z => key z.1) Prod.snd}
/-- PDF p.25: accessible information after one positive disclosure. -/
def conditionalAccessible {X K Z Q : Type} [Fintype X] [Fintype K]
[Fintype Q] [DecidableEq Q] (p : X → ℝ) (rho : X → Matrix Q Q ℂ)
(key : X → K) (disclosed : X → Z) (z : Z) : ℝ :=
ensembleAccessibleInfo (given p disclosed z) rho key
/-- PDF p.25, Eq.(33): maximum of separately optimized conditional values. -/
def quantumDisclosureMaximum {X Q : Type} [Fintype X] [Fintype Q] [DecidableEq Q]
{m : ℕ} {A : Fin m → Type} [∀ i, Fintype (A i)]
(p : X → ℝ) (rho : X → Matrix Q Q ℂ)
(key : (i : Fin m) → X → A i) : ℝ :=
finiteMax (Finset.univ.biUnion fun i : Fin m =>
((Finset.univ.filter fun a => 0 < pushLaw p (others key i) a).image
fun a => conditionalAccessible p rho (key i) (others key i) a))
/-- PDF p.5: probe coefficient vectors, not normalized states individually. -/
abbrev Probes (n : ℕ) (Q : Type) := Qubits n → Qubits n → EuclideanSpace ℂ Q
/-- PDF pp.5--6: binary character as a complex sign. -/
def character {n : ℕ} (x y : Qubits n) : ℂ := if dotBits x y then -1 else 1
/-- PDF p.14, Eq.(12): probes computed from U and a fixed initial probe state.
The attack is fixed before Alice's input. -/
def attackProbes {n d : ℕ}
(U : Matrix.unitaryGroup (Fin d × Qubits n) ℂ) (e0 : Fin d) : Probes n (Fin d) :=
fun i j => WithLp.toLp 2 fun q => (U : Matrix _ _ ℂ) (q, j) (e0, i)
/-- PDF pp.5,14, Eqs.(2),(13): coherent symmetrization with a retained mask.
Alice's input is uniform; Bob's output is not assumed uniform. -/
def coherentBitSymmetrize {n : ℕ} {Q : Type} (E : Probes n Q) : Probes n (Qubits n × Q) :=
fun i j => WithLp.toLp 2 fun z =>
((Real.sqrt ((2 : ℝ) ^ n))⁻¹ : ℂ) * character (i + j) z.1 *
E (i + z.1) (j + z.1) z.2
/-- PDF pp.14--15: the actual probability of the test outcome. A fixed basis
and partition are absorbed into U's coordinates, with test positions first. -/
def testProbability {n : ℕ} {Q : Type} [Fintype Q] (E : Probes (n + n) Q)
(iT jT iI : Qubits n) : ℝ :=
∑ jI, ‖E (Fin.append iT iI) (Fin.append jT jI)‖ ^ 2
/-- PDF p.15, Eq.(17): normalization computed from the same attack using zero
as reference information input. Used only at positive-probability transcripts. -/
def conditionOnTest {n : ℕ} {Q : Type} [Fintype Q] (E : Probes (n + n) Q)
(iT jT : Qubits n) : Probes n Q :=
fun iI jI => ((Real.sqrt (testProbability E iT jT (fun _ => false)))⁻¹ : ℂ) •
E (Fin.append iT iI) (Fin.append jT jI)
/-- PDF pp.5--6,14--15: the specific conditional symmetrized probes from U. -/
def conditionedSymmetric {n d : ℕ}
(U : Matrix.unitaryGroup (Fin d × Qubits (n + n)) ℂ)
(e0 : Fin d) (iT jT : Qubits n) : Probes n (Qubits (n + n) × Fin d) :=
conditionOnTest (coherentBitSymmetrize (attackProbes U e0)) iT jT
/-- PDF p.6, Section 3.1: Eve's mixed state after tracing Bob out. -/
def probeDensity {n : ℕ} {Q : Type} (E : Probes n Q) (i : Qubits n) : Matrix Q Q ℂ :=
fun q r => ∑ j, E i j q * conj (E i j r)
/-- PDF p.6, Section 3.2: the specific error-labelled purification, c=i+j. -/
def errorPurification {n : ℕ} {Q : Type} (E : Probes n Q) (i : Qubits n) :
EuclideanSpace ℂ (Q × Qubits n) := WithLp.toLp 2 fun z => E i (i + z.2) z.1
/-- PDF p.6, Definition 3.1: Fourier coefficient 2^(-n); no eta-hat for zero eta. -/
def probeFourierComponent {n : ℕ} {Q : Type} (E : Probes n Q) (l : Qubits n) :
EuclideanSpace ℂ (Q × Qubits n) :=
(((2 : ℝ) ^ n)⁻¹ : ℂ) • ∑ i, character l i • errorPurification E i
/-- PDF p.6: squared Fourier-component norm. -/
def fourierWeight {n : ℕ} {Q : Type} [Fintype Q] (E : Probes n Q)
(l : Qubits n) : ℝ := ‖probeFourierComponent E l‖ ^ 2
/-- PDF p.17, Appendix E: change both information input and output bases of
this same conditional map; test bases stay fixed. -/
def conjugateProbes {n : ℕ} {Q : Type} (E : Probes n Q) : Probes n Q :=
fun k l => (((2 : ℝ) ^ n)⁻¹ : ℂ) •
∑ i, ∑ j, (character i k * character j l) • E i j
/-- PDF p.7: error probabilities averaged over Alice's uniform inputs. -/
def probeErrorProbability {n : ℕ} {Q : Type} [Fintype Q] (E : Probes n Q)
(c : Qubits n) : ℝ := ((2 : ℝ) ^ n)⁻¹ * ∑ i, ‖E i (i + c)‖ ^ 2
/-- PDF p.8: minimum distance to a disclosed span, which contains zero. -/
def distanceToSpan {n : ℕ} (S : Submodule (ZMod 2) (Fin n → ZMod 2))
(v : Fin n → ZMod 2) : ℕ :=
Finset.univ.inf' Finset.univ_nonempty
(fun w : S => hammingWeight (bitsOfZMod (v + w.val)))
/-- PDF pp.8,19: boundary-inclusive tail; doubled integer weights avoid
truncated division at odd distance. -/
def fourierTail {n : ℕ} {Q : Type} [Fintype Q] (E : Probes n Q) (dist : ℕ) : ℝ :=
∑ l ∈ Finset.univ.filter (fun l => dist ≤ 2 * hammingWeight l), fourierWeight E l
/-- PDF p.8, Eq.(7): conjugate-basis error tail, with equality included. -/
def conjugateTail {n : ℕ} {Q : Type} [Fintype Q] (E : Probes n Q) (dist : ℕ) : ℝ :=
∑ c ∈ Finset.univ.filter (fun c => dist ≤ 2 * hammingWeight c),
probeErrorProbability (conjugateProbes E) c
/-- PDF pp.17--18: uniform coset i0+C, parametrized bijectively by c in C.
A basis of C-perp gives exactly the source's full-rank parity check matrix. -/
def codeLaw {n : ℕ} (C : Submodule (ZMod 2) (Fin n → ZMod 2)) : C → ℝ :=
fun _ => (Fintype.card C : ℝ)⁻¹
/-- PDF pp.7,18,21: the source's purified states on the fixed syndrome coset.
The error register is retained: rho_i = |phi_i><phi_i| in Section 3.4 and Appendix G,
not the less informative mixed marginal probeDensity from Section 3.1. -/
def codeStates {n : ℕ} {Q : Type} (E : Probes n Q)
(C : Submodule (ZMod 2) (Fin n → ZMod 2)) (i0 : Fin n → ZMod 2) :
C → Matrix (Q × Qubits n) (Q × Qubits n) ℂ :=
fun c => pureDensity (errorPurification E (bitsOfZMod (i0 + c.val)))
/-- PDF pp.7,17: binary parity dot product. -/
def maskParity {n : ℕ} (v x : Fin n → ZMod 2) : Bool := decide (x ⬝ᵥ v = 1)
/-- PDF pp.8,18,22: accessible parity information in the error-labelled
purification, with disclosed C-perp and syndrome. v outside C-perp ensures
a fair, nonempty pair of parity classes. -/
def parityInformation {n : ℕ} {Q : Type} [Fintype Q] [DecidableEq Q]
(E : Probes n Q) (C : Submodule (ZMod 2) (Fin n → ZMod 2))
(i0 v : Fin n → ZMod 2) : ℝ :=
ensembleAccessibleInfo (codeLaw C) (codeStates E C i0) (fun c => maskParity v (i0 + c.val))
/-- PDF p.8: ECC rows and all other PA rows disclosed for bit j. -/
def disclosedSpan {n m : ℕ} (C : Submodule (ZMod 2) (Fin n → ZMod 2))
(V : Fin m → Fin n → ZMod 2) (j : Fin m) : Submodule (ZMod 2) (Fin n → ZMod 2) :=
binDual C ⊔ Submodule.span (ZMod 2) {v | ∃ k : Fin m, k ≠ j ∧ V k = v}
/-- PDF pp.3,8: joint PA independence modulo the ECC rows. -/
def IndependentPA {n m : ℕ} (C : Submodule (ZMod 2) (Fin n → ZMod 2))
(V : Fin m → Fin n → ZMod 2) : Prop :=
∀ z : Fin m → ZMod 2, (∑ j, z j • V j) ∈ binDual C → z = 0
/-- PDF pp.8--9: minimum distance over key bits with all others disclosed.
Only m>=1 is used below, excluding the syntactic empty default. -/
def keyDistance {n m : ℕ} (C : Submodule (ZMod 2) (Fin n → ZMod 2))
(V : Fin m → Fin n → ZMod 2) : ℕ :=
if h : (Finset.univ : Finset (Fin m)).Nonempty then
Finset.univ.inf' h (fun j => distanceToSpan (disclosedSpan C V j) (V j)) else 0
/-- PDF p.9, Eq.(8): whole-key accessible information in the error-labelled
purification on the uniform syndrome coset; ECC and PA are fixed independently
of the unknown coset element. This also upper-bounds the actual mixed probes. -/
def wholeKeyInformation {n m : ℕ} {Q : Type} [Fintype Q] [DecidableEq Q]
(E : Probes n Q) (C : Submodule (ZMod 2) (Fin n → ZMod 2))
(i0 : Fin n → ZMod 2) (V : Fin m → Fin n → ZMod 2) : ℝ :=
ensembleAccessibleInfo (codeLaw C) (codeStates E C i0) (fun c j => maskParity (V j) (i0 + c.val))
/-- PDF pp.10,27: all balanced choices of information positions. -/
abbrev BalancedPartition (n : ℕ) := {s : Finset (Fin (n + n)) // s.card = n}
/-- PDF p.27: errors in the information positions. -/
def informationErrors {n : ℕ} (s : BalancedPartition n) (c : Qubits (n + n)) : ℕ :=
(s.val.filter fun q => c q = true).card
/-- PDF p.27: errors in the complementary test positions. -/
def testErrors {n : ℕ} (s : BalancedPartition n) (c : Qubits (n + n)) : ℕ :=
((Finset.univ \ s.val).filter fun q => c q = true).card
/-- PDF pp.10,27--28: joint deviation under any full-error-string law at fixed
basis, and an independent uniform balanced partition. -/
def samplingDeviation {n : ℕ} (p : Law (Qubits (n + n))) (allowed margin : ℝ) : ℝ :=
(Fintype.card (BalancedPartition n) : ℝ)⁻¹ * ∑ s : BalancedPartition n, ∑ c,
if (informationErrors s c : ℝ) ≥ n * (allowed + margin) ∧
(testErrors s c : ℝ) ≤ n * allowed then p.prob c else 0
/-- PDF p.28: subnormalized joint pass/transcript weights. -/
structure PassWeights (T : Type) [Fintype T] where
weight : T → ℝ
nonnegative : ∀ t, 0 ≤ weight t
total_le_one : ∑ t, weight t ≤ 1
/-- PDF pp.28--29: joint probability of passing and information >= a. -/
def luckyProbability {T : Type} [Fintype T] (p : PassWeights T)
(info : T → ℝ) (a : ℝ) : ℝ := ∑ t, if a ≤ info t then p.weight t else 0
/-- PDF p.24: null conditioning really has the stated zero convention. -/
example {Omega Z : Type} [Fintype Omega] (p : Omega → ℝ)
(Zvar : Omega → Z) (z : Z) (h : pushLaw p Zvar z = 0) : given p Zvar z = 0 := by
funext w
simp [given, h]
/-- PDF p.25: the measurement optimization has an admissible one-outcome POVM. -/
example {Q : Type} [Fintype Q] [DecidableEq Q] :
(trivialMeasurement Q).outcomes = 1 := rfl
/-- PDF p.6: c labels the error rather than Bob's measured bit. -/
example {n : ℕ} {Q : Type} (E : Probes n Q) (i c : Qubits n) (q : Q) :
errorPurification E i (q, c) = E i (i + c) q := rfl
/-- PDF p.15, immediately before Eq.(18): symmetrize only the test mask, with
the common normalization from the full symmetrization. Individual rows need not
be normalized before information symmetrization; their uniform average is. -/
def testOnlyConditioned {n d : ℕ}
(U : Matrix.unitaryGroup (Fin d × Qubits (n + n)) ℂ) (e0 : Fin d)
(iT jT : Qubits n) : Probes n (Qubits n × Fin d) :=
fun iI jI => WithLp.toLp 2 fun z =>
((Real.sqrt (testProbability (coherentBitSymmetrize (attackProbes U e0))
iT jT (fun _ => false)))⁻¹ : ℂ) *
((Real.sqrt ((2 : ℝ) ^ n))⁻¹ : ℂ) * character (iT + jT) z.1 *
attackProbes U e0 (Fin.append (iT + z.1) iI) (Fin.append (jT + z.1) jI) z.2
end QAlgorithms.Papers.Independent.Intakenext100.P77
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakenext100.P77.BalancedPartition
For every natural number , this is the type of subsets having exactly elements. The selected subset is part of the data; its complement supplies the other half. When , the type has exactly one element, represented by the empty subset.
QAlgorithms.Papers.Independent.Intakenext100.P77.IndependentPA
For every pair of natural numbers , linear subspace , and family , this defines the proposition that every coefficient vector satisfies
Thus any linear combination of the lying in the subspace orthogonal to every element of must have all coefficients zero. For , the condition holds because the only coefficient vector is zero. For , or for , it can hold only when .
QAlgorithms.Papers.Independent.Intakenext100.P77.JointIndependent
For an arbitrary finite type , a natural number , a family of finite types , a real-valued function , and functions , this predicate requires, for every tuple , that
There is no assumption that is nonnegative or normalized, and the finite types may be empty. If the product alphabet has no elements, the universal requirement is vacuous. When , there is one empty tuple, and the predicate requires exactly , because the empty product on the right is one.
QAlgorithms.Papers.Independent.Intakenext100.P77.PassWeights
For a finite type , this structure consists of a real-valued function , together with the requirements that for every and . Equality with is not required, and the identically zero function is permitted. The type may be empty, in which case the total weight is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.Probes
For any natural number and any type , a probe family is a function assigning to each ordered pair of Boolean strings of length a complex coordinate vector indexed by , represented in the Euclidean-space type:
No finiteness assumption on , normalization condition, or other restriction on this family is included. When , there is exactly one input pair, consisting of two empty strings.
QAlgorithms.Papers.Independent.Intakenext100.P77.attackProbes
For natural numbers , a unitary matrix indexed by , and a chosen index , this defines a vector for every pair of length- Boolean strings by
Thus the coordinates are the specified entries of . The chosen index excludes ; is allowed and gives the vector with coordinates .
QAlgorithms.Papers.Independent.Intakenext100.P77.averagedConditionalInfo
For arbitrary finite types , a real-valued function , and functions , , and , put and define on that fiber and zero elsewhere. For each , let , , and be the sums of over the fibers of , , and their pair, respectively. This defines
No nonnegativity or normalization is required of . Division by zero gives zero, and the real logarithm is total, taking value zero at zero and using the absolute value for negative arguments. Zero-mass fibers therefore contribute zero. Empty finite types and empty sums are allowed.
QAlgorithms.Papers.Independent.Intakenext100.P77.character
For any natural number and Boolean strings of length , this defines the complex number
where the exponent matters only modulo two: the value is when an odd number of positions have both bits true, and otherwise. For , the sum is empty and the value is .
QAlgorithms.Papers.Independent.Intakenext100.P77.classicalMutualInfo
For arbitrary finite types , a real-valued function , and functions and , define the marginal weights , , and joint weights . The declared quantity is
There is no assumption that is nonnegative or sums to one. The logarithm is the total real logarithm used by the code, with and for negative . Empty finite types and empty sums are allowed.
QAlgorithms.Papers.Independent.Intakenext100.P77.codeLaw
For every natural number and linear subspace , this defines the real-valued function on assigning
The subspace is finite and contains zero, so its cardinality is positive. In particular, if , including the case , the function assigns weight one to its sole element.
QAlgorithms.Papers.Independent.Intakenext100.P77.codeStates
For every natural number , arbitrary type , family assigning a complex vector to each pair of bit strings , binary linear subspace , and vector , this defines a matrix for every . Let have its -th bit true exactly when , and define , where addition of bit strings is coordinatewise exclusive-or. The resulting matrix, indexed by , is
No finiteness assumption on or normalization assumption on is imposed, so these matrices are not required to have trace one. The definition includes , when there is a single empty bit string.
QAlgorithms.Papers.Independent.Intakenext100.P77.coherentBitSymmetrize
For any natural number , any type , and any family assigning a complex -indexed vector to each pair of length- Boolean strings, this defines a family with vectors indexed by through
Here every is coordinatewise exclusive-or, and the sign is negative precisely when the displayed sum is odd. No finiteness assumption on or normalization assumption on is imposed. For , the string index is unique, the prefactor and sign are both , and the coordinates are those of .
QAlgorithms.Papers.Independent.Intakenext100.P77.conditionOnTest
For any natural number , finite type , arbitrary vector family indexed by pairs of length- Boolean strings, and fixed length- strings , let
The definition assigns to each pair the vector
The denominator always uses the all-false string , regardless of . No positivity or normalization hypothesis is imposed; when , its inverse square root is defined as zero and the entire resulting family is zero. The case is included.
QAlgorithms.Papers.Independent.Intakenext100.P77.conditionalAccessible
For finite types , with decidable equality on , an arbitrary type , functions , , , , and , define and when , and otherwise. The defined value is the real supremum, over every positive integer and every family of positive semidefinite matrices satisfying , of
where , , , , and , using the total real logarithm. There is no assumption that is a probability distribution or that the matrices are density matrices. Division by zero is defined as zero, so makes identically zero and the defined value zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.conditionedSymmetric
For natural numbers , a unitary matrix indexed by , a chosen , and length- Boolean strings , define, for and ,
The defined family has coordinates , for every pair of length- strings . Concatenation is denoted by , addition of strings is coordinatewise exclusive-or, and each sign is determined by parity. If , the whole family is zero by the zero-inverse convention. The index excludes , while is allowed.
QAlgorithms.Papers.Independent.Intakenext100.P77.conjugateProbes
For every natural number , arbitrary type , and family of complex coordinate vectors indexed by , where , this defines another such family by
with each dot product calculated modulo two. There is no finiteness assumption on and no normalization assumption on . For , the resulting family equals .
QAlgorithms.Papers.Independent.Intakenext100.P77.conjugateTail
For every natural number , finite type , family of vectors in , where , and natural number , this defines
Here counts the true coordinates, dot products are modulo two, and is coordinatewise exclusive-or. No normalization is required. The condition includes equality; includes all , and gives zero. For , the value is when , and zero otherwise.
QAlgorithms.Papers.Independent.Intakenext100.P77.coordinateMaximum
For arbitrary finite types , a natural number , finite types for , a real-valued function , functions , and a function , write . For each tuple , put and define on that fiber and zero elsewhere. Let , , and be the weights obtained by summing over the fibers of , , and . This defines the maximum, over , of
with value zero when . No probability or independence assumptions are required. Division by zero is zero, and the total logarithm takes value zero at zero and uses the absolute value for negative arguments. Thus zero-mass fibers contribute zero; a nonempty collection of coordinate values is maximized without truncation at zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.disclosedSpan
For every pair of natural numbers , linear subspace , family , and index , this defines the subspace
The sum denotes the smallest linear subspace containing both displayed subspaces. Only the index is excluded, so a different index may still supply a vector equal to . For , this is ; for , there is no admissible index . When , the resulting subspace is the zero subspace.
QAlgorithms.Papers.Independent.Intakenext100.P77.disclosureMaximum
For arbitrary finite types , a natural number , finite types for , a real-valued function , functions , and a function , write and . For every pair with and , define on the fiber , and zero elsewhere; let , , and be its marginal and joint weights under and . This defines the maximum of
over all such pairs, and defines the value to be zero if there are no such pairs, including when . The function need not be nonnegative or normalized, and no independence is assumed. Only strictly positive fiber sums are included; zero and negative fiber sums are excluded. The logarithm is total, with value zero at zero and the logarithm of the absolute value for negative arguments.
QAlgorithms.Papers.Independent.Intakenext100.P77.distanceToSpan
For every natural number , linear subspace , and vector , this defines the natural number
Thus the minimized quantity counts the nonzero coordinates of . The minimum is over a finite, nonempty set because every linear subspace contains zero. The definition includes , for which the value is the number of nonzero coordinates of , and , for which the value is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.ensembleAccessibleInfo
For arbitrary finite types , with decidable equality on , a real-valued function , arbitrary complex matrices indexed by , and a function , consider every measurement with a positive finite number of outcomes and positive semidefinite matrices satisfying . For each measurement put , , , and . The declared quantity is the real supremum of
over all these measurements, with no fixed bound on their number of outcomes. No normalization or nonnegativity is imposed on , and no density-matrix conditions are imposed on . Empty finite types are allowed. The logarithm is total, taking value zero at zero and using the absolute value for negative arguments; the real supremum is also total, with value zero for an empty or unbounded-above set of values.
QAlgorithms.Papers.Independent.Intakenext100.P77.errorPurification
For any natural number , any type , any family assigning a complex -indexed vector to each pair of length- Boolean strings, and any length- string , this defines a vector indexed by whose coordinates are
Here is coordinatewise exclusive-or. No finiteness assumption on or normalization condition is imposed. When , is the unique empty string and these coordinates reduce to those of .
QAlgorithms.Papers.Independent.Intakenext100.P77.finiteMax
For every finite set , this defines its greatest element when is nonempty and defines the value to be zero when is empty. A nonempty set containing only negative numbers therefore has its negative maximum as the value.
QAlgorithms.Papers.Independent.Intakenext100.P77.fourierTail
For every natural number , finite type , family of vectors in , where , and natural number , this defines
Here counts the true coordinates of , the dot product is modulo two, and is coordinatewise exclusive-or. No normalization of is assumed. The threshold is inclusive: includes every , whereas gives an empty sum and hence zero. For , the value is if , and zero otherwise.
QAlgorithms.Papers.Independent.Intakenext100.P77.fourierWeight
For every natural number , finite type , family of complex Euclidean vectors indexed by , where , and , this defines the real number
Here is coordinatewise exclusive-or and . No normalization or other condition on is required. When , the sums have one term and the value is ; when is empty, the value is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.given
For an arbitrary finite type , an arbitrary type , a real-valued function , a function , and an element , this defines the function
No finiteness assumption on , normalization assumption on , or positivity assumption on the denominator is imposed. Division by zero is defined to be zero, so a zero denominator makes identically zero, including when cancellation among signed weights causes that denominator to vanish. The type may be empty.
QAlgorithms.Papers.Independent.Intakenext100.P77.informationErrors
For every natural number , every subset of cardinality , and every binary string , the defined natural number is
Thus it counts true coordinates of inside the selected subset. The definition permits , when the count is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.keyDistance
For natural numbers , a binary linear subspace , and vectors indexed by , define and . The defined natural number is
where counts nonzero coordinates and addition is over . Each inner minimum is over a nonempty finite set because . No independence assumption is imposed on the modulo , so the value may be zero. The definition also permits .
QAlgorithms.Papers.Independent.Intakenext100.P77.luckyProbability
For a finite type , nonnegative real weights satisfying , an arbitrary function , and a real threshold , the defined real number is
Equality with the threshold is included. The weights need not have total mass one; if is empty or no value meets the threshold, the sum is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.maskParity
For every natural number and vectors , this defines a Boolean that is true exactly when
and false otherwise. The empty sum is zero, so for the result is false; it is also false whenever or .
QAlgorithms.Papers.Independent.Intakenext100.P77.measuredWeights
For arbitrary finite types , with decidable equality on , a real-valued function , arbitrary complex matrices indexed by , and a measurement consisting of a positive natural number of outcomes and matrices that are positive semidefinite and satisfy , this defines the real-valued function on by
There is no assumption that is a probability distribution or that any is positive semidefinite or has trace one. The finite types may be empty.
QAlgorithms.Papers.Independent.Intakenext100.P77.mutualAt
For arbitrary finite types , an arbitrary type , functions , , , , and an element , put and let when , and otherwise. Form the weights , , and . The declared value is
The function need not be a probability distribution. The logarithm is total, with value zero at zero and the logarithm of the absolute value for negative arguments; division by zero is zero. In particular, gives value zero. Empty finite types are included.
QAlgorithms.Papers.Independent.Intakenext100.P77.others
For an arbitrary type , a natural number , arbitrary types indexed by , functions , an index , and an element , this defines the tuple
No finiteness, probability, or independence assumptions are imposed. For , the result is the unique empty tuple; for , no index can be supplied.
QAlgorithms.Papers.Independent.Intakenext100.P77.parityInformation
For every natural number , finite type with decidable equality, family of vectors in , linear subspace , and vectors , this defines the following real supremum. Write , let be the Boolean string whose -th coordinate is true exactly when , set
and range over all positive integers and matrices that are positive semidefinite and sum to the identity. For each such choice put , , , and . The defined number is
No normalization condition on is imposed, so the arrays used in this entropy formula are not required to have total mass one. Zero entries use the total logarithm convention . The definition includes the trivial code and .
QAlgorithms.Papers.Independent.Intakenext100.P77.previous
For an arbitrary type , a natural number , arbitrary types indexed by , functions , an index , and an element , this defines the tuple of earlier coordinates
No finiteness, probability, or independence assumptions are imposed. For , the result is the unique empty tuple. When , there is no index to supply.
QAlgorithms.Papers.Independent.Intakenext100.P77.probeDensity
For any natural number , any type , any family assigning a complex -indexed vector to each pair of length- Boolean strings, and any such string , this defines the matrix
There is no finiteness assumption on and no normalization assumption on ; in particular, trace one is not required. For , the sum consists of the single outer product associated with the empty output string.
QAlgorithms.Papers.Independent.Intakenext100.P77.probeErrorProbability
For every natural number , finite type , family of vectors in , where , and , this defines
where is coordinatewise exclusive-or and the norm is the Euclidean norm. No normalization condition is imposed, so this real number is not required by the definition to be at most one. When , its value is ; when is empty, its value is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.probeFourierComponent
For any natural number , any type , any family assigning a complex -indexed vector to each pair of length- Boolean strings, and any length- string , this defines the vector indexed by with coordinates
The sign is negative exactly when the displayed exponent is odd, and denotes coordinatewise exclusive-or. No finiteness assumption on or normalization assumption on is imposed. For , the prefactor is one and the sum has the single term .
QAlgorithms.Papers.Independent.Intakenext100.P77.quantumDisclosureMaximum
For finite types , with decidable equality on , any natural number , finite types for , arbitrary , matrices , and functions , let . For each and each tuple satisfying , put if , and zero otherwise. Associate to this pair the real supremum over all positive integers and positive semidefinite matrices summing to of
where , , , and , using the total real logarithm. The definition returns the maximum of the finite set of these supremum values, or zero if that set is empty. In particular, it returns zero when or no disclosure tuple has strictly positive weight. No probability-distribution assumption on , density-matrix assumption on , or independence assumption on the keys is imposed.
QAlgorithms.Papers.Independent.Intakenext100.P77.samplingDeviation
For a natural number , a probability law on binary strings of length —meaning and —and arbitrary real numbers and , the defined real number is
The two comparisons are inclusive, with the counts and interpreted as real numbers. No sign or range restrictions are imposed on the two real parameters. When , both comparisons hold and the value is .
QAlgorithms.Papers.Independent.Intakenext100.P77.testErrors
For every natural number , every subset of cardinality , and every binary string , the defined natural number is
Thus it counts true coordinates of outside the selected subset. The definition permits , when the count is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.testOnlyConditioned
For natural numbers , a unitary matrix indexed by , an index , and binary strings of length , write , where the exponent is computed modulo , write for coordinatewise XOR, and write for concatenation. Define
The declared family assigns to each pair a vector indexed by , with coordinate
No positivity hypothesis on is imposed; when , the inverse square root is defined to be zero, so every resulting vector is zero. The definition permits , while the supplied index requires .
QAlgorithms.Papers.Independent.Intakenext100.P77.testProbability
For any natural number , finite type , family assigning a vector in to each pair of length- Boolean strings, and length- strings , this defines
where denotes concatenation, with the first displayed string occupying the first positions. No normalization of is assumed, so this nonnegative quantity need not be at most one. When , the sum has one term; if is empty, every term is zero.
QAlgorithms.Papers.Independent.Intakenext100.P77.wholeKeyInformation
For natural numbers , a finite type with decidable equality, an arbitrary family of complex vectors indexed by binary strings , a binary linear subspace , an offset , and vectors for , let be the binary string whose coordinate is true exactly when the corresponding coordinate of equals , and set
The defined real number is the real supremum, over every positive integer and every family of positive semidefinite matrices on satisfying , of
Here , pushforward weights are obtained by summing over fibers, and , using the total real logarithm, including . No normalization or other assumption on is required, so the weights in this formula need not sum to one. Both and are allowed; when , the key has a single possible value.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.