Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8: composite probability, closure, commutation and independence

Open
QAlgorithms.Papers.Independent.Intakethird100.P03.measurement_composition

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

prove2quantum

Fix an orthogonal family Ω\OmegaΩ with support NNN. A measurement acts on each subspace VVV by the identity on the measured system and an ancillary unitary UVU_VUV​, with a specified output subregister. For any normalized ∣ξ⟩∈N|\xi\rangle\in N∣ξ⟩∈N,

Pr⁡[y]=∑V∈ΩP(ξ,V)PU,C(V,y).\Pr[y]=\sum_{V\in\Omega}P(\xi,V)P_{U,C}(V,y).Pr[y]=V∈Ω∑​P(ξ,V)PU,C​(V,y).

Products of measurement operators remain measurement operators. Operators with disjoint ancillary registers commute, even though they share the measured system. For two such measurements,

PU′U′′,C′∪C′′(V,(y′,y′′))=PU′,C′(V,y′)PU′′,C′′(V,y′′).P_{U'U'',C'\cup C''}(V,(y',y''))=P_{U',C'}(V,y')P_{U'',C''}(V,y'').PU′U′′,C′∪C′′​(V,(y′,y′′))=PU′,C′​(V,y′)PU′′,C′′​(V,y′′).

The independence is conditional on VVV, not unconditional independence for a superposition of eigenspaces.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate Kronecker

namespace QAlgorithms.Papers.Independent.Intakethird100.P03

open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)

attribute [local instance] Classical.propDecidable

/-- PDF pp.16–17, Lemma 8, all clauses: mixture probabilities, closure under products,
commutation on disjoint ancillary registers, and independence conditional on the eigenspace.
The measured system I is shared. -/
theorem measurement_composition {I : Type*} [Fintype I] [DecidableEq I]
    (r d m e t : ℕ) (O : OrthogonalProjectorFamily I r)
    (V W : Fin r → Matrix (Qubits d) (Qubits d) ℂ)
    (Z : Fin r → Matrix (Qubits e) (Qubits e) ℂ)
    (C : Fin m ↪ Fin d) (D : Fin t ↪ Fin e)
    (hV : ∀ v, V v ∈ Matrix.unitaryGroup (Qubits d) ℂ)
    (hW : ∀ v, W v ∈ Matrix.unitaryGroup (Qubits d) ℂ)
    (hZ : ∀ v, Z v ∈ Matrix.unitaryGroup (Qubits e) ℂ) :
    (∀ (x : EuclideanSpace ℂ I), IsState x → act O.support x = x → ∀ y : Qubits m,
      probEvent (act (measurementMatrix O V) (tensorVec x (zeroKet d)))
        (fun z => z.2 ∘ C = y) =
      ∑ v, subspaceProbability (pureDensity x) (O.proj v) * eigenspaceOutcomeProbability V C v y) ∧
    measurementMatrix O V * measurementMatrix O W = measurementMatrix O (fun v => V v * W v) ∧
    (∀ v, V v * W v ∈ Matrix.unitaryGroup (Qubits d) ℂ) ∧
    firstMeasurement (K := Qubits e) O V * secondMeasurement (J := Qubits d) O Z =
      secondMeasurement (J := Qubits d) O Z * firstMeasurement (K := Qubits e) O V ∧
    (∀ (v : Fin r) (y : Qubits m) (z : Qubits t),
      probEvent (act (V v ⊗ₖ Z v) (tensorVec (zeroKet d) (zeroKet e)))
        (fun p => p.1 ∘ C = y ∧ p.2 ∘ D = z) =
        eigenspaceOutcomeProbability V C v y * eigenspaceOutcomeProbability Z D v z) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P03

end
Source
Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1, PDF p. 16, Lemma 8: composite probability, closure, commutation and independence
Read-back

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

Let III be a finite index type with decidable equality, let r,d,m,e,t∈Nr,d,m,e,t\in\mathbb Nr,d,m,e,t∈N, and put Bk={0,1}kB_k=\{0,1\}^kBk​={0,1}k. Let (Pv)v<r(P_v)_{v<r}(Pv​)v<r​ be Hermitian idempotent complex matrices on III with PvPu=0P_vP_u=0Pv​Pu​=0 for v≠uv\ne uv=u, and put S=∑v<rPvS=\sum_{v<r}P_vS=∑v<r​Pv​. Let (Vv)v<r(V_v)_{v<r}(Vv​)v<r​ and (Wv)v<r(W_v)_{v<r}(Wv​)v<r​ be unitary matrices on BdB_dBd​, let (Zv)v<r(Z_v)_{v<r}(Zv​)v<r​ be unitary matrices on BeB_eBe​, and let C:{0,…,m−1}↪{0,…,d−1}C:\{0,\ldots,m-1\}\hookrightarrow\{0,\ldots,d-1\}C:{0,…,m−1}↪{0,…,d−1} and D:{0,…,t−1}↪{0,…,e−1}D:\{0,\ldots,t-1\}\hookrightarrow\{0,\ldots,e-1\}D:{0,…,t−1}↪{0,…,e−1} be injections. For any family AvA_vAv​ of matrices on a finite index set JJJ, define MP(A)=∑vPv⊗Av+(II−S)⊗IJM_P(A)=\sum_vP_v\otimes A_v+(I_I-S)\otimes I_JMP​(A)=∑v​Pv​⊗Av​+(II​−S)⊗IJ​, and write pA(v,y)=∑z∘C=y∣(Av∣0d⟩)z∣2p_A(v,y)=\sum_{z\circ C=y}|(A_v|0^d\rangle)_z|^2pA​(v,y)=∑z∘C=y​∣(Av​∣0d⟩)z​∣2 when AvA_vAv​ acts on BdB_dBd​, with the corresponding definition using DDD and eee for ZZZ. Then all five assertions hold:

∀x∈CI,∥x∥2=1, Sx=x ⟹ ∀y∈Bm,∑(i,z)∈I×Bdz∘C=y∣(MP(V)(x⊗∣0d⟩))(i,z)∣2=∑v<rRe⁡tr⁡(xx†Pv) pV(v,y);MP(V)MP(W)=MP((VvWv)v<r);∀v<r,VvWv is unitary;M1M2=M2M1,M1=∑vPv⊗(Vv⊗IBe)+(II−S)⊗IBd×Be,M2=∑vPv⊗(IBd⊗Zv)+(II−S)⊗IBd×Be;∀v<r, ∀y∈Bm, ∀z∈Bt,∑(u,h)∈Bd×Beu∘C=y, h∘D=z∣((Vv⊗Zv)(∣0d⟩⊗∣0e⟩))(u,h)∣2=pV(v,y) pZ(v,z).\begin{gathered} \forall x\in\mathbb C^I,\quad \|x\|_2=1,\ Sx=x \ \Longrightarrow\ \forall y\in B_m,\quad \sum_{\substack{(i,z)\in I\times B_d\\z\circ C=y}} \left|\bigl(M_P(V)(x\otimes|0^d\rangle)\bigr)_{(i,z)}\right|^2 =\sum_{v<r}\operatorname{Re}\operatorname{tr}(xx^\dagger P_v)\,p_V(v,y); \\ M_P(V)M_P(W)=M_P\bigl((V_vW_v)_{v<r}\bigr); \qquad \forall v<r,\quad V_vW_v\text{ is unitary}; \\ M_1M_2=M_2M_1,\quad M_1=\sum_vP_v\otimes(V_v\otimes I_{B_e})+(I_I-S)\otimes I_{B_d\times B_e}, \quad M_2=\sum_vP_v\otimes(I_{B_d}\otimes Z_v)+(I_I-S)\otimes I_{B_d\times B_e}; \\ \forall v<r,\ \forall y\in B_m,\ \forall z\in B_t,\quad \sum_{\substack{(u,h)\in B_d\times B_e\\u\circ C=y,\ h\circ D=z}} \left|\bigl((V_v\otimes Z_v)(|0^d\rangle\otimes|0^e\rangle)\bigr)_{(u,h)}\right|^2 =p_V(v,y)\,p_Z(v,z). \end{gathered}∀x∈CI,∥x∥2​=1, Sx=x ⟹ ∀y∈Bm​,(i,z)∈I×Bd​z∘C=y​∑​​(MP​(V)(x⊗∣0d⟩))(i,z)​​2=v<r∑​Retr(xx†Pv​)pV​(v,y);MP​(V)MP​(W)=MP​((Vv​Wv​)v<r​);∀v<r,Vv​Wv​ is unitary;M1​M2​=M2​M1​,M1​=v∑​Pv​⊗(Vv​⊗IBe​​)+(II​−S)⊗IBd​×Be​​,M2​=v∑​Pv​⊗(IBd​​⊗Zv​)+(II​−S)⊗IBd​×Be​​;∀v<r, ∀y∈Bm​, ∀z∈Bt​,(u,h)∈Bd​×Be​u∘C=y, h∘D=z​∑​​((Vv​⊗Zv​)(∣0d⟩⊗∣0e⟩))(u,h)​​2=pV​(v,y)pZ​(v,z).​

Here ∣0k⟩|0^k\rangle∣0k⟩ is the coordinate vector of the all-false string, (a⊗b)(i,j)=aibj(a\otimes b)_{(i,j)}=a_ib_j(a⊗b)(i,j)​=ai​bj​, and xx†xx^\daggerxx† has entries xixj‾x_i\overline{x_j}xi​xj​​. The projector sum SSS need not be the identity. Zero register lengths and r=0r=0r=0 are included; when r=0r=0r=0, the first assertion has no norm-one vector satisfying Sx=xSx=xSx=x, and assertions quantified over vvv are vacuous.

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