Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Depth-two tree: logical X and Z success probabilities

Open
QAlgorithms.Papers.Independent.Intakenext100.P89.depth_two_measurements

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Consider a regular tree with positive integer branching factors b0,b1b_0,b_1b0​,b1​. Every physical photon used in a measurement independently survives with probability p=1−ϵstat∈[0,1]p=1-\epsilon_{\rm stat}\in[0,1]p=1−ϵstat​∈[0,1]. The tree has b0b_0b0​ child groups, each comprising a child and its b1b_1b1​ grandchildren. Logical XXX succeeds if at least one group survives completely. Logical ZZZ succeeds if every group contains at least one surviving photon, allowing the child to be measured directly or indirectly. Then

PX=1−(1−pb1+1)b0,PZ=[1−(1−p)b1+1]b0.P_X=1-(1-p^{b_1+1})^{b_0},\qquad P_Z=\left[1-(1-p)^{b_1+1}\right]^{b_0}.PX​=1−(1−pb1​+1)b0​,PZ​=[1−(1−p)b1​+1]b0​.

These are the depth-two specializations of the indirect-measurement recursion. For the source's repeater, p=e−αL/nPchipk+2PfibηGHZηcp=e^{-\alpha L/n}P_{\rm chip}^{k+2}P_{\rm fib}\eta_{\rm GHZ}\eta_cp=e−αL/nPchipk+2​Pfib​ηGHZ​ηc​. No optimality of depth two is assumed.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P89
Formal statement
namespace QAlgorithms.Papers.Independent.Intakenext100.P89

open scoped BigOperators ComplexConjugate

-- Accepted probability primitives: symbol true is success; choose n x is zero for x > n.

open QAlgorithms.Papers.Independent.Information100.P54 (binomialMass)

open QAlgorithms.Papers.Independent.Information100.P56 (bernoulli)

noncomputable section

/-- Source p.11, IV, Eqs.(2)--(6): the depth-two specialization of the indirect-measurement
recursion with positive integral branches. Here p = 1-epsilon_stat is photon survival.
No optimality of depth two is asserted or assumed. -/
theorem depth_two_measurements (b0 b1 : ℕ) (hb0 : 0 < b0) (hb1 : 0 < b1)
    (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) :
    depthTwoLogicalXSuccess b0 b1 p = 1 - (1 - p ^ (b1 + 1)) ^ b0 ∧
    logicalZ b0 b1 p = (1 - (1 - p) ^ (b1 + 1)) ^ b0 := by sorry

end

end QAlgorithms.Papers.Independent.Intakenext100.P89
Source
Rate-distance tradeoff and resource costs for all-optical quantum repeaters, arXiv:1603.01353v4, PDF p. 11, IV, Eqs.(5)–(6): depth-two logical measurement probabilities
Read-back

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

For positive natural numbers b0,b1b_0,b_1b0​,b1​ and a real number ppp with 0≤p≤10\le p\le10≤p≤1, assign each Boolean array zzz with b0b_0b0​ rows and b1+1b_1+1b1​+1 columns the weight wp(z)=∏i=0b0−1∏j=0b1(p if zij=true, otherwise 1−p)w_p(z)=\prod_{i=0}^{b_0-1}\prod_{j=0}^{b_1}(p\text{ if }z_{ij}=\mathrm{true},\text{ otherwise }1-p)wp​(z)=∏i=0b0​−1​∏j=0b1​​(p if zij​=true, otherwise 1−p). The theorem asserts both

∑z∃i∀j, zij=truewp(z)=1−(1−pb1+1)b0,∑z∀i∃j, zij=truewp(z)=(1−(1−p)b1+1)b0.\sum_{\substack{z\\\exists i\;\forall j,\ z_{ij}=\mathrm{true}}}w_p(z) =1-\left(1-p^{b_1+1}\right)^{b_0}, \qquad \sum_{\substack{z\\\forall i\;\exists j,\ z_{ij}=\mathrm{true}}}w_p(z) =\left(1-(1-p)^{b_1+1}\right)^{b_0}.z∃i∀j, zij​=true​∑​wp​(z)=1−(1−pb1​+1)b0​,z∀i∃j, zij​=true​∑​wp​(z)=(1−(1−p)b1​+1)b0​.

The endpoint values p=0p=0p=0 and p=1p=1p=1 are included; neither b0=0b_0=0b0​=0 nor b1=0b_1=0b1​=0 is included.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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