Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix C — characterization of condition (5) by Hilbert–Schmidt terms

Proved
OCB2012.process_condition_iff_allowed

by Alien60 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

indefinite-causal-orderprocess-matrixquantum-gravityquantum-information

Throughout, A1,A2A_1,A_2A1​,A2​ (Alice's input and output) and B1,B2B_1,B_2B1​,B2​ (Bob's) are finite-dimensional systems; operators on A1A2B1B2A_1A_2B_1B_2A1​A2​B1​B2​ are complex matrices in that tensor order. A CJ matrix MX1X2M^{X_1X_2}MX1​X2​ of a CPTP map satisfies M≥0M\ge 0M≥0 and Tr⁡X2M=1X1\operatorname{Tr}_{X_2}M=\mathbb 1^{X_1}TrX2​​M=1X1​. For each system XXX fix a Hilbert–Schmidt basis {σμX}μ=0dX2−1\{\sigma^X_\mu\}_{\mu=0}^{d_X^2-1}{σμX​}μ=0dX2​−1​ with σ0X=1\sigma^X_0=\mathbb 1σ0X​=1, σjX\sigma^X_jσjX​ Hermitian and traceless for j≥1j\ge1j≥1, and Tr⁡σμXσνX=dXδμν\operatorname{Tr}\sigma^X_\mu\sigma^X_\nu=d_X\delta_{\mu\nu}TrσμX​σνX​=dX​δμν​. A term σμA1σνA2σλB1σγB2\sigma^{A_1}_\mu\sigma^{A_2}_\nu\sigma^{B_1}_\lambda\sigma^{B_2}_\gammaσμA1​​σνA2​​σλB1​​σγB2​​ is allowed if its set of non-identity factors is one of ∅,A1,B1,A1B1,A2B1,A1A2B1,A1B2,A1B1B2\varnothing, A_1, B_1, A_1B_1, A_2B_1, A_1A_2B_1, A_1B_2, A_1B_1B_2∅,A1​,B1​,A1​B1​,A2​B1​,A1​A2​B1​,A1​B2​,A1​B1​B2​ (Fig. 3). Then for every Hermitian WWW on A1A2B1B2A_1A_2B_1B_2A1​A2​B1​B2​:

Tr⁡[W(MA1A2⊗MB1B2)]=1  ∀ CPTP CJ MA1A2,MB1B2\operatorname{Tr}[W(M^{A_1A_2}\otimes M^{B_1B_2})]=1\ \ \forall\,\text{CPTP CJ } M^{A_1A_2},M^{B_1B_2}Tr[W(MA1​A2​⊗MB1​B2​)]=1  ∀CPTP CJ MA1​A2​,MB1​B2​

holds if and only if Tr⁡W=dA2dB2\operatorname{Tr}W=d_{A_2}d_{B_2}TrW=dA2​​dB2​​ and Tr⁡[W σμA1σνA2σλB1σγB2]=0\operatorname{Tr}[W\,\sigma^{A_1}_\mu\sigma^{A_2}_\nu\sigma^{B_1}_\lambda\sigma^{B_2}_\gamma]=0Tr[WσμA1​​σνA2​​σλB1​​σγB2​​]=0 for every term that is not allowed, i.e. the Hilbert–Schmidt coefficients wμνλγw_{\mu\nu\lambda\gamma}wμνλγ​ of WWW vanish outside the allowed types and w0000=1/(dA1dB1)w_{0000}=1/(d_{A_1}d_{B_1})w0000​=1/(dA1​​dB1​​).

Formalization Note The coefficient wμνλγw_{\mu\nu\lambda\gamma}wμνλγ​ equals Tr⁡[Wσμσνσλσγ]/(dA1dA2dB1dB2)\operatorname{Tr}[W\sigma_\mu\sigma_\nu\sigma_\lambda\sigma_\gamma]/(d_{A_1}d_{A_2}d_{B_1}d_{B_2})Tr[Wσμ​σν​σλ​σγ​]/(dA1​​dA2​​dB1​​dB2​​) by orthogonality, so vanishing coefficients are stated as vanishing traces. Hermiticity of WWW and of the basis matches the source's restriction to real coefficients (Eq. (17)).

Preamble
import Mathlib
import Definitions.Def_PeresTerno_kraus_basics
import Definitions.Def_OCB2012_defs

open Matrix
open scoped Kronecker ComplexOrder
Formal statement
namespace OCB2012

theorem process_condition_iff_allowed {a1 a2 b1 b2 : Type*} [Fintype a1] [Fintype a2]
    [Fintype b1] [Fintype b2] [DecidableEq a1] [DecidableEq a2] [DecidableEq b1] [DecidableEq b2]
    (BA1 : HSBasis a1) (BA2 : HSBasis a2) (BB1 : HSBasis b1) (BB2 : HSBasis b2)
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ) (hW : W.IsHermitian) :
    (∀ (MA : Matrix (a1 × a2) (a1 × a2) ℂ) (MB : Matrix (b1 × b2) (b1 × b2) ℂ),
        IsCPTP_CJ MA → IsCPTP_CJ MB → prob W MA MB = 1) ↔
      (W.trace = (Fintype.card a2 * Fintype.card b2 : ℂ) ∧
        ∀ μ ν l γ, ¬ AllowedType μ.isSome ν.isSome l.isSome γ.isSome →
          (W * ((BA1.σ μ ⊗ₖ BA2.σ ν) ⊗ₖ (BB1.σ l ⊗ₖ BB2.σ γ))).trace = 0) := by sorry

end OCB2012
Source
O. Oreshkov, F. Costa, Č. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), https://arxiv.org/abs/1105.4464v3, Appendix C, Eqs. (16)–(18) and the general form at the end of App. C; Fig. 3 (allowed terms), Fig. 4 (disallowed terms)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let a1,a2,b1,b2a_1, a_2, b_1, b_2a1​,a2​,b1​,b2​ be arbitrary finite types with decidable equality. They index the systems A1,A2,B1,B2A_1, A_2, B_1, B_2A1​,A2​,B1​,B2​. Write dA1=∣a1∣d_{A_1} = |a_1|dA1​​=∣a1​∣, dA2=∣a2∣d_{A_2} = |a_2|dA2​​=∣a2​∣, dB1=∣b1∣d_{B_1} = |b_1|dB1​​=∣b1​∣, dB2=∣b2∣d_{B_2} = |b_2|dB2​​=∣b2​∣. All matrices have complex entries. A matrix on the composite system is indexed by ((a1×a2)×(b1×b2))((a_1 \times a_2) \times (b_1 \times b_2))((a1​×a2​)×(b1​×b2​)), and ⊗\otimes⊗ denotes the Kronecker product, with (X⊗Y)(i,k),(j,l)=XijYkl(X \otimes Y)_{(i,k),(j,l)} = X_{ij} Y_{kl}(X⊗Y)(i,k),(j,l)​=Xij​Ykl​. So (P⊗Q)⊗(R⊗S)(P \otimes Q) \otimes (R \otimes S)(P⊗Q)⊗(R⊗S) acts on (A1A2)(B1B2)(A_1 A_2)(B_1 B_2)(A1​A2​)(B1​B2​) in that factor order.

Hilbert–Schmidt bases (given data). The theorem takes four arbitrary Hilbert–Schmidt bases BA1,BA2,BB1,BB2\mathcal B_{A_1}, \mathcal B_{A_2}, \mathcal B_{B_1}, \mathcal B_{B_2}BA1​​,BA2​​,BB1​​,BB2​​, one for each system. For a finite type XXX with d=∣X∣d = |X|d=∣X∣, such a basis B\mathcal BB consists of the following data:

  • a finite index type ι\iotaι with decidable equality;
  • a family of d×dd \times dd×d complex matrices (τj)j∈ι(\tau_j)_{j \in \iota}(τj​)j∈ι​ such that:
    • each τj\tau_jτj​ is Hermitian;
    • Tr⁡τj=0\operatorname{Tr} \tau_j = 0Trτj​=0 for every jjj;
    • Tr⁡(τiτj)=d δij\operatorname{Tr}(\tau_i \tau_j) = d\,\delta_{ij}Tr(τi​τj​)=dδij​ for all i,j∈ιi, j \in \iotai,j∈ι;
    • ∣ι∣+1=d2|\iota| + 1 = d^2∣ι∣+1=d2.

The extended family σ:{none}∪ι→Cd×d\sigma : \{\text{none}\} \cup \iota \to \mathbb C^{d\times d}σ:{none}∪ι→Cd×d is defined by σnone=1\sigma_{\text{none}} = \mathbb 1σnone​=1 (the "identity" index 000) and σj=τj\sigma_{j} = \tau_jσj​=τj​ for j∈ιj \in \iotaj∈ι (the "non-identity" indices). No further property is assumed, such as spanning or linear independence, beyond what follows from these axioms.

Edge cases.

  • If XXX is empty, then d=0d = 0d=0 and the condition ∣ι∣+1=0|\iota| + 1 = 0∣ι∣+1=0 cannot hold. So no Hilbert–Schmidt basis exists for an empty type. Since the theorem takes bases for all four systems as inputs, it only ever applies when a1,a2,b1,b2a_1, a_2, b_1, b_2a1​,a2​,b1​,b2​ are all nonempty.
  • If d=1d = 1d=1, then ι\iotaι is empty and the only basis element is σnone=1\sigma_{\text{none}} = \mathbb 1σnone​=1.

Allowed types. For a quadruple of flags (μ,ν,λ,γ)(\mu, \nu, \lambda, \gamma)(μ,ν,λ,γ) for A1,A2,B1,B2A_1, A_2, B_1, B_2A1​,A2​,B1​,B2​, each flag is "true" exactly when the corresponding basis index is a non-identity index. The quadruple is allowed iff

(ν⇒λ∧¬γ)  ∧  (γ⇒μ∧¬ν).(\nu \Rightarrow \lambda \wedge \neg\gamma) \;\wedge\; (\gamma \Rightarrow \mu \wedge \neg\nu).(ν⇒λ∧¬γ)∧(γ⇒μ∧¬ν).

In words: a non-identity factor on A2A_2A2​ requires a non-identity factor on B1B_1B1​ and an identity factor on B2B_2B2​. A non-identity factor on B2B_2B2​ requires a non-identity factor on A1A_1A1​ and an identity factor on A2A_2A2​.

Listed by the set of systems carrying a non-identity factor, the 16 cases split as follows.

  • Allowed (8): ∅\varnothing∅, A1A_1A1​, B1B_1B1​, A1B1A_1B_1A1​B1​, A2B1A_2B_1A2​B1​, A1A2B1A_1A_2B_1A1​A2​B1​, A1B2A_1B_2A1​B2​, A1B1B2A_1B_1B_2A1​B1​B2​.
  • Not allowed (8): A2A_2A2​, A1A2A_1A_2A1​A2​, B2B_2B2​, B1B2B_1B_2B1​B2​, A2B2A_2B_2A2​B2​, A1A2B2A_1A_2B_2A1​A2​B2​, A2B1B2A_2B_1B_2A2​B1​B2​, A1A2B1B2A_1A_2B_1B_2A1​A2​B1​B2​.

Every set containing both A2A_2A2​ and B2B_2B2​ is not allowed.

CPTP Choi matrices. For finite types x1,x2x_1, x_2x1​,x2​, a matrix MMM indexed by x1×x2x_1 \times x_2x1​×x2​ is called a CPTP Choi matrix, written CPTP(M)\mathrm{CPTP}(M)CPTP(M), iff both of the following hold:

  • MMM is positive semidefinite, meaning Hermitian with v∗Mv≥0v^* M v \ge 0v∗Mv≥0 (as a real number) for all vvv;
  • its partial trace over the second factor is the identity:
(Tr⁡x2M)ij=∑k∈x2M(i,k),(j,k)=δijfor all i,j∈x1.(\operatorname{Tr}_{x_2} M)_{ij} = \sum_{k \in x_2} M_{(i,k),(j,k)} = \delta_{ij} \quad \text{for all } i, j \in x_1.(Trx2​​M)ij​=k∈x2​∑​M(i,k),(j,k)​=δij​for all i,j∈x1​.

For MAM_AMA​ on A1A2A_1A_2A1​A2​ this means Tr⁡A2MA=1A1\operatorname{Tr}_{A_2} M_A = \mathbb 1_{A_1}TrA2​​MA​=1A1​​. For MBM_BMB​ on B1B2B_1B_2B1​B2​ it means Tr⁡B2MB=1B1\operatorname{Tr}_{B_2} M_B = \mathbb 1_{B_1}TrB2​​MB​=1B1​​.

The probability is defined as the complex number

p(W,MA,MB)=Tr⁡ ⁣[W(MA⊗MB)].p(W, M_A, M_B) = \operatorname{Tr}\!\big[W (M_A \otimes M_B)\big].p(W,MA​,MB​)=Tr[W(MA​⊗MB​)].

Statement. Let WWW be any Hermitian matrix on (A1A2)(B1B2)(A_1A_2)(B_1B_2)(A1​A2​)(B1​B2​). Positive semidefiniteness is not assumed. Then the following two conditions are equivalent: each implies the other.

(L) For every matrix MAM_AMA​ on A1A2A_1A_2A1​A2​ and every matrix MBM_BMB​ on B1B2B_1B_2B1​B2​ such that CPTP(MA)\mathrm{CPTP}(M_A)CPTP(MA​) and CPTP(MB)\mathrm{CPTP}(M_B)CPTP(MB​) both hold,

Tr⁡ ⁣[W(MA⊗MB)]=1\operatorname{Tr}\!\big[W (M_A \otimes M_B)\big] = 1Tr[W(MA​⊗MB​)]=1

as a complex number.

(R) Both of the following hold.

  1. The trace condition holds as an equality of complex numbers:
Tr⁡W=dA2 dB2.\operatorname{Tr} W = d_{A_2}\, d_{B_2}.TrW=dA2​​dB2​​.
  1. Choose indices μ\muμ, ν\nuν, λ\lambdaλ, γ\gammaγ, each either the identity index or a non-identity index of the basis on its own system:

    • μ\muμ for BA1\mathcal B_{A_1}BA1​​;
    • ν\nuν for BA2\mathcal B_{A_2}BA2​​;
    • λ\lambdaλ for BB1\mathcal B_{B_1}BB1​​;
    • γ\gammaγ for BB2\mathcal B_{B_2}BB2​​.

    For every such choice whose non-identity pattern is not allowed (one of the 8 non-allowed cases above),

Tr⁡ ⁣[W((σμA1⊗σνA2)⊗(σλB1⊗σγB2))]=0.\operatorname{Tr}\!\Big[W \big((\sigma^{A_1}_\mu \otimes \sigma^{A_2}_\nu) \otimes (\sigma^{B_1}_\lambda \otimes \sigma^{B_2}_\gamma)\big)\Big] = 0.Tr[W((σμA1​​⊗σνA2​​)⊗(σλB1​​⊗σγB2​​))]=0.

Allowed patterns, including the all-identity term, receive no constraint from clause 2.

Quantifier scope. The equivalence is asserted for all finite types a1,a2,b1,b2a_1, a_2, b_1, b_2a1​,a2​,b1​,b2​, for every choice of the four bases, and for every Hermitian WWW. Clause 2 of (R) refers to the specific given bases, so the theorem claims that (L) holds iff the vanishing condition holds for each one of these arbitrary basis choices. Because bases cannot exist for empty types, the statement is vacuous whenever any of a1,a2,b1,b2a_1, a_2, b_1, b_2a1​,a2​,b1​,b2​ is empty.

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

    Confirmed by the moderator at approval.

  • Endorsed by Alien60 · Oct 8, 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