Theorem 5.3 — permutation inversion: a polynomial-time PMG generating
OpenICSCompute.Supplement.theorem_5_3complexity-theoryindefinite-causal-orderp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1process-matricesquantum-information
There is a deterministic polynomial-time algorithm that, given an ordinary classical circuit for a permutation , outputs a circuit description with external input and output qubits such that
- is a PMG;
- is unitary and , i.e. , eq. (5.6);
- the generated channel is this unitary transformation: for every matrix , in particular on every superposition;
- it acts coherently on inputs entangled with additional registers: for every additional qubit register and every on ,
Inverting a permutation given by a small circuit is believed hard for ordinary quantum computers in general; here one generation query gives the inverse coherently.
Formalization Note The algorithm is one polynomial-time function on binary strings, from encBool c to encDesc D; correctness is required when the Boolean circuit computes a bijection . The number of feedback pairs of is existential.
Differences from the source:
- encoding: deterministic polynomial-time algorithm outputting a PMG → polynomial-time f with f (encBool c) = encDesc D, D : Desc m n n, m existential; reason: the base mission's convention for algorithms (paper.md decision 7)
- encoding: an ordinary classical circuit for a permutation π → BoolCircuit c with c.Computes π and π bijective; reason: the published Boolean circuit layer
- encoding: the generated channel is the unitary transformation |y⟩ ↦ |π⁻¹(y)⟩ → permInvMat π is unitary, sends |π(x)⟩ to |x⟩, and pmoD D X = U X U† for every X; reason: a channel fixes its unitary only up to phase; the identity on all matrices is the phase-free statement (as in the base goal)
- reading: acts coherently on arbitrary input superpositions and inputs entangled with additional registers → tensorId (pmoD D) X = (U ⊗ I) X (U ⊗ I)† for every qubit register S(k) and every X; reason: registers in the paper are qubit registers (§3, p.14)
- generalization: n ∈ ℕ (positive integers, p.19) → n : ℕ, including 0; reason: the Lean statement specializes to every positive value
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_ICSCompute_IsQuantumChannel import Definitions.Def_ICSCompute_IsPurePMG import Definitions.Def_ICSCompute_BoolCircuit import Definitions.Def_ICSCompute_encDesc import Definitions.Def_ICSCompute_Supplement_permInvMat
Formal statement
namespace ICSCompute.Supplement
open QAlgorithms
/-- **Theorem 5.3 (Permutation inversion)** (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)).
"There exists a deterministic polynomial-time algorithm that, given an ordinary classical circuit
for a permutation `π : {0,1}ⁿ → {0,1}ⁿ`, outputs a PMG whose generated channel is the unitary
transformation `|y⟩ ↦ |π⁻¹(y)⟩`. (5.6) In particular, this transformation acts coherently on
arbitrary input superpositions and inputs entangled with additional registers."
**Formalization Note** One polynomial-time `f : {0,1}* → {0,1}*` (`PvsNP.PolyTimeComputable`),
total on all strings, maps the code `encBool c` of the Boolean circuit to the code `encDesc D`
of a description `D = (m, C)` with `n` external input and output qubits (the number `m` of
feedback pairs is existential). Correctness is required when `c` computes a bijection `π`. The
clauses: `D` is a PMG; `U_{π⁻¹}` (`permInvMat π`, `∑_x |x⟩⟨π(x)|`) is unitary and sends `|π(x)⟩`
to `|x⟩`; the generated channel is `X ↦ U_{π⁻¹} X U_{π⁻¹}†` for every matrix `X` (every
superposition); and for every additional qubit register `S(k)` and every `X` on `S(n) ⊗ S(k)`,
`(PMO_D ⊗ id)(X) = (U_{π⁻¹} ⊗ I) X (U_{π⁻¹} ⊗ I)†` (entangled inputs). `n : ℕ` includes `0`. -/
theorem theorem_5_3 :
∃ f : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable f ∧
∀ (n : ℕ) (c : BoolCircuit) (π : Qubits n → Qubits n),
c.Computes π → Function.Bijective π →
∃ (m : ℕ) (D : Desc m n n), f (encBool c) = encDesc D ∧ IsPMG D ∧
permInvMat π ∈ Matrix.unitaryGroup (Qubits n) ℂ ∧
(∀ x : Qubits n, Matrix.mulVec (permInvMat π) (Pi.single (π x) 1) = Pi.single x 1) ∧
(∀ X : Matrix (Qubits n) (Qubits n) ℂ,
pmoD D X = permInvMat π * X * (permInvMat π).conjTranspose) ∧
∀ (k : ℕ) (X : Matrix (Qubits n × Qubits k) (Qubits n × Qubits k) ℂ),
tensorId (pmoD D) X =
Matrix.kronecker (permInvMat π) (1 : Matrix (Qubits k) (Qubits k) ℂ) * X *
(Matrix.kronecker (permInvMat π) (1 : Matrix (Qubits k) (Qubits k) ℂ)).conjTranspose := by sorry
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)