The inverse-permutation matrix
DefinitionICSCompute_Supplement_permInvMatcomplexity-theoryindefinite-causal-orderp2o-gran-per-chapterp2o-plan-paperp2o-v1process-matricesquantum-information
For a map , let
the matrix whose entry is exactly when . When is a permutation, for every and is a permutation matrix, hence unitary. It is the generated unitary of the permutation-inversion construction (Theorem 5.3, eq. (5.6)).
Formalization Note The matrix is defined for every map ; Theorem 5.3 assumes bijective.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Basic
namespace ICSCompute.Supplement
open QAlgorithms
/-- **The inverse-permutation unitary `U_{π⁻¹}`** (Shmueli, *What Can Be Computed with Indefinite
Causal Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Theorem 5.3,
eq. (5.6), p.30 (PDF p.32): `U_{π⁻¹}|y⟩ := |π⁻¹(y)⟩`).
For `π : {0,1}ⁿ → {0,1}ⁿ`, the `0/1` matrix with `(a, b)` entry `1` iff `π(a) = b`, i.e.
`∑_x |x⟩⟨π(x)|`. When `π` is a bijection it sends `|y⟩` to `|π⁻¹(y)⟩` and is a permutation
matrix, hence unitary.
**Formalization Note** Bits are `Bool`, `Qubits n = Fin n → Bool`; the matrix is defined for
every map `π`, and the theorems using it assume `π` bijective. -/
def permInvMat {n : ℕ} (π : Qubits n → Qubits n) : Matrix (Qubits n) (Qubits n) ℂ :=
Matrix.of fun a b => if π a = b then 1 else 0
end ICSCompute.Supplement
Source
Shmueli, What Can Be Computed with Indefinite Causal Structure?, arXiv:2610.40573 (version of 2026-11-03, sha256 d3e36399…b606), Theorem 5.3, eq. (5.6), p.30 (PDF p.32)