Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Process matrices, local instruments, causal separability and the qubit protocol (OCB 2012)

Definition
OCB2012_defs

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

indefinite-causal-orderprocess-matrixquantum-gravityquantum-information

Shared vocabulary of the mission. For finite-dimensional systems A1,A2,B1,B2A_1,A_2,B_1,B_2A1​,A2​,B1​,B2​ with operators on A1A2B1B2A_1A_2B_1B_2A1​A2​B1​B2​ indexed in that order: the partial trace Tr⁡2\operatorname{Tr}_2Tr2​; CJ matrices of CPTP maps (M≥0M\ge0M≥0, Tr⁡X2M=1X1\operatorname{Tr}_{X_2}M=\mathbb 1^{X_1}TrX2​​M=1X1​, p. 4); the probability rule Tr⁡[W(MA⊗MB)]\operatorname{Tr}[W(M^A\otimes M^B)]Tr[W(MA⊗MB)] (Eq. (3)); process matrices (Eqs. (4)–(5)); Alice's and Bob's local instruments with input bits aaa and (b,b′)(b,b')(b,b′) and guesses x,yx,yx,y; the success probability psuccp_{succ}psucc​ of Eq. (1) (real parts of traces, bits as Booleans); the one-way forms 1A2⊗WA1B1B2\mathbb 1^{A_2}\otimes W^{A_1B_1B_2}1A2​⊗WA1​B1​B2​ (A⪯̸BA\not\preceq BA⪯B) and 1B2⊗WA1A2B1\mathbb 1^{B_2}\otimes W^{A_1A_2B_1}1B2​⊗WA1​A2​B1​ (B⪯̸AB\not\preceq AB⪯A); causal separability (Eq. (6)); the Pauli matrices, the process matrix WWW of Eq. (7), Alice's instrument ξ\xiξ (Eq. (20)) and Bob's η\etaη (Eqs. (21)–(23), with Bob's prepared state ρB2\rho^{B_2}ρB2​ as a parameter); Hilbert–Schmidt bases (Appendix C) and the allowed term types of Fig. 3.

Definition code
import Mathlib
import Definitions.Def_PeresTerno_kraus_basics

/-!
# Process matrices and the causal inequality

Definitions for the mission drafted from O. Oreshkov, F. Costa and Č. Brukner,
*Quantum correlations with no causal order*, Nat. Commun. 3, 1092 (2012),
arXiv:1105.4464v3.

Alice has an input system `A1` and an output system `A2`; Bob has `B1` and `B2`.
All systems are finite-dimensional and indexed by finite types `a1 a2 b1 b2`.
Bipartite operators on `A1A2B1B2` are matrices indexed by `(a1 × a2) × (b1 × b2)`,
so that `MA ⊗ₖ MB` is `M^{A1A2} ⊗ M^{B1B2}` in the order used by the paper.
Local operations are represented directly by their Choi–Jamiołkowski (CJ) matrices.
-/

namespace OCB2012

open Matrix
open scoped Kronecker ComplexOrder

noncomputable section

/-- Partial trace over the second tensor factor:
`(Tr₂ M)_{ij} = ∑ₖ M_{(i,k),(j,k)}`. -/
def ptrace₂ {α β : Type*} [Fintype β] (M : Matrix (α × β) (α × β) ℂ) : Matrix α α ℂ :=
  Matrix.of fun i j => ∑ k, M (i, k) (j, k)

/-- p. 4: the CJ matrix `M^{X1X2}` of a completely positive trace-preserving map from
`X1` to `X2` is characterized by `M ≥ 0` and `Tr_{X2} M = 𝟙^{X1}`. -/
def IsCPTP_CJ {x1 x2 : Type*} [Fintype x1] [Fintype x2] [DecidableEq x1]
    (M : Matrix (x1 × x2) (x1 × x2) ℂ) : Prop :=
  M.PosSemidef ∧ ptrace₂ M = 1

/-- Eq. (3): the probability `Tr[W (M^{A1A2} ⊗ M^{B1B2})]` of the pair of local
outcomes with CJ matrices `MA`, `MB`. -/
def prob {a1 a2 b1 b2 : Type*} [Fintype a1] [Fintype a2] [Fintype b1] [Fintype b2]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ)
    (MA : Matrix (a1 × a2) (a1 × a2) ℂ) (MB : Matrix (b1 × b2) (b1 × b2) ℂ) : ℂ :=
  (W * (MA ⊗ₖ MB)).trace

/-- Eqs. (4)–(5): `W` is a **process matrix** if `W ≥ 0` and
`Tr[W (M^{A1A2} ⊗ M^{B1B2})] = 1` for all CJ matrices of CPTP maps. -/
def IsProcessMatrix {a1 a2 b1 b2 : Type*} [Fintype a1] [Fintype a2] [Fintype b1]
    [Fintype b2] [DecidableEq a1] [DecidableEq b1]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ) : Prop :=
  W.PosSemidef ∧
    ∀ (MA : Matrix (a1 × a2) (a1 × a2) ℂ) (MB : Matrix (b1 × b2) (b1 × b2) ℂ),
      IsCPTP_CJ MA → IsCPTP_CJ MB → prob W MA MB = 1

/-- Alice's local quantum instrument in the task of Eq. (1): for each input bit `a`
a family of CJ matrices `MA x a ≥ 0` indexed by her guess `x`, whose sum over `x`
is the CJ matrix of a CPTP map. -/
def IsAliceInstrument {a1 a2 : Type*} [Fintype a1] [Fintype a2] [DecidableEq a1]
    (MA : Bool → Bool → Matrix (a1 × a2) (a1 × a2) ℂ) : Prop :=
  (∀ x a, (MA x a).PosSemidef) ∧ ∀ a, IsCPTP_CJ (∑ x, MA x a)

/-- Bob's local quantum instrument in the task of Eq. (1): for each pair of input bits
`b, b'` a family of CJ matrices `MB y b b' ≥ 0` indexed by his guess `y`, whose sum
over `y` is the CJ matrix of a CPTP map. -/
def IsBobInstrument {b1 b2 : Type*} [Fintype b1] [Fintype b2] [DecidableEq b1]
    (MB : Bool → Bool → Bool → Matrix (b1 × b2) (b1 × b2) ℂ) : Prop :=
  (∀ y b b', (MB y b b').PosSemidef) ∧ ∀ b b', IsCPTP_CJ (∑ y, MB y b b')

/-- Eq. (1): the probability of success
`p_succ = ½ [P(x = b | b' = 0) + P(y = a | b' = 1)]`, with `a, b, b'` independent and
uniformly distributed. Bits are encoded as `Bool` (`false ↦ 0`, `true ↦ 1`), and the
joint probability of guesses `x, y` given inputs `a, b, b'` is
`Tr[W (MA x a ⊗ MB y b b')]` (Eq. (3)). Probabilities are the real parts of these traces. -/
def pSucc {a1 a2 b1 b2 : Type*} [Fintype a1] [Fintype a2] [Fintype b1] [Fintype b2]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ)
    (MA : Bool → Bool → Matrix (a1 × a2) (a1 × a2) ℂ)
    (MB : Bool → Bool → Bool → Matrix (b1 × b2) (b1 × b2) ℂ) : ℝ :=
  (1 / 2 : ℝ) * ((1 / 4 : ℝ) * ∑ a : Bool, ∑ b : Bool, ∑ y : Bool,
      (prob W (MA b a) (MB y b false)).re) +
  (1 / 2 : ℝ) * ((1 / 4 : ℝ) * ∑ a : Bool, ∑ b : Bool, ∑ x : Bool,
      (prob W (MA x a) (MB a b true)).re)

/-- p. 4: `W` has the form `𝟙^{A2} ⊗ W^{A1B1B2}` (a channel with memory from Bob to
Alice; no signalling from Alice to Bob, written `A ⋠ B`). -/
def IsNoSignalAtoB {a1 a2 b1 b2 : Type*} [DecidableEq a2]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ) : Prop :=
  ∃ X : Matrix (a1 × (b1 × b2)) (a1 × (b1 × b2)) ℂ,
    W = Matrix.of fun r c => if r.1.2 = c.1.2 then X (r.1.1, r.2) (c.1.1, c.2) else 0

/-- p. 4: `W` has the form `𝟙^{B2} ⊗ W^{A1A2B1}` (no signalling from Bob to Alice,
written `B ⋠ A`). -/
def IsNoSignalBtoA {a1 a2 b1 b2 : Type*} [DecidableEq b2]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ) : Prop :=
  ∃ X : Matrix ((a1 × a2) × b1) ((a1 × a2) × b1) ℂ,
    W = Matrix.of fun r c => if r.2.2 = c.2.2 then X (r.1, r.2.1) (c.1, c.2.1) else 0

/-- Eq. (6): `W` is **causally separable** if `W = q W^{B⋠A} + (1 - q) W^{A⋠B}` for some
`0 ≤ q ≤ 1`, where `W^{B⋠A}` and `W^{A⋠B}` are process matrices of the respective
no-signalling forms. -/
def IsCausallySeparable {a1 a2 b1 b2 : Type*} [Fintype a1] [Fintype a2] [Fintype b1]
    [Fintype b2] [DecidableEq a1] [DecidableEq a2] [DecidableEq b1] [DecidableEq b2]
    (W : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ) : Prop :=
  ∃ q : ℝ, 0 ≤ q ∧ q ≤ 1 ∧
    ∃ WBA WAB : Matrix ((a1 × a2) × (b1 × b2)) ((a1 × a2) × (b1 × b2)) ℂ,
      IsProcessMatrix WBA ∧ IsNoSignalBtoA WBA ∧
      IsProcessMatrix WAB ∧ IsNoSignalAtoB WAB ∧
      W = (q : ℂ) • WBA + ((1 - q : ℝ) : ℂ) • WAB

/-! ### The qubit example (Eq. (7)) and the protocol of Appendix E -/

/-- A two-level system. -/
abbrev Qubit := Fin 2

/-- Pauli matrix `σ_x`. -/
def σx : Matrix Qubit Qubit ℂ := !![0, 1; 1, 0]

/-- Pauli matrix `σ_z` (`|z₊⟩ = |0⟩`, `|z₋⟩ = |1⟩`). -/
def σz : Matrix Qubit Qubit ℂ := !![1, 0; 0, -1]

/-- `(-1)^x` for a bit `x`. -/
def sgn (x : Bool) : ℂ := if x then -1 else 1

/-- Eq. (7): the process matrix
`W = ¼ [𝟙 + (1/√2)(σ_z^{A2} σ_z^{B1} + σ_z^{A1} σ_x^{B1} σ_z^{B2})]`
on four qubits `A1 A2 B1 B2`. -/
def W7 : Matrix ((Qubit × Qubit) × (Qubit × Qubit)) ((Qubit × Qubit) × (Qubit × Qubit)) ℂ :=
  (1 / 4 : ℂ) • (1 + ((1 / Real.sqrt 2 : ℝ) : ℂ) •
    ((((1 : Matrix Qubit Qubit ℂ) ⊗ₖ σz) ⊗ₖ (σz ⊗ₖ (1 : Matrix Qubit Qubit ℂ))) +
     ((σz ⊗ₖ (1 : Matrix Qubit Qubit ℂ)) ⊗ₖ (σx ⊗ₖ σz))))

/-- Eq. (20): Alice's CJ matrices `ξ(x, a) = ¼ [𝟙 + (-1)^x σ_z]^{A1} ⊗ [𝟙 + (-1)^a σ_z]^{A2}`
(measure the incoming qubit in the `z` basis, record `x`, re-prepare `a` in the `z` basis). -/
def ξ (x a : Bool) : Matrix (Qubit × Qubit) (Qubit × Qubit) ℂ :=
  (1 / 4 : ℂ) • ((1 + sgn x • σz) ⊗ₖ (1 + sgn a • σz))

/-- Eqs. (21)–(23): Bob's CJ matrices `η(y, b, b') = b' η₁(y, b) + (b' ⊕ 1) η₂(y, b)` with
`η₁(y, b) = ½ [𝟙 + (-1)^y σ_z]^{B1} ⊗ ρ^{B2}` and
`η₂(y, b) = ¼ [𝟙 + (-1)^y σ_x]^{B1} ⊗ [𝟙 + (-1)^{b+y} σ_z]^{B2}`,
where `ρ` is the arbitrary state Bob prepares when `b' = 1`. -/
def η (ρ : Matrix Qubit Qubit ℂ) (y b b' : Bool) : Matrix (Qubit × Qubit) (Qubit × Qubit) ℂ :=
  if b' then (1 / 2 : ℂ) • ((1 + sgn y • σz) ⊗ₖ ρ)
  else (1 / 4 : ℂ) • ((1 + sgn y • σx) ⊗ₖ (1 + sgn (xor b y) • σz))

/-! ### Hilbert–Schmidt bases (Appendix C) -/

/-- Appendix C: a Hilbert–Schmidt basis `{σ_μ}_{μ=0}^{d²-1}` of the operators on `ℂ^X`,
with `σ₀ = 𝟙` and the remaining elements `τ j` Hermitian, traceless, and orthogonal:
`Tr σ_μ σ_ν = d δ_{μν}`, where `d = |X|`. -/
structure HSBasis (X : Type*) [Fintype X] [DecidableEq X] where
  /-- Index type of the non-identity elements. -/
  ι : Type
  [instFintype : Fintype ι]
  [instDecEq : DecidableEq ι]
  /-- The non-identity basis elements `σ_j`, `j = 1, …, d² - 1`. -/
  τ : ι → Matrix X X ℂ
  isHermitian : ∀ j, (τ j).IsHermitian
  trace_eq_zero : ∀ j, (τ j).trace = 0
  trace_mul : ∀ i j, (τ i * τ j).trace = if i = j then (Fintype.card X : ℂ) else 0
  card_eq : Fintype.card ι + 1 = Fintype.card X ^ 2

attribute [instance] HSBasis.instFintype HSBasis.instDecEq

/-- The full basis `σ_μ`, with `none ↦ σ₀ = 𝟙` and `some j ↦ σ_j`. -/
def HSBasis.σ {X : Type*} [Fintype X] [DecidableEq X] (B : HSBasis X) :
    Option B.ι → Matrix X X ℂ
  | none => 1
  | some j => B.τ j

/-- Fig. 3 / Appendix C: a Hilbert–Schmidt term `σ_μ^{A1} σ_ν^{A2} σ_λ^{B1} σ_γ^{B2}` is of an
**allowed type** if its set of non-identity factors is one of `∅, A1, B1, A1B1, A2B1,
A1A2B1, A1B2, A1B1B2`; equivalently, a non-identity factor on `A2` requires one on `B1`
and none on `B2`, and a non-identity factor on `B2` requires one on `A1` and none on `A2`. -/
def AllowedType (μ ν l γ : Bool) : Prop :=
  (ν → l ∧ ¬γ) ∧ (γ → μ ∧ ¬ν)

end

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, pp. 2–5 Eqs. (1), (3)–(7); Appendix C; Appendix E Eqs. (20)–(23); Fig. 3
Read-back

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

General conventions. All matrices have complex entries. Matrices are indexed by finite types rather than by {1,…,n}\{1,\dots,n\}{1,…,n}. A product index type α×β\alpha\times\betaα×β is indexed by pairs (i,k)(i,k)(i,k). The Kronecker product A⊗BA\otimes BA⊗B of AAA (indexed by α\alphaα) and BBB (indexed by β\betaβ) is the matrix indexed by α×β\alpha\times\betaα×β with entries (A⊗B)(i,k),(j,l)=AijBkl(A\otimes B)_{(i,k),(j,l)} = A_{ij}B_{kl}(A⊗B)(i,k),(j,l)​=Aij​Bkl​. "Positive semidefinite" (PSD) means Hermitian with vˉTMv≥0\bar v^{\mathsf T} M v \ge 0vˉTMv≥0 for every complex vector vvv, using the partial order on C\mathbb CC in which z≥0z\ge 0z≥0 means zzz is a nonnegative real. 1\mathbb 11 is the identity matrix of the appropriate index type, and Tr⁡\operatorname{Tr}Tr is the usual trace, the sum of the diagonal entries. Bipartite operators in this file are indexed by ((a1×a2)×(b1×b2))((a_1\times a_2)\times(b_1\times b_2))((a1​×a2​)×(b1​×b2​)), so a row index has the form ((i1,i2),(k1,k2))((i_1,i_2),(k_1,k_2))((i1​,i2​),(k1​,k2​)) with i1∈a1i_1\in a_1i1​∈a1​, i2∈a2i_2\in a_2i2​∈a2​, k1∈b1k_1\in b_1k1​∈b1​, k2∈b2k_2\in b_2k2​∈b2​. The subsystem names A1,A2,B1,B2A_1,A_2,B_1,B_2A1​,A2​,B1​,B2​ refer to these four positions. The imported dependency file is not used by any definition here.


ptrace₂ (partial trace over the second factor). Let α\alphaα be any type and β\betaβ a finite type (α\alphaα need not be finite). For a complex matrix MMM indexed by α×β\alpha\times\betaα×β, Tr⁡2M\operatorname{Tr}_2 MTr2​M is the matrix indexed by α\alphaα with

(Tr⁡2M)ij=∑k∈βM(i,k),(j,k).(\operatorname{Tr}_2 M)_{ij} = \sum_{k\in\beta} M_{(i,k),(j,k)}.(Tr2​M)ij​=k∈β∑​M(i,k),(j,k)​.

If β\betaβ is empty, the result is the zero matrix.


IsCPTP_CJ. Let x1,x2x_1, x_2x1​,x2​ be finite types, where x1x_1x1​ has decidable equality. For MMM indexed by x1×x2x_1\times x_2x1​×x2​, the predicate holds iff

  1. MMM is positive semidefinite, and
  2. Tr⁡2M=1x1\operatorname{Tr}_2 M = \mathbb 1_{x_1}Tr2​M=1x1​​, where the partial trace is over the second factor x2x_2x2​ as in ptrace₂.

Edge cases:

  • If x1x_1x1​ is empty, the only such matrix is the empty matrix, and it satisfies the predicate.
  • If x2x_2x2​ is empty and x1x_1x1​ is nonempty, Tr⁡2M=0≠1\operatorname{Tr}_2 M = 0 \ne \mathbb 1Tr2​M=0=1, so no matrix satisfies it.

prob. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be finite types. For a matrix WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​), a matrix MAM_AMA​ indexed by a1×a2a_1\times a_2a1​×a2​ and a matrix MBM_BMB​ indexed by b1×b2b_1\times b_2b1​×b2​,

prob⁡(W,MA,MB)=Tr⁡[W (MA⊗MB)]∈C.\operatorname{prob}(W,M_A,M_B) = \operatorname{Tr}\big[W\,(M_A\otimes M_B)\big]\in\mathbb C.prob(W,MA​,MB​)=Tr[W(MA​⊗MB​)]∈C.

This is a complex number. Nothing is assumed about WWW, MAM_AMA​ or MBM_BMB​.


IsProcessMatrix. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be finite types, with decidable equality on a1a_1a1​ and b1b_1b1​. A matrix WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​) is a process matrix iff

  1. WWW is positive semidefinite, and
  2. for every MAM_AMA​ indexed by a1×a2a_1\times a_2a1​×a2​ and every MBM_BMB​ indexed by b1×b2b_1\times b_2b1​×b2​ such that both satisfy IsCPTP_CJ, the complex number Tr⁡[W(MA⊗MB)]\operatorname{Tr}[W(M_A\otimes M_B)]Tr[W(MA​⊗MB​)] equals exactly 111.

IsCPTP_CJ here means PSD, with partial trace over a2a_2a2​ (respectively b2b_2b2​) equal to the identity on a1a_1a1​ (respectively b1b_1b1​).

Edge case: if no matrix satisfies IsCPTP_CJ on one side (for example a2a_2a2​ empty and a1a_1a1​ nonempty), condition 2 is vacuous, and every PSD WWW qualifies.


IsAliceInstrument. Let a1,a2a_1,a_2a1​,a2​ be finite types, with decidable equality on a1a_1a1​. The input is a family MA(x,a)M_A(x,a)MA​(x,a) of matrices indexed by a1×a2a_1\times a_2a1​×a2​, where x,ax,ax,a range over the Booleans. The first argument xxx is called the guess and the second argument aaa is called the input. The predicate holds iff

  1. every MA(x,a)M_A(x,a)MA​(x,a) is positive semidefinite, and
  2. for each aaa, the sum MA(false,a)+MA(true,a)M_A(\text{false},a)+M_A(\text{true},a)MA​(false,a)+MA​(true,a) satisfies IsCPTP_CJ. That is, the sum is PSD and its partial trace over a2a_2a2​ equals 1a1\mathbb 1_{a_1}1a1​​.

IsBobInstrument. Let b1,b2b_1,b_2b1​,b2​ be finite types, with decidable equality on b1b_1b1​. The input is a family MB(y,b,b′)M_B(y,b,b')MB​(y,b,b′) of matrices indexed by b1×b2b_1\times b_2b1​×b2​, with three Boolean arguments. The first argument is yyy (the guess), then bbb, then b′b'b′. The predicate holds iff

  1. every MB(y,b,b′)M_B(y,b,b')MB​(y,b,b′) is PSD, and
  2. for each pair (b,b′)(b,b')(b,b′), the sum ∑yMB(y,b,b′)\sum_{y} M_B(y,b,b')∑y​MB​(y,b,b′) satisfies IsCPTP_CJ. That is, the sum is PSD and its partial trace over b2b_2b2​ equals 1b1\mathbb 1_{b_1}1b1​​.

pSucc. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be finite types. Given:

  • a matrix WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​),
  • a family MA(⋅,⋅)M_A(\cdot,\cdot)MA​(⋅,⋅) of matrices on a1×a2a_1\times a_2a1​×a2​ indexed by two Booleans, and
  • a family MB(⋅,⋅,⋅)M_B(\cdot,\cdot,\cdot)MB​(⋅,⋅,⋅) of matrices on b1×b2b_1\times b_2b1​×b2​ indexed by three Booleans,

the real number psuccp_{\rm succ}psucc​ is defined by

psucc=12⋅14∑a,b,y∈{f,t}Re⁡Tr⁡[W (MA(b,a)⊗MB(y,b,false))]  +  12⋅14∑a,b,x∈{f,t}Re⁡Tr⁡[W (MA(x,a)⊗MB(a,b,true))].p_{\rm succ} = \tfrac12\cdot\tfrac14\sum_{a,b,y\in\{\rm f,t\}} \operatorname{Re}\operatorname{Tr}\big[W\,(M_A(b,a)\otimes M_B(y,b,\text{false}))\big] \;+\; \tfrac12\cdot\tfrac14\sum_{a,b,x\in\{\rm f,t\}} \operatorname{Re}\operatorname{Tr}\big[W\,(M_A(x,a)\otimes M_B(a,b,\text{true}))\big].psucc​=21​⋅41​a,b,y∈{f,t}∑​ReTr[W(MA​(b,a)⊗MB​(y,b,false))]+21​⋅41​a,b,x∈{f,t}∑​ReTr[W(MA​(x,a)⊗MB​(a,b,true))].

How the Booleans are used:

  • In the first sum, the first argument of MAM_AMA​ is set equal to bbb, and b′=falseb'=\text{false}b′=false.
  • In the second sum, the first argument of MBM_BMB​ is set equal to aaa, and b′=trueb'=\text{true}b′=true.
  • Booleans are summed directly. Equality of a guess with an input bit is imposed by substituting the same Boolean. No numeric encoding is involved.

Only real parts of the traces are taken. No hypotheses are placed on WWW, MAM_AMA​ or MBM_BMB​: they need not be PSD, a process matrix or instruments.


IsNoSignalAtoB. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be arbitrary types (no finiteness required), with decidable equality on a2a_2a2​. The predicate holds for WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​) iff there exists a complex matrix XXX, indexed by a1×(b1×b2)a_1\times(b_1\times b_2)a1​×(b1​×b2​), such that for all indices

W((i1,i2),k), ((j1,j2),l)=δi2j2 X(i1,k),(j1,l)(k,l∈b1×b2).W_{((i_1,i_2),k),\,((j_1,j_2),l)} = \delta_{i_2 j_2}\, X_{(i_1,k),(j_1,l)} \qquad (k,l\in b_1\times b_2).W((i1​,i2​),k),((j1​,j2​),l)​=δi2​j2​​X(i1​,k),(j1​,l)​(k,l∈b1​×b2​).

In words, WWW is the identity on a2a_2a2​ tensored with XXX on the remaining factors a1,b1,b2a_1,b_1,b_2a1​,b1​,b2​, with the factors reordered. No positivity, trace or other condition is placed on XXX.


IsNoSignalBtoA. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be arbitrary types, with decidable equality on b2b_2b2​. The predicate holds for WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​) iff there exists a complex matrix XXX, indexed by (a1×a2)×b1(a_1\times a_2)\times b_1(a1​×a2​)×b1​, such that for all indices

W(r,(k1,k2)), (c,(l1,l2))=δk2l2 X(r,k1),(c,l1)(r,c∈a1×a2).W_{(r,(k_1,k_2)),\,(c,(l_1,l_2))} = \delta_{k_2 l_2}\, X_{(r,k_1),(c,l_1)} \qquad (r,c\in a_1\times a_2).W(r,(k1​,k2​)),(c,(l1​,l2​))​=δk2​l2​​X(r,k1​),(c,l1​)​(r,c∈a1​×a2​).

In words, WWW is the identity on b2b_2b2​ tensored with an unconstrained XXX on a1,a2,b1a_1,a_2,b_1a1​,a2​,b1​.


IsCausallySeparable. Let a1,a2,b1,b2a_1,a_2,b_1,b_2a1​,a2​,b1​,b2​ be finite types, all with decidable equality. A matrix WWW indexed by (a1×a2)×(b1×b2)(a_1\times a_2)\times(b_1\times b_2)(a1​×a2​)×(b1​×b2​) is causally separable iff there exist:

  • a real number qqq with 0≤q≤10\le q\le 10≤q≤1, and
  • two matrices WB≰AW^{B\not\le A}WB≤A and WA≰BW^{A\not\le B}WA≤B of the same shape,

such that

  1. WB≰AW^{B\not\le A}WB≤A is a process matrix (IsProcessMatrix) and has the form of IsNoSignalBtoA (identity on b2b_2b2​),
  2. WA≰BW^{A\not\le B}WA≤B is a process matrix and has the form of IsNoSignalAtoB (identity on a2a_2a2​), and
  3. the following equality holds, with qqq and 1−q1-q1−q embedded as complex scalars:
W=q WB≰A+(1−q) WA≰B.W = q\,W^{B\not\le A} + (1-q)\,W^{A\not\le B}.W=qWB≤A+(1−q)WA≤B.

Qubit. This is the two-element index type {0,1}\{0,1\}{0,1}.

σx. The 2×22\times22×2 complex matrix σx=(0110)\sigma_x=\begin{pmatrix}0&1\\1&0\end{pmatrix}σx​=(01​10​), with rows and columns indexed by 0,10,10,1.

σz. The matrix σz=(100−1)\sigma_z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}σz​=(10​0−1​), so (σz)00=1(\sigma_z)_{00}=1(σz​)00​=1 and (σz)11=−1(\sigma_z)_{11}=-1(σz​)11​=−1.

sgn. For a Boolean xxx, sgn⁡(x)∈C\operatorname{sgn}(x)\in\mathbb Csgn(x)∈C equals −1-1−1 if x=truex=\text{true}x=true and 111 if x=falsex=\text{false}x=false. Under the encoding true ↦1\mapsto 1↦1, false ↦0\mapsto 0↦0, this is (−1)x(-1)^x(−1)x.


W7. This is the 16×1616\times1616×16 complex matrix indexed by ({0,1}×{0,1})×({0,1}×{0,1})(\{0,1\}\times\{0,1\})\times(\{0,1\}\times\{0,1\})({0,1}×{0,1})×({0,1}×{0,1}) given by

W7=14[1+12((1⊗σz)⊗(σz⊗1)  +  (σz⊗1)⊗(σx⊗σz))].W_7 = \tfrac14\Big[\mathbb 1 + \tfrac{1}{\sqrt2}\Big( (\mathbb 1\otimes\sigma_z)\otimes(\sigma_z\otimes\mathbb 1) \;+\; (\sigma_z\otimes\mathbb 1)\otimes(\sigma_x\otimes\sigma_z)\Big)\Big].W7​=41​[1+2​1​((1⊗σz​)⊗(σz​⊗1)+(σz​⊗1)⊗(σx​⊗σz​))].

12\frac1{\sqrt2}2​1​ is computed as a real number (positive square root) and then embedded in C\mathbb CC.

Read off by position (a1,a2,b1,b2)(a_1,a_2,b_1,b_2)(a1​,a2​,b1​,b2​):

  • The first term acts as 1\mathbb 11 on a1a_1a1​, σz\sigma_zσz​ on a2a_2a2​, σz\sigma_zσz​ on b1b_1b1​ and 1\mathbb 11 on b2b_2b2​.
  • The second term acts as σz\sigma_zσz​ on a1a_1a1​, 1\mathbb 11 on a2a_2a2​, σx\sigma_xσx​ on b1b_1b1​ and σz\sigma_zσz​ on b2b_2b2​.

ξ. For Booleans x,ax,ax,a, ξ(x,a)\xi(x,a)ξ(x,a) is the 4×44\times44×4 matrix indexed by {0,1}×{0,1}\{0,1\}\times\{0,1\}{0,1}×{0,1} given by

ξ(x,a)=14 (1+sgn⁡(x) σz)⊗(1+sgn⁡(a) σz).\xi(x,a) = \tfrac14\,\big(\mathbb 1 + \operatorname{sgn}(x)\,\sigma_z\big)\otimes\big(\mathbb 1+\operatorname{sgn}(a)\,\sigma_z\big).ξ(x,a)=41​(1+sgn(x)σz​)⊗(1+sgn(a)σz​).

The first Kronecker factor, which depends on xxx, occupies the first index position.


η. For an arbitrary complex 2×22\times22×2 matrix ρ\rhoρ and Booleans y,b,b′y,b,b'y,b,b′, ηρ(y,b,b′)\eta_\rho(y,b,b')ηρ​(y,b,b′) is the 4×44\times44×4 matrix indexed by {0,1}×{0,1}\{0,1\}\times\{0,1\}{0,1}×{0,1} given by

ηρ(y,b,b′)={12 (1+sgn⁡(y) σz)⊗ρif b′=true,14 (1+sgn⁡(y) σx)⊗(1+sgn⁡(b⊕y) σz)if b′=false,\eta_\rho(y,b,b') = \begin{cases} \tfrac12\,\big(\mathbb 1+\operatorname{sgn}(y)\,\sigma_z\big)\otimes\rho & \text{if } b'=\text{true},\\[4pt] \tfrac14\,\big(\mathbb 1+\operatorname{sgn}(y)\,\sigma_x\big)\otimes\big(\mathbb 1+\operatorname{sgn}(b\oplus y)\,\sigma_z\big) & \text{if } b'=\text{false},\end{cases}ηρ​(y,b,b′)={21​(1+sgn(y)σz​)⊗ρ41​(1+sgn(y)σx​)⊗(1+sgn(b⊕y)σz​)​if b′=true,if b′=false,​

where b⊕yb\oplus yb⊕y is Boolean exclusive or. When b′=trueb'=\text{true}b′=true, the value does not depend on bbb. No condition is placed on ρ\rhoρ: it need not be PSD, Hermitian or of unit trace.


HSBasis X (a structure). Let XXX be a finite type with decidable equality, and let d=∣X∣d=|X|d=∣X∣. An element of HSBasis X consists of the following data and conditions.

Data:

  • a type ι\iotaι (in the lowest universe), equipped with finiteness and decidable equality, and
  • a family of complex matrices τj\tau_jτj​ indexed by XXX, for j∈ιj\in\iotaj∈ι.

Conditions:

  1. every τj\tau_jτj​ is Hermitian,
  2. Tr⁡τj=0\operatorname{Tr}\tau_j=0Trτj​=0 for all jjj,
  3. Tr⁡(τiτj)=d\operatorname{Tr}(\tau_i\tau_j) = dTr(τi​τj​)=d if i=ji=ji=j and 000 if i≠ji\neq ji=j, for all i,ji,ji,j, and
  4. ∣ι∣+1=d2|\iota|+1=d^2∣ι∣+1=d2.

Edge cases:

  • If XXX is empty, then d=0d=0d=0 and condition 4 cannot hold, so no such structure exists.
  • If d=1d=1d=1, then ι\iotaι is empty.

HSBasis.σ. Given BBB in HSBasis X, define σμ\sigma_\muσμ​ for μ\muμ in ι∪{none}\iota\cup\{\text{none}\}ι∪{none} (an option type) by σnone=1X\sigma_{\text{none}}=\mathbb 1_Xσnone​=1X​ and σj=τj\sigma_{j}=\tau_jσj​=τj​ for j∈ιj\in\iotaj∈ι.


AllowedType. This is a predicate on four Booleans (μ,ν,l,γ)(\mu,\nu,l,\gamma)(μ,ν,l,γ), where true is read as the proposition "true". It holds iff

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

Exactly 8 of the 16 tuples satisfy it. Listing the set of variables that are true:

∅, {μ}, {l}, {μ,l}, {ν,l}, {μ,ν,l}, {μ,γ}, {μ,l,γ}.\emptyset,\ \{\mu\},\ \{l\},\ \{\mu,l\},\ \{\nu,l\},\ \{\mu,\nu,l\},\ \{\mu,\gamma\},\ \{\mu,l,\gamma\}.∅, {μ}, {l}, {μ,l}, {ν,l}, {μ,ν,l}, {μ,γ}, {μ,l,γ}.

The code gives the Booleans no meaning beyond their positions, and nothing links them to HSBasis.

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