Process matrices, local instruments, causal separability and the qubit protocol (OCB 2012)
DefinitionOCB2012_defsShared vocabulary of the mission. For finite-dimensional systems with operators on indexed in that order: the partial trace ; CJ matrices of CPTP maps (, , p. 4); the probability rule (Eq. (3)); process matrices (Eqs. (4)–(5)); Alice's and Bob's local instruments with input bits and and guesses ; the success probability of Eq. (1) (real parts of traces, bits as Booleans); the one-way forms () and (); causal separability (Eq. (6)); the Pauli matrices, the process matrix of Eq. (7), Alice's instrument (Eq. (20)) and Bob's (Eqs. (21)–(23), with Bob's prepared state as a parameter); Hilbert–Schmidt bases (Appendix C) and the allowed term types of Fig. 3.
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
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 . A product index type is indexed by pairs . The Kronecker product of (indexed by ) and (indexed by ) is the matrix indexed by with entries . "Positive semidefinite" (PSD) means Hermitian with for every complex vector , using the partial order on in which means is a nonnegative real. is the identity matrix of the appropriate index type, and is the usual trace, the sum of the diagonal entries. Bipartite operators in this file are indexed by , so a row index has the form with , , , . The subsystem names refer to these four positions. The imported dependency file is not used by any definition here.
ptrace₂ (partial trace over the second factor). Let be any type and a finite type ( need not be finite). For a complex matrix indexed by , is the matrix indexed by with
If is empty, the result is the zero matrix.
IsCPTP_CJ. Let be finite types, where has decidable equality. For indexed by , the predicate holds iff
- is positive semidefinite, and
- , where the partial trace is over the second factor as in
ptrace₂.
Edge cases:
- If is empty, the only such matrix is the empty matrix, and it satisfies the predicate.
- If is empty and is nonempty, , so no matrix satisfies it.
prob. Let be finite types. For a matrix indexed by , a matrix indexed by and a matrix indexed by ,
This is a complex number. Nothing is assumed about , or .
IsProcessMatrix. Let be finite types, with decidable equality on and . A matrix indexed by is a process matrix iff
- is positive semidefinite, and
- for every indexed by and every indexed by such that both satisfy
IsCPTP_CJ, the complex number equals exactly .
IsCPTP_CJ here means PSD, with partial trace over (respectively ) equal to the identity on (respectively ).
Edge case: if no matrix satisfies IsCPTP_CJ on one side (for example empty and nonempty), condition 2 is vacuous, and every PSD qualifies.
IsAliceInstrument. Let be finite types, with decidable equality on . The input is a family of matrices indexed by , where range over the Booleans. The first argument is called the guess and the second argument is called the input. The predicate holds iff
- every is positive semidefinite, and
- for each , the sum satisfies
IsCPTP_CJ. That is, the sum is PSD and its partial trace over equals .
IsBobInstrument. Let be finite types, with decidable equality on . The input is a family of matrices indexed by , with three Boolean arguments. The first argument is (the guess), then , then . The predicate holds iff
- every is PSD, and
- for each pair , the sum satisfies
IsCPTP_CJ. That is, the sum is PSD and its partial trace over equals .
pSucc. Let be finite types. Given:
- a matrix indexed by ,
- a family of matrices on indexed by two Booleans, and
- a family of matrices on indexed by three Booleans,
the real number is defined by
How the Booleans are used:
- In the first sum, the first argument of is set equal to , and .
- In the second sum, the first argument of is set equal to , and .
- 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 , or : they need not be PSD, a process matrix or instruments.
IsNoSignalAtoB. Let be arbitrary types (no finiteness required), with decidable equality on . The predicate holds for indexed by iff there exists a complex matrix , indexed by , such that for all indices
In words, is the identity on tensored with on the remaining factors , with the factors reordered. No positivity, trace or other condition is placed on .
IsNoSignalBtoA. Let be arbitrary types, with decidable equality on . The predicate holds for indexed by iff there exists a complex matrix , indexed by , such that for all indices
In words, is the identity on tensored with an unconstrained on .
IsCausallySeparable. Let be finite types, all with decidable equality. A matrix indexed by is causally separable iff there exist:
- a real number with , and
- two matrices and of the same shape,
such that
- is a process matrix (
IsProcessMatrix) and has the form ofIsNoSignalBtoA(identity on ), - is a process matrix and has the form of
IsNoSignalAtoB(identity on ), and - the following equality holds, with and embedded as complex scalars:
Qubit. This is the two-element index type .
σx. The complex matrix , with rows and columns indexed by .
σz. The matrix , so and .
sgn. For a Boolean , equals if and if . Under the encoding true , false , this is .
W7. This is the complex matrix indexed by given by
is computed as a real number (positive square root) and then embedded in .
Read off by position :
- The first term acts as on , on , on and on .
- The second term acts as on , on , on and on .
ξ. For Booleans , is the matrix indexed by given by
The first Kronecker factor, which depends on , occupies the first index position.
η. For an arbitrary complex matrix and Booleans , is the matrix indexed by given by
where is Boolean exclusive or. When , the value does not depend on . No condition is placed on : it need not be PSD, Hermitian or of unit trace.
HSBasis X (a structure). Let be a finite type with decidable equality, and let . An element of HSBasis X consists of the following data and conditions.
Data:
- a type (in the lowest universe), equipped with finiteness and decidable equality, and
- a family of complex matrices indexed by , for .
Conditions:
- every is Hermitian,
- for all ,
- if and if , for all , and
- .
Edge cases:
- If is empty, then and condition 4 cannot hold, so no such structure exists.
- If , then is empty.
HSBasis.σ. Given in HSBasis X, define for in (an option type) by and for .
AllowedType. This is a predicate on four Booleans , where true is read as the proposition "true". It holds iff
Exactly 8 of the 16 tuples satisfy it. Listing the set of variables that are true:
The code gives the Booleans no meaning beyond their positions, and nothing links them to HSBasis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.