Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Pauli measurements: conditional-Z and Hadamard reordering instruments

Proved
QAlgorithms.Papers.Independent.Intakenext100.P89.appendix_pauli_reordering

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

prove2quantum

Let RRR be any finite nonempty unmeasured register, including arbitrary spectators, and let all input density operators be positive with trace one. Let {Mo}o∈O\{M_o\}_{o\in O}{Mo​}o∈O​ be any earlier measurement of qubit aaa, with a finite nonempty outcome set and ∑oMo†Mo=I\sum_oM_o^\dagger M_o=I∑o​Mo†​Mo​=I. Its outcome ooo controls Zi(o)Z^{i(o)}Zi(o) on a distinct qubit bbb. A later unitary Uo,rU_{o,r}Uo,r​ on RRR is controlled by ooo and by the Pauli outcome r∈{0,1}r\in\{0,1\}r∈{0,1} on bbb; outcome zero means eigenvalue +1+1+1. Write Lo,rA\mathcal L_{o,r}^{A}Lo,rA​ for the subnormalized residual branch after this sequence, discarding a,ba,ba,b. Define fX(i)=fY(i)=if_X(i)=f_Y(i)=ifX​(i)=fY​(i)=i and fZ(i)=0f_Z(i)=0fZ​(i)=0. Let Eo,tA\mathcal E_{o,t}^{A}Eo,tA​ instead measure bbb before the earlier measurement, omit Zi(o)Z^{i(o)}Zi(o), and apply Uo,t⊕fA(i(o))U_{o,t\oplus f_A(i(o))}Uo,t⊕fA​(i(o))​. Then, for every joint input state,

Lo,rA=Eo,r⊕fA(i(o))A(A=X,Y,Z).\mathcal L_{o,r}^{A}=\mathcal E_{o,r\oplus f_A(i(o))}^{A}\qquad(A=X,Y,Z).Lo,rA​=Eo,r⊕fA​(i(o))A​(A=X,Y,Z).

For the Hadamard identities, let PA,r=(I+(−1)rA)/2P_{A,r}=(I+(-1)^rA)/2PA,r​=(I+(−1)rA)/2, set h(X)=Z,h(Z)=X,h(Y)=Yh(X)=Z,h(Z)=X,h(Y)=Yh(X)=Z,h(Z)=X,h(Y)=Y and g(X)=g(Z)=0,g(Y)=1g(X)=g(Z)=0,g(Y)=1g(X)=g(Z)=0,g(Y)=1. If Tr⁡b\operatorname{Tr}_bTrb​ discards the measured qubit, then for every density σ\sigmaσ on bRbRbR,

Tr⁡b ⁣[(PA,rH⊗I)σ(PA,rH⊗I)†]=Tr⁡b ⁣[(Ph(A),r⊕g(A)⊗I)σ(Ph(A),r⊕g(A)⊗I)].\operatorname{Tr}_b\!\left[(P_{A,r}H\otimes I)\sigma(P_{A,r}H\otimes I)^\dagger\right]=\operatorname{Tr}_b\!\left[(P_{h(A),r\oplus g(A)}\otimes I)\sigma(P_{h(A),r\oplus g(A)}\otimes I)\right].Trb​[(PA,r​H⊗I)σ(PA,r​H⊗I)†]=Trb​[(Ph(A),r⊕g(A)​⊗I)σ(Ph(A),r⊕g(A)​⊗I)].

These identities include removal of ZZZ before a ZZZ measurement and the sign reversal for a YYY measurement after HHH. They preserve the joint outcome laws and residual states through the branch traces, not the measured output vectors. They make no assertion about equal loss accrued under different physical measurement times.

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

/-- Appendix A p.15, Fig.8(a)--(c): all conditional-Z and Hadamard measurement identities,
including the corrected downstream control of U. Equality is of subnormalized residual
branches after disposing of measured photons, hence of joint outcome probabilities and
residual states, with arbitrary finite references. No equality of measured output vectors
or time-dependent lossy hardware channels is asserted. -/
theorem appendix_pauli_reordering {O R : Type*} [Fintype O] [Nonempty O]
    [Fintype R] [DecidableEq R] [Nonempty R]
    (MA : O → Matrix Bool Bool ℂ)
    (hMA : ∑ o, (MA o).conjTranspose * MA o = 1)
    (feed : O → Bool) (U : O → Bool → Matrix.unitaryGroup R ℂ) :
    (∀ (rho : Matrix ((Bool × Bool) × R) ((Bool × Bool) × R) ℂ),
      QAlgorithms.IsDensityMatrix rho → ∀ (a : PauliBasis) (o : O) (r : Bool),
        latePauliBranch MA feed U a o r rho =
          earlyPauliBranch MA feed U a o (xor r (zOutcomeFlip a (feed o))) rho) ∧
    (∀ (rho : Matrix (Bool × R) (Bool × R) ℂ), QAlgorithms.IsDensityMatrix rho →
      ∀ (a : PauliBasis) (r : Bool),
        effectDiscard (QAlgorithms.hadamard.conjTranspose * pauliProjector a r *
          QAlgorithms.hadamard) rho =
        effectDiscard (pauliProjector (hadamardBasis a)
          (xor r (hadamardOutcomeFlip a))) rho) := 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. 15, Appendix A, Fig.8(a)–(c): Pauli measurement and feedforward identities
Read-back

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

For every finite nonempty type OOO, every finite nonempty type RRR with decidable equality, every family of complex 2×22\times22×2 matrices MoM_oMo​ satisfying ∑o∈OMo†Mo=I2\sum_{o\in O}M_o^\dagger M_o=I_2∑o∈O​Mo†​Mo​=I2​, every Boolean function f:O→{false,true}f:O\to\{\mathrm{false},\mathrm{true}\}f:O→{false,true}, and every family of unitary matrices Uo,bU_{o,b}Uo,b​ on CR\mathbb C^RCR, the following two assertions hold. Use Boolean order false,true\mathrm{false},\mathrm{true}false,true, let σX=(0110)\sigma_X=\begin{pmatrix}0&1\\1&0\end{pmatrix}σX​=(01​10​), σY=(0−ii0)\sigma_Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}σY​=(0i​−i0​), σZ=(100−1)\sigma_Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}σZ​=(10​0−1​), and set Πa(b)=12(I2+(−1)bσa)\Pi_a(b)=\tfrac12(I_2+(-1)^b\sigma_a)Πa​(b)=21​(I2​+(−1)bσa​), interpreting Boolean exponents as 000 or 111. Let Co=σZC_o=\sigma_ZCo​=σZ​ when f(o)=truef(o)=\mathrm{true}f(o)=true, otherwise Co=I2C_o=I_2Co​=I2​, and let Fa(o)=f(o)F_a(o)=f(o)Fa​(o)=f(o) for a=X,Ya=X,Ya=X,Y, while FZ(o)=falseF_Z(o)=\mathrm{false}FZ​(o)=false. For either finite index set S={false,true}S=\{\mathrm{false},\mathrm{true}\}S={false,true} or S={false,true}2S=\{\mathrm{false},\mathrm{true}\}^2S={false,true}2, define [DE(ρ)]u,v=∑α,β∈SEβ,αρ(α,u),(β,v)[D_E(\rho)]_{u,v}=\sum_{\alpha,\beta\in S}E_{\beta,\alpha}\rho_{(\alpha,u),(\beta,v)}[DE​(ρ)]u,v​=∑α,β∈S​Eβ,α​ρ(α,u),(β,v)​. First, for every positive semidefinite matrix ρ\rhoρ of trace 111 on the two Boolean registers together with RRR, every a∈{X,Y,Z}a\in\{X,Y,Z\}a∈{X,Y,Z}, every o∈Oo\in Oo∈O, and every Boolean rrr,

Uo,rD Mo†Mo⊗(Co†Πa(r)Co)(ρ)Uo,r†=Uo,rD Mo†Mo⊗Πa(r⊕Fa(o))(ρ)Uo,r†.U_{o,r}D_{\,M_o^\dagger M_o\otimes(C_o^\dagger\Pi_a(r)C_o)}(\rho)U_{o,r}^\dagger = U_{o,r}D_{\,M_o^\dagger M_o\otimes\Pi_a(r\oplus F_a(o))}(\rho)U_{o,r}^\dagger.Uo,r​DMo†​Mo​⊗(Co†​Πa​(r)Co​)​(ρ)Uo,r†​=Uo,r​DMo†​Mo​⊗Πa​(r⊕Fa​(o))​(ρ)Uo,r†​.

The right side is the early branch with outcome r⊕Fa(o)r\oplus F_a(o)r⊕Fa​(o), whose unitary index is (r⊕Fa(o))⊕Fa(o)=r(r\oplus F_a(o))\oplus F_a(o)=r(r⊕Fa​(o))⊕Fa​(o)=r. Second, for every positive semidefinite matrix ρ\rhoρ of trace 111 on one Boolean register together with RRR, every a∈{X,Y,Z}a\in\{X,Y,Z\}a∈{X,Y,Z}, and every Boolean rrr,

D H†Πa(r)H(ρ)=D Πh(a)(r⊕e(a))(ρ),H=12(111−1),D_{\,H^\dagger\Pi_a(r)H}(\rho) = D_{\,\Pi_{h(a)}(r\oplus e(a))}(\rho), \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},DH†Πa​(r)H​(ρ)=DΠh(a)​(r⊕e(a))​(ρ),H=2​1​(11​1−1​),

where h(X)=Zh(X)=Zh(X)=Z, h(Y)=Yh(Y)=Yh(Y)=Y, h(Z)=Xh(Z)=Xh(Z)=X, and e(Y)=truee(Y)=\mathrm{true}e(Y)=true, e(X)=e(Z)=falsee(X)=e(Z)=\mathrm{false}e(X)=e(Z)=false.

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