Purifiable process matrices and purifiable PMGs
DefinitionICSCompute_Supplement_IsPurifiablePMGLet be a process matrix (Definition 4.4) with single-qubit feedback pairs, feedback input , feedback output , external input and external output . Then is purifiable if there are additional external qubit registers , and a unitary
such that
- , where , is a process matrix for the same feedback pairs with external input and external output ;
- initializing to and discarding recovers : with ,
A circuit description is a purifiable PMG if is a purifiable process matrix for its feedback pairs (Definition 4.10). Purifiability, proposed by Araújo, Feix, Navascués and Brukner as a physicality condition, is the extra condition on valid generation queries in Theorem 1.1.
Formalization Note The extension is a unitary matrix, not a circuit: no circuit for , size bound or constructibility is required, as the paper states after Definition 4.10. Registers are indexed input first, , as in the mission's published process-matrix layer. The predicate contains the standing hypothesis that itself is a process matrix, so a purifiable PMG is in particular a PMG.
import Mathlib
import Definitions.Def_ICSCompute_IsProcessMatrix
import Definitions.Def_ICSCompute_IsPurePMG
namespace ICSCompute.Supplement
open QAlgorithms
/-- The operator `|U⟩⟩⟨⟨U|` of a matrix `U ∈ L(H_α, H_β)` (Shmueli, arXiv:2610.40573,
Definition 4.1, p.18 (PDF p.20): `|M⟩⟩ := ∑_x |x⟩ ⊗ M|x⟩`), indexed input first: its
`((a, b), (a', b'))` entry is `U_{b a} · conj(U_{b' a'})`. For `U` unitary this is the Choi
operator `CJ(Ad U)` of Definition 3.14. -/
def choiOp {α β : Type*} (U : Matrix β α ℂ) : Matrix (α × β) (α × β) ℂ :=
Matrix.of fun a b => U a.2 a.1 * star (U b.2 b.1)
/-- **Purifiable process matrix** (Shmueli, *What Can Be Computed with Indefinite Causal
Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Definition 4.9,
p.21 (PDF p.23)). A process matrix `W` with feedback input `R`, feedback output `S`, external
input `P` and external output `F` is purifiable if there are additional external registers
`P′`, `F′` and a unitary `U : H_R ⊗ H_P ⊗ H_{P′} → H_S ⊗ H_F ⊗ H_{F′}` such that
1. `W̃ := |U⟩⟩⟨⟨U|` is a process matrix for the same feedback pairs, with external input
`P, P′` and external output `F, F′`;
2. with `V := U (I_{H_R ⊗ H_P} ⊗ |0⟩_{P′})`, `W = Tr_{F′}(|V⟩⟩⟨⟨V|)`.
**Formalization Note** `n` separate single-qubit feedback pairs, `R = S(n)` (`AI`) and
`S = S(n)` (`AO`), with the base mission's input-first indexing `((R, P), (S, F))`. `P′ = S(p′)`
and `F′ = S(f′)` are qubit registers of arbitrary size (zero allowed). `U` is a matrix from
`R × (P × P′)` to `S × (F × F′)` with `U†U = I` and `UU† = I` (so the dimensions agree); no
circuit for `U`, no size bound and no constructibility is required (p.22). Condition 2 is written
entrywise: `W((x, p), (s, f)), ((x′, p″), (s′, f″)) = ∑_g V((s, (f, g)), (x, p)) ·
conj V((s′, (f″, g)), (x′, p″))` with `V((s, (f, g)), (x, p)) = U((s, (f, g)), (x, (p, 0)))`.
The clause `IsProcessMatrix W` records the definition's standing hypothesis "Let `W` be a
process matrix". -/
def IsPurifiable {n : ℕ} {P F : Type*} [Fintype P] [DecidableEq P] [Fintype F] [DecidableEq F]
(W : Matrix ((Qubits n × P) × (Qubits n × F)) ((Qubits n × P) × (Qubits n × F)) ℂ) :
Prop :=
IsProcessMatrix W ∧
∃ (p' f' : ℕ) (U : Matrix (Qubits n × (F × Qubits f')) (Qubits n × (P × Qubits p')) ℂ),
U.conjTranspose * U = 1 ∧ U * U.conjTranspose = 1 ∧
IsProcessMatrix (n := n) (P := P × Qubits p') (F := F × Qubits f') (choiOp U) ∧
∀ a b, W a b = ∑ g : Qubits f',
U (a.2.1, (a.2.2, g)) (a.1.1, (a.1.2, fun _ => false)) *
star (U (b.2.1, (b.2.2, g)) (b.1.1, (b.1.2, fun _ => false)))
/-- **Purifiable process matrix generator** (Shmueli, *What Can Be Computed with Indefinite
Causal Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606,
Definition 4.10, p.22 (PDF p.24)): "Let `D = (n, C)` be a PMG as in Definition 4.5. We say that
`D` is purifiable if `CJ(𝒞_C)` is a purifiable process matrix according to Definition 4.9, with
the same `n` separate single-qubit feedback pairs."
**Formalization Note** `IsPurifiable` contains `IsProcessMatrix (choiW D)`, which is `IsPMG D`,
so the PMG hypothesis of the definition is part of this predicate. The circuit `C` may discard
wires; purifiability asks for a unitary matrix, not a unitary circuit (p.22: "The existence of
such a circuit over our fixed gate set, its size, and the complexity of constructing it are
additional requirements, not part of purifiability"). -/
def IsPurifiablePMG {n r ℓ : ℕ} (D : Desc n r ℓ) : Prop :=
IsPurifiable (choiW D)
end ICSCompute.Supplement