Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Tight Finite-Key Analysis for Quantum Cryptography

Definition
QAlgorithms_Papers_Independent_Intakethird100_P01

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Tight Finite-Key Analysis for Quantum Cryptography (arXiv:1103.4130) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • StringPair: PDF p.13: a pair of total classical strings, with no independence assumption on their bits.
  • Sample: PDF p.13: the possible samples, exactly the k-element subsets of n+k positions.
  • SamplingOutcome: PDF p.13: the original strings and the independently drawn sample.
  • samplingWeight: PDF p.13: product of the input string law and the uniform law on k-subsets.
  • subsetEventProbability: PDF p.13: event probability in the product experiment; validity requires P>=0 and sum P=1.
  • sampleError: PDF p.13: relative Hamming distance on the test sample (used only with k>0).
  • complementErrorFraction: PDF p.13: relative Hamming distance on the complementary key positions (used with n>0).
  • complementaryString: PDF p.13: the complementary n positions, in their original increasing order.
  • passProbability: PDF p.13: passing parameter estimation means sample error at most Q_tol.
  • probabilityGivenPass: PDF p.13, (S11)--(S14): normalized conditional probability; the theorems require positive pass probability.
  • keyLawGivenPass: PDF pp.13--14, (S15): the conditioned marginal of the two key strings; Lambda is marginalized.
  • samplingFailureParameter: PDF p.13, (S13)--(S14): epsilon as a function of the nonnegative deviation mu.
  • samplingDeviation: PDF p.13, (S15): deviation with the paper's finite-population correction and natural logarithm.
  • truncatedBinaryEntropy: PDF p.12 footnote 1: binary entropy in bits, truncated to one above one half. The theorem only evaluates this function at nonnegative arguments.
  • logTwoExtended: Extended logarithm for nonnegative fidelity squares: zero has value minus infinity. This elementary helper is retained with its sanity example; entropy itself is imported.
  • classicalDensity: PDF p.13: embed the actual classical joint law as a diagonal density operator.
  • singletKet: PDF pp.9,11: accepted normalized singlet ket, with Bool coordinates relabeled false=0 and true=1. The emitted system is the second tensor factor.
  • singletMeasurementVector: PDF pp.9,11: the measurement vector (conj b,-conj a) that remotely prepares (a,b) from the singlet. The choice explicitly includes the singlet's conjugation and sign.
  • preparationEffect: PDF pp.9,11: rank-one effect on the measured half, constructed from a preparation basis.
  • singletContraction: PDF pp.9,11: unnormalized emitted vector after the rank-one measurement outcome v.
  • remoteBranch: PDF pp.9,11: the emitted branch density; its trace is the Born probability of the outcome.
  • RealizesUniformQubitBasis: PDF pp.3,9,11: the constructed projective measurement is complete and gives each outcome probability 1/2, with conditional emitted density equal to the desired preparation density.
  • fourMaximum: PDF pp.3--4: finite maximum over the four pairs of binary outcomes.
  • preparationOverlap: PDF p.3: maximum squared inner-product overlap of the two preparation bases.
  • preparationMeasurementOverlap: PDF pp.4,9,11: maximum squared L2 operator norm of the products of square-root effects. This uses the frozen operator norm, rather than the matrix entrywise norm.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P67
import Definitions.Def_QAlgorithms_Papers_Independent_Frontier18_P14

/-!
# Tight Finite-Key Analysis for Quantum Cryptography

arXiv:1103.4130v2. Independent statistical statements and the local qubit-source reduction.
Operational protocol nodes deferred in the accompanying HARD.md are deliberately absent.
New paper-specific constructions are local; matching frozen primitives are imported. Compilation is pending the mechanical handoff.
-/

namespace QAlgorithms.Papers.Independent.Intakethird100.P01

open scoped BigOperators ComplexConjugate ComplexOrder

-- Accepted extended entropy: the finite-real smoothing helper excludes radius >= 1.
open QAlgorithms.Papers.Independent.Information100.P67
  (IsSubnormalized purifiedDistance conditionalMaxEntropy smoothConditionalMaxEntropyExtended)

noncomputable section

/-- PDF p.13: a pair of total classical strings, with no independence assumption on their bits. -/
abbrev StringPair (N : ℕ) := Qubits N × Qubits N

/-- PDF p.13: the possible samples, exactly the k-element subsets of n+k positions. -/
abbrev Sample (n k : ℕ) := {s : Finset (Fin (n + k)) // s.card = k}

/-- PDF p.13: the original strings and the independently drawn sample. -/
abbrev SamplingOutcome (n k : ℕ) := StringPair (n + k) × Sample n k

/-- PDF p.13: product of the input string law and the uniform law on k-subsets. -/
def samplingWeight {n k : ℕ} (P : StringPair (n + k) → ℝ)
    (w : SamplingOutcome n k) : ℝ :=
  P w.1 / (Fintype.card (Sample n k) : ℝ)

/-- PDF p.13: event probability in the product experiment; validity requires P>=0 and sum P=1. -/
def subsetEventProbability {n k : ℕ} (P : StringPair (n + k) → ℝ)
    (event : SamplingOutcome n k → Prop) : ℝ := by
  classical
  exact ∑ w, if event w then samplingWeight P w else 0

/-- PDF p.13: relative Hamming distance on the test sample (used only with k>0). -/
def sampleError {n k : ℕ} (w : SamplingOutcome n k) : ℝ :=
  ((w.2.val.filter (fun i => w.1.1 i ≠ w.1.2 i)).card : ℝ) / (k : ℝ)

/-- PDF p.13: relative Hamming distance on the complementary key positions (used with n>0). -/
def complementErrorFraction {n k : ℕ} (w : SamplingOutcome n k) : ℝ :=
  (((w.2.valᶜ).filter (fun i => w.1.1 i ≠ w.1.2 i)).card : ℝ) / (n : ℝ)

/-- PDF p.13: the complementary n positions, in their original increasing order. -/
def complementaryString {n k : ℕ} (s : Sample n k) (z : Qubits (n + k)) : Qubits n :=
  fun i => z ((s.valᶜ).orderEmbOfFin (by
    rw [Finset.card_compl, Fintype.card_fin, s.property]
    omega) i)

/-- PDF p.13: passing parameter estimation means sample error at most Q_tol. -/
def passProbability {n k : ℕ} (P : StringPair (n + k) → ℝ) (Q : ℝ) : ℝ :=
  subsetEventProbability P (fun w => sampleError w ≤ Q)

/-- PDF p.13, (S11)--(S14): normalized conditional probability; the theorems require positive pass probability. -/
def probabilityGivenPass {n k : ℕ} (P : StringPair (n + k) → ℝ) (Q : ℝ)
    (event : SamplingOutcome n k → Prop) : ℝ :=
  subsetEventProbability P (fun w => sampleError w ≤ Q ∧ event w) / passProbability P Q

/-- PDF pp.13--14, (S15): the conditioned marginal of the two key strings; Lambda is marginalized. -/
def keyLawGivenPass {n k : ℕ} (P : StringPair (n + k) → ℝ) (Q : ℝ)
    (z : StringPair n) : ℝ :=
  probabilityGivenPass P Q (fun w =>
    (complementaryString w.2 w.1.1, complementaryString w.2 w.1.2) = z)

/-- PDF p.13, (S13)--(S14): epsilon as a function of the nonnegative deviation mu. -/
def samplingFailureParameter (n k : ℕ) (mu : ℝ) : ℝ :=
  Real.exp (-(((k : ℝ) * (n : ℝ)) / ((n : ℝ) + (k : ℝ))) *
    ((k : ℝ) / ((k : ℝ) + 1)) * mu ^ 2)

/-- PDF p.13, (S15): deviation with the paper's finite-population correction and natural logarithm. -/
def samplingDeviation (n k : ℕ) (epsilon : ℝ) : ℝ :=
  Real.sqrt ((((n : ℝ) + (k : ℝ)) / ((n : ℝ) * (k : ℝ))) *
    (((k : ℝ) + 1) / (k : ℝ)) * Real.log (1 / epsilon))

/-- PDF p.12 footnote 1: binary entropy in bits, truncated to one above one half.
The theorem only evaluates this function at nonnegative arguments. -/
def truncatedBinaryEntropy (t : ℝ) : ℝ :=
  if t ≤ 1 / 2 then binEntropy2 t else 1

/-- Extended logarithm for nonnegative fidelity squares: zero has value minus infinity.
This elementary helper is retained with its sanity example; entropy itself is imported. -/
def logTwoExtended (x : ℝ) : EReal :=
  if x ≤ 0 then ⊥ else (Real.logb 2 x : EReal)

/-- PDF p.13: embed the actual classical joint law as a diagonal density operator. -/
def classicalDensity {I : Type*} [DecidableEq I] (P : I → ℝ) : Matrix I I ℂ :=
  Matrix.diagonal (fun i => (P i : ℂ))

/-- PDF pp.9,11: accepted normalized singlet ket, with Bool coordinates relabeled
false=0 and true=1. The emitted system is the second tensor factor. -/
def singletKet : EuclideanSpace ℂ (Bool × Bool) :=
  WithLp.toLp 2 (fun p => QAlgorithms.Papers.Independent.Frontier18.P14.singlet
    (if p.1 then 1 else 0, if p.2 then 1 else 0))

/-- PDF pp.9,11: the measurement vector (conj b,-conj a) that remotely prepares (a,b)
from the singlet. The choice explicitly includes the singlet's conjugation and sign. -/
def singletMeasurementVector (psi : EuclideanSpace ℂ Bool) : EuclideanSpace ℂ Bool :=
  WithLp.toLp 2 (fun b => if b then -conj (psi false) else conj (psi true))

/-- PDF pp.9,11: rank-one effect on the measured half, constructed from a preparation basis. -/
def preparationEffect (B : Bool → EuclideanSpace ℂ Bool) (x : Bool) : Matrix Bool Bool ℂ :=
  pureDensity (singletMeasurementVector (B x))

/-- PDF pp.9,11: unnormalized emitted vector after the rank-one measurement outcome v. -/
def singletContraction (v : EuclideanSpace ℂ Bool) : EuclideanSpace ℂ Bool :=
  WithLp.toLp 2 (fun j => ∑ i : Bool, conj (v i) * singletKet (i, j))

/-- PDF pp.9,11: the emitted branch density; its trace is the Born probability of the outcome. -/
def remoteBranch (B : Bool → EuclideanSpace ℂ Bool) (x : Bool) : Matrix Bool Bool ℂ :=
  pureDensity (singletContraction (singletMeasurementVector (B x)))

/-- PDF pp.3,9,11: the constructed projective measurement is complete and gives each outcome
probability 1/2, with conditional emitted density equal to the desired preparation density. -/
def RealizesUniformQubitBasis (B : Bool → EuclideanSpace ℂ Bool) : Prop :=
  Orthonormal ℂ (fun x => singletMeasurementVector (B x)) ∧
    (∑ x : Bool, preparationEffect B x) = 1 ∧
    ∀ x : Bool, (preparationEffect B x).PosSemidef ∧
      preparationEffect B x * preparationEffect B x = preparationEffect B x ∧
      (remoteBranch B x).trace = (1 / 2 : ℂ) ∧
      (2 : ℂ) • remoteBranch B x = pureDensity (B x)

/-- PDF pp.3--4: finite maximum over the four pairs of binary outcomes. -/
def fourMaximum (f : Bool → Bool → ℝ) : ℝ :=
  max (max (f false false) (f false true)) (max (f true false) (f true true))

/-- PDF p.3: maximum squared inner-product overlap of the two preparation bases. -/
def preparationOverlap (X Z : Bool → EuclideanSpace ℂ Bool) : ℝ :=
  fourMaximum (fun x z => ‖inner ℂ (X x) (Z z)‖ ^ 2)

/-- PDF pp.4,9,11: maximum squared L2 operator norm of the products of square-root effects.
This uses the frozen operator norm, rather than the matrix entrywise norm. -/
def preparationMeasurementOverlap (X Z : Bool → EuclideanSpace ℂ Bool) : ℝ :=
  fourMaximum (fun x z =>
    specNorm (cfc Real.sqrt (preparationEffect X x) *
      cfc Real.sqrt (preparationEffect Z z)) ^ 2)

/-- Definition sanity: no deviation remains at epsilon=1. -/
example (n k : ℕ) : samplingDeviation n k 1 = 0 := by
  simp [samplingDeviation]

/-- Definition sanity: the tail parameter at zero deviation is exactly one. -/
example (n k : ℕ) : samplingFailureParameter n k 0 = 1 := by
  simp [samplingFailureParameter]

/-- Definition sanity: the entropy cap is one at error fraction one. -/
example : truncatedBinaryEntropy 1 = 1 := by
  norm_num [truncatedBinaryEntropy]

/-- Definition sanity: zero fidelity has extended logarithm minus infinity. -/
example : logTwoExtended 0 = ⊥ := by
  simp [logTwoExtended]

/-- Definition sanity: the classical embedding uses precisely the given diagonal weights. -/
example {I : Type*} [DecidableEq I] (P : I → ℝ) (i : I) :
    classicalDensity P i i = (P i : ℂ) := by
  simp [classicalDensity]

/-- Definition sanity: the singlet has no amplitude on |00>. -/
example : singletKet (false, false) = 0 := by
  simp [singletKet, QAlgorithms.Papers.Independent.Frontier18.P14.singlet]

/-- Definition sanity: the first measurement coordinate is conj b. -/
example (psi : EuclideanSpace ℂ Bool) :
    singletMeasurementVector psi false = conj (psi true) := rfl

/-- Definition sanity: the second measurement coordinate is -conj a. -/
example (psi : EuclideanSpace ℂ Bool) :
    singletMeasurementVector psi true = -conj (psi false) := rfl

end

end QAlgorithms.Papers.Independent.Intakethird100.P01
Source
Tight Finite-Key Analysis for Quantum Cryptography, arXiv:1103.4130v2, https://arxiv.org/abs/1103.4130v2
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Intakethird100.P01.RealizesUniformQubitBasis

For every function BBB assigning a complex Boolean-indexed Euclidean vector BxB_xBx​ to each Boolean value xxx, this predicate requires the following conjunction. Define Jx=(Bx(true)‾,−Bx(false)‾)J_x=(\overline{B_x(\mathrm{true})},-\overline{B_x(\mathrm{false})})Jx​=(Bx​(true)​,−Bx​(false)​) in Boolean order, Ex(a,b)=Jx(a)Jx(b)‾E_x(a,b)=J_x(a)\overline{J_x(b)}Ex​(a,b)=Jx​(a)Jx​(b)​, and Rx(a,b)=12Bx(a)Bx(b)‾R_x(a,b)=\tfrac12 B_x(a)\overline{B_x(b)}Rx​(a,b)=21​Bx​(a)Bx​(b)​. The two vectors Jfalse,JtrueJ_{\mathrm{false}},J_{\mathrm{true}}Jfalse​,Jtrue​ must be orthonormal for the usual complex inner product, their matrices must satisfy Efalse+Etrue=IE_{\mathrm{false}}+E_{\mathrm{true}}=IEfalse​+Etrue​=I, and for every Boolean xxx,

Ex⪰0,Ex2=Ex,Tr⁡Rx=12,2Rx=(Bx(a)Bx(b)‾)a,b.E_x\succeq0,\qquad E_x^2=E_x,\qquad \operatorname{Tr}R_x=\frac12,\qquad 2R_x=\bigl(B_x(a)\overline{B_x(b)}\bigr)_{a,b}.Ex​⪰0,Ex2​=Ex​,TrRx​=21​,2Rx​=(Bx​(a)Bx​(b)​)a,b​.

Here positive semidefiniteness is for complex matrices, and the trace equality is an equality in C\mathbb CC.

QAlgorithms.Papers.Independent.Intakethird100.P01.Sample

For all natural numbers n,kn,kn,k, Sample(n,k)\mathrm{Sample}(n,k)Sample(n,k) is the type of subsets s⊆{0,…,n+k−1}s\subseteq\{0,\ldots,n+k-1\}s⊆{0,…,n+k−1} having exactly kkk elements. Zero values are allowed: when k=0k=0k=0, the only sample is the empty set; when n=0n=0n=0, the only sample is the entire index set.

QAlgorithms.Papers.Independent.Intakethird100.P01.SamplingOutcome

For all natural numbers n,kn,kn,k, SamplingOutcome(n,k)\mathrm{SamplingOutcome}(n,k)SamplingOutcome(n,k) is the type of triples (x,y,s)(x,y,s)(x,y,s), where x,y:{0,…,n+k−1}→{false,true}x,y:\{0,\ldots,n+k-1\}\to\{\mathrm{false},\mathrm{true}\}x,y:{0,…,n+k−1}→{false,true} are Boolean strings and sss is a subset of their index set with exactly kkk elements. There are no restrictions on the strings or their relation to sss. This includes n=k=0n=k=0n=k=0, when there is exactly one outcome, consisting of two empty strings and the empty subset.

QAlgorithms.Papers.Independent.Intakethird100.P01.StringPair

For every natural number NNN, StringPair(N)\mathrm{StringPair}(N)StringPair(N) is the type of ordered pairs (x,y)(x,y)(x,y) of Boolean strings of length NNN; each string is a function from {0,…,N−1}\{0,\ldots,N-1\}{0,…,N−1} to {false,true}\{\mathrm{false},\mathrm{true}\}{false,true}. This includes N=0N=0N=0, when both strings are the unique empty string.

QAlgorithms.Papers.Independent.Intakethird100.P01.classicalDensity

For every index type III equipped with decidable equality and every function P:I→RP:I\to\mathbb RP:I→R, this defines the complex matrix ρP\rho_PρP​ indexed by III through

(ρP)ij={P(i),i=j,0,i≠j,(\rho_P)_{ij}= \begin{cases} P(i),&i=j,\\ 0,&i\ne j, \end{cases}(ρP​)ij​={P(i),0,​i=j,i=j,​

with real entries embedded into C\mathbb CC. There is no finiteness or nonemptiness assumption on III, and no nonnegativity or normalization assumption on PPP.

QAlgorithms.Papers.Independent.Intakethird100.P01.complementErrorFraction

For all natural numbers n,kn,kn,k and every outcome w=(x,y,s)w=(x,y,s)w=(x,y,s), where x,yx,yx,y are Boolean strings of length n+kn+kn+k and sss is a kkk-element subset of their index set, the complementary error fraction is

complementErrorFraction(w)=∣{i∈{0,…,n+k−1}∖s:x(i)≠y(i)}∣n,\mathrm{complementErrorFraction}(w) =\frac{|\{i\in\{0,\ldots,n+k-1\}\setminus s:x(i)\ne y(i)\}|}{n},complementErrorFraction(w)=n∣{i∈{0,…,n+k−1}∖s:x(i)=y(i)}∣​,

with the cardinality and denominator interpreted as real numbers. The complement has exactly nnn elements. When n=0n=0n=0, it is empty and the value is zero, using real division by zero equal to zero. The parameter kkk may also be zero.

QAlgorithms.Papers.Independent.Intakethird100.P01.complementaryString

For all natural numbers n,kn,kn,k, every kkk-element subset s⊆{0,…,n+k−1}s\subseteq\{0,\ldots,n+k-1\}s⊆{0,…,n+k−1}, and every Boolean string zzz of length n+kn+kn+k, list the nnn indices outside sss in increasing order as c0<⋯<cn−1c_0<\cdots<c_{n-1}c0​<⋯<cn−1​. The complementary string is the length-nnn Boolean string defined by

complementaryString(s,z)(i)=z(ci)(0≤i<n).\mathrm{complementaryString}(s,z)(i)=z(c_i) \qquad(0\le i<n).complementaryString(s,z)(i)=z(ci​)(0≤i<n).

When n=0n=0n=0, the result is the unique empty string; when k=0k=0k=0, it is zzz with all indices retained in their original order.

QAlgorithms.Papers.Independent.Intakethird100.P01.fourMaximum

For any function f:{false,true}2→Rf:\{\mathrm{false},\mathrm{true}\}^2\to\mathbb Rf:{false,true}2→R, this defines the real number

max⁡ ⁣(max⁡(f(false,false),f(false,true)), max⁡(f(true,false),f(true,true))).\max\!\bigl(\max(f(\mathrm{false},\mathrm{false}),f(\mathrm{false},\mathrm{true})),\, \max(f(\mathrm{true},\mathrm{false}),f(\mathrm{true},\mathrm{true}))\bigr).max(max(f(false,false),f(false,true)),max(f(true,false),f(true,true))).

QAlgorithms.Papers.Independent.Intakethird100.P01.keyLawGivenPass

For all natural numbers n,kn,kn,k, every real-valued function PPP on pairs of Boolean strings of length n+kn+kn+k, every real threshold QQQ, and every pair z=(u,v)z=(u,v)z=(u,v) of Boolean strings of length nnn, let x∣scx|_{s^c}x∣sc​ denote the string obtained by retaining the indices outside sss in increasing order. With e(x,y,s)=∣{i∈s:x(i)≠y(i)}∣/ke(x,y,s)=|\{i\in s:x(i)\ne y(i)\}|/ke(x,y,s)=∣{i∈s:x(i)=y(i)}∣/k, the definition is

keyLawGivenPass(P,Q,(u,v))=∑x,y, s: ∣s∣=ke(x,y,s)≤Qx∣sc=u, y∣sc=vP(x,y)(n+kk)∑x,y, s: ∣s∣=ke(x,y,s)≤QP(x,y)(n+kk).\mathrm{keyLawGivenPass}(P,Q,(u,v)) = \frac{\displaystyle \sum_{\substack{x,y,\ s:\ |s|=k\\e(x,y,s)\le Q\\ x|_{s^c}=u,\ y|_{s^c}=v}} \frac{P(x,y)}{\binom{n+k}{k}}} {\displaystyle \sum_{\substack{x,y,\ s:\ |s|=k\\e(x,y,s)\le Q}} \frac{P(x,y)}{\binom{n+k}{k}}}.keyLawGivenPass(P,Q,(u,v))=x,y, s: ∣s∣=ke(x,y,s)≤Q​∑​(kn+k​)P(x,y)​x,y, s: ∣s∣=ke(x,y,s)≤Qx∣sc​=u, y∣sc​=v​∑​(kn+k​)P(x,y)​​.

Here s⊆{0,…,n+k−1}s\subseteq\{0,\ldots,n+k-1\}s⊆{0,…,n+k−1}, and all string pairs are included in the sums. No nonnegativity or normalization of PPP, restriction on QQQ, or nonzero-denominator hypothesis is imposed; a zero denominator gives value zero. When k=0k=0k=0, the sample error is zero; when n=0n=0n=0, both retained strings are empty.

QAlgorithms.Papers.Independent.Intakethird100.P01.logTwoExtended

For every real number xxx, this defines an extended real number by

logTwoExtended⁡(x)={−∞,x≤0,log⁡2x,x>0,\operatorname{logTwoExtended}(x)= \begin{cases} -\infty,&x\le 0,\\ \log_2 x,&x>0, \end{cases}logTwoExtended(x)={−∞,log2​x,​x≤0,x>0,​

where the second branch embeds the finite real logarithm into the extended real numbers.

QAlgorithms.Papers.Independent.Intakethird100.P01.passProbability

For all natural numbers n,kn,kn,k, every real-valued function PPP on pairs of Boolean strings of length n+kn+kn+k, and every real threshold QQQ, define

passProbability(P,Q)=∑x,y, s∣s∣=k∣{i∈s:x(i)≠y(i)}∣/k≤QP(x,y)(n+kk),\mathrm{passProbability}(P,Q) =\sum_{\substack{x,y,\ s\\ |s|=k\\ |\{i\in s:x(i)\ne y(i)\}|/k\le Q}} \frac{P(x,y)}{\binom{n+k}{k}},passProbability(P,Q)=x,y, s∣s∣=k∣{i∈s:x(i)=y(i)}∣/k≤Q​∑​(kn+k​)P(x,y)​,

where sss ranges over subsets of {0,…,n+k−1}\{0,\ldots,n+k-1\}{0,…,n+k−1}. No nonnegativity or normalization of PPP, or restriction on QQQ, is assumed. The error quotient is zero when k=0k=0k=0, so in that case every outcome passes exactly when Q≥0Q\ge0Q≥0. For any kkk, if Q<0Q<0Q<0, no outcome passes and the value is zero. The parameter nnn may be zero.

QAlgorithms.Papers.Independent.Intakethird100.P01.preparationEffect

For every function BBB assigning a complex Boolean-indexed Euclidean vector BxB_xBx​ to each Boolean value xxx, and every Boolean xxx, this defines the matrix

Ex(a,b)=(JBx)(a) (JBx)(b)‾,E_x(a,b)=(JB_x)(a)\,\overline{(JB_x)(b)},Ex​(a,b)=(JBx​)(a)(JBx​)(b)​,

where (JBx)(false)=Bx(true)‾(JB_x)(\mathrm{false})=\overline{B_x(\mathrm{true})}(JBx​)(false)=Bx​(true)​ and (JBx)(true)=−Bx(false)‾(JB_x)(\mathrm{true})=-\overline{B_x(\mathrm{false})}(JBx​)(true)=−Bx​(false)​. No normalization or orthogonality assumption on the two vectors assigned by BBB is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P01.preparationMeasurementOverlap

For arbitrary families X,Z:{false,true}→C2X,Z:\{\mathrm{false},\mathrm{true}\}\to\mathbb C^2X,Z:{false,true}→C2, define, for either family BBB and each Boolean xxx, the vector vB,xv_{B,x}vB,x​ by vB,x(false)=Bx(true)‾v_{B,x}(\mathrm{false})=\overline{B_x(\mathrm{true})}vB,x​(false)=Bx​(true)​ and vB,x(true)=−Bx(false)‾v_{B,x}(\mathrm{true})=-\overline{B_x(\mathrm{false})}vB,x​(true)=−Bx​(false)​, and the matrix PB,x(i,j)=vB,x(i)vB,x(j)‾P_{B,x}(i,j)=v_{B,x}(i)\overline{v_{B,x}(j)}PB,x​(i,j)=vB,x​(i)vB,x​(j)​. The declaration defines

max⁡x,z∈{false,true}∥PX,x PZ,z∥op2,\max_{x,z\in\{\mathrm{false},\mathrm{true}\}} \left\|\sqrt{P_{X,x}}\,\sqrt{P_{Z,z}}\right\|_{\mathrm{op}}^2,x,z∈{false,true}max​​PX,x​​PZ,z​​​op2​,

where each matrix square root is obtained by continuous functional calculus with the real square-root function, and the norm is the Euclidean operator norm. No normalization or orthogonality is assumed; the matrices PB,xP_{B,x}PB,x​ need not be projections.

QAlgorithms.Papers.Independent.Intakethird100.P01.preparationOverlap

For arbitrary families X,Z:{false,true}→C2X,Z:\{\mathrm{false},\mathrm{true}\}\to\mathbb C^2X,Z:{false,true}→C2, where vector coordinates are indexed by Booleans, this defines

max⁡x,z∈{false,true}∣⟨Xx,Zz⟩∣2.\max_{x,z\in\{\mathrm{false},\mathrm{true}\}} \left|\langle X_x,Z_z\rangle\right|^2.x,z∈{false,true}max​∣⟨Xx​,Zz​⟩∣2.

The inner product is the standard complex Euclidean inner product, conjugate-linear in its first argument. No normalization or orthogonality is assumed; zero vectors are permitted.

QAlgorithms.Papers.Independent.Intakethird100.P01.probabilityGivenPass

For all natural numbers n,kn,kn,k, every real-valued function PPP on pairs of Boolean strings of length n+kn+kn+k, every real number QQQ, and every predicate E\mathcal EE on outcomes w=(x,y,s)w=(x,y,s)w=(x,y,s) with ∣s∣=k|s|=k∣s∣=k, set e(w)=∣{i∈s:x(i)≠y(i)}∣/ke(w)=|\{i\in s:x(i)\ne y(i)\}|/ke(w)=∣{i∈s:x(i)=y(i)}∣/k and a(w)=P(x,y)/(n+kk)a(w)=P(x,y)/\binom{n+k}{k}a(w)=P(x,y)/(kn+k​). The definition is

probabilityGivenPass(P,Q,E)=∑we(w)≤QE(w)a(w)∑we(w)≤Qa(w).\mathrm{probabilityGivenPass}(P,Q,\mathcal E) =\frac{\displaystyle\sum_{\substack{w\\e(w)\le Q\\\mathcal E(w)}}a(w)} {\displaystyle\sum_{\substack{w\\e(w)\le Q}}a(w)}.probabilityGivenPass(P,Q,E)=we(w)≤Q​∑​a(w)we(w)≤QE(w)​∑​a(w)​.

Both sums range over all string pairs and kkk-element subsets. No probability assumptions on PPP, decidability assumption on E\mathcal EE, or positivity assumption on the denominator is required. If the denominator is zero, the value is zero by real division by zero. Zero parameters are allowed, and e(w)=0e(w)=0e(w)=0 when k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakethird100.P01.remoteBranch

For every function BBB assigning a complex Boolean-indexed Euclidean vector BxB_xBx​ to each Boolean value xxx, and every Boolean xxx, this defines the matrix Rx(a,b)=cx(a)cx(b)‾R_x(a,b)=c_x(a)\overline{c_x(b)}Rx​(a,b)=cx​(a)cx​(b)​, where cxc_xcx​ is obtained by first forming the vector (Bx(true)‾,−Bx(false)‾)(\overline{B_x(\mathrm{true})},-\overline{B_x(\mathrm{false})})(Bx​(true)​,−Bx​(false)​) in the order (false,true)(\mathrm{false},\mathrm{true})(false,true), then contracting its conjugated coefficients against the vector with coefficients s(false,true)=1/2s(\mathrm{false},\mathrm{true})=1/\sqrt2s(false,true)=1/2​, s(true,false)=−1/2s(\mathrm{true},\mathrm{false})=-1/\sqrt2s(true,false)=−1/2​, and zero otherwise. Explicitly,

cx(a)=Bx(a)2,Rx(a,b)=12Bx(a)Bx(b)‾.c_x(a)=\frac{B_x(a)}{\sqrt2}, \qquad R_x(a,b)=\frac12 B_x(a)\overline{B_x(b)}.cx​(a)=2​Bx​(a)​,Rx​(a,b)=21​Bx​(a)Bx​(b)​.

No normalization or orthogonality assumption on BBB is required.

QAlgorithms.Papers.Independent.Intakethird100.P01.sampleError

For all natural numbers n,kn,kn,k and every outcome w=(x,y,s)w=(x,y,s)w=(x,y,s), where x,yx,yx,y are Boolean strings of length n+kn+kn+k and sss is a kkk-element subset of their index set, the sample error is

sampleError(w)=∣{i∈s:x(i)≠y(i)}∣k,\mathrm{sampleError}(w) =\frac{|\{i\in s:x(i)\ne y(i)\}|}{k},sampleError(w)=k∣{i∈s:x(i)=y(i)}∣​,

with the cardinality and denominator interpreted as real numbers. When k=0k=0k=0, the sample is empty and the value is zero, using the convention that division by zero in R\mathbb RR yields zero. The parameter nnn may also be zero.

QAlgorithms.Papers.Independent.Intakethird100.P01.samplingDeviation

For every pair of natural numbers n,kn,kn,k, including zero, and every real number ϵ\epsilonϵ, this defines

samplingDeviation⁡(n,k,ϵ)=n+knk k+1k ln⁡(1/ϵ).\operatorname{samplingDeviation}(n,k,\epsilon) =\sqrt{\frac{n+k}{nk}\,\frac{k+1}{k}\,\ln(1/\epsilon)}.samplingDeviation(n,k,ϵ)=nkn+k​kk+1​ln(1/ϵ)​.

All arithmetic inside the square root is real arithmetic. Division by zero is defined to give zero, the real logarithm satisfies ln⁡0=0\ln 0=0ln0=0 and ln⁡x=ln⁡∣x∣\ln x=\ln|x|lnx=ln∣x∣ for negative xxx, and the real square root of a nonpositive number is zero. In particular, the value is zero if n=0n=0n=0, k=0k=0k=0, or ϵ=0\epsilon=0ϵ=0; no positivity or probability-range assumption on ϵ\epsilonϵ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P01.samplingFailureParameter

For all natural numbers n,kn,kn,k and every real number μ\muμ, the sampling failure parameter is defined by

samplingFailureParameter(n,k,μ)=exp⁡ ⁣(−knn+k kk+1 μ2),\mathrm{samplingFailureParameter}(n,k,\mu) =\exp\!\left( -\frac{kn}{n+k}\,\frac{k}{k+1}\,\mu^2 \right),samplingFailureParameter(n,k,μ)=exp(−n+kkn​k+1k​μ2),

where all natural numbers in the expression are interpreted as real numbers. No positivity assumption on n,kn,kn,k, or μ\muμ, is imposed. Real division by zero is zero, so the value is 111 whenever n=0n=0n=0 or k=0k=0k=0, including n=k=0n=k=0n=k=0; it is also 111 when μ=0\mu=0μ=0.

QAlgorithms.Papers.Independent.Intakethird100.P01.samplingWeight

For all natural numbers n,kn,kn,k, every real-valued function PPP on ordered pairs of Boolean strings of length n+kn+kn+k, and every outcome w=(x,y,s)w=(x,y,s)w=(x,y,s) with ∣s∣=k|s|=k∣s∣=k, the sampling weight is defined by

samplingWeight(P,w)=P(x,y)(n+kk).\mathrm{samplingWeight}(P,w)=\frac{P(x,y)}{\binom{n+k}{k}}.samplingWeight(P,w)=(kn+k​)P(x,y)​.

The denominator counts all kkk-element subsets of the index set and is positive, including when n=0n=0n=0 or k=0k=0k=0. No nonnegativity or normalization assumption is imposed on PPP.

QAlgorithms.Papers.Independent.Intakethird100.P01.singletContraction

For every complex Euclidean vector vvv indexed by Boolean values, this defines the Boolean-indexed vector cvc_vcv​ by

cv(j)=∑i∈{false,true}v(i)‾ s(i,j),c_v(j)=\sum_{i\in\{\mathrm{false},\mathrm{true}\}}\overline{v(i)}\,s(i,j),cv​(j)=i∈{false,true}∑​v(i)​s(i,j),

where s(false,true)=1/2s(\mathrm{false},\mathrm{true})=1/\sqrt2s(false,true)=1/2​, s(true,false)=−1/2s(\mathrm{true},\mathrm{false})=-1/\sqrt2s(true,false)=−1/2​, and its other coefficients are zero. Equivalently,

cv(false)=−v(true)‾2,cv(true)=v(false)‾2.c_v(\mathrm{false})=-\frac{\overline{v(\mathrm{true})}}{\sqrt2}, \qquad c_v(\mathrm{true})=\frac{\overline{v(\mathrm{false})}}{\sqrt2}.cv​(false)=−2​v(true)​​,cv​(true)=2​v(false)​​.

There is no normalization assumption on vvv.

QAlgorithms.Papers.Independent.Intakethird100.P01.singletKet

This defines the vector s∈C{false,true}2s\in\mathbb C^{\{\mathrm{false},\mathrm{true}\}^2}s∈C{false,true}2 with the Euclidean norm by

s(false,true)=12,s(true,false)=−12,s(false,false)=s(true,true)=0.s(\mathrm{false},\mathrm{true})=\frac1{\sqrt2}, \qquad s(\mathrm{true},\mathrm{false})=-\frac1{\sqrt2}, \qquad s(\mathrm{false},\mathrm{false})=s(\mathrm{true},\mathrm{true})=0.s(false,true)=2​1​,s(true,false)=−2​1​,s(false,false)=s(true,true)=0.

Thus, writing ∣a,b⟩|a,b\rangle∣a,b⟩ for the vector with coefficient one at (a,b)(a,b)(a,b) and zero elsewhere, it is (∣false,true⟩−∣true,false⟩)/2(|\mathrm{false},\mathrm{true}\rangle-|\mathrm{true},\mathrm{false}\rangle)/\sqrt2(∣false,true⟩−∣true,false⟩)/2​.

QAlgorithms.Papers.Independent.Intakethird100.P01.singletMeasurementVector

For every complex Euclidean vector ψ\psiψ indexed by the two Boolean values, this defines the vector JψJ\psiJψ by

(Jψ)(false)=ψ(true)‾,(Jψ)(true)=−ψ(false)‾.(J\psi)(\mathrm{false})=\overline{\psi(\mathrm{true})}, \qquad (J\psi)(\mathrm{true})=-\overline{\psi(\mathrm{false})}.(Jψ)(false)=ψ(true)​,(Jψ)(true)=−ψ(false)​.

No normalization assumption on ψ\psiψ is required.

QAlgorithms.Papers.Independent.Intakethird100.P01.subsetEventProbability

For all natural numbers n,kn,kn,k, every real-valued function PPP on pairs of Boolean strings of length n+kn+kn+k, and every predicate E\mathcal EE on triples (x,y,s)(x,y,s)(x,y,s) with s⊆{0,…,n+k−1}s\subseteq\{0,\ldots,n+k-1\}s⊆{0,…,n+k−1} and ∣s∣=k|s|=k∣s∣=k, the definition is

subsetEventProbability(P,E)=∑x,y, s∣s∣=kE(x,y,s)P(x,y)(n+kk).\mathrm{subsetEventProbability}(P,\mathcal E) =\sum_{\substack{x,y,\ s\\ |s|=k\\ \mathcal E(x,y,s)}} \frac{P(x,y)}{\binom{n+k}{k}}.subsetEventProbability(P,E)=x,y, s∣s∣=kE(x,y,s)​∑​(kn+k​)P(x,y)​.

The sum ranges over all such string pairs and subsets. The predicate is arbitrary, with no supplied decidability assumption required. Neither nonnegativity nor normalization of PPP is assumed, so the resulting real number need not be a probability. An empty event gives zero; n=0n=0n=0 and k=0k=0k=0 are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P01.truncatedBinaryEntropy

For every real number ttt, this defines

htr(t)={−tln⁡t−(1−t)ln⁡(1−t)ln⁡2,t≤12,1,t>12.h_{\mathrm{tr}}(t)= \begin{cases} \dfrac{-t\ln t-(1-t)\ln(1-t)}{\ln 2},&t\le \tfrac12,\\[4pt] 1,&t>\tfrac12. \end{cases}htr​(t)=⎩⎨⎧​ln2−tlnt−(1−t)ln(1−t)​,1,​t≤21​,t>21​.​

Here the logarithm is the total real logarithm, with ln⁡0=0\ln 0=0ln0=0 and ln⁡x=ln⁡∣x∣\ln x=\ln|x|lnx=ln∣x∣ for negative xxx. The argument ttt is unrestricted: the first branch includes negative values, and the second branch includes every value greater than 12\tfrac1221​, including values greater than one.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me