Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 2.3 — existence of the random purification channel RPC(d,r,n)\mathrm{RPC}^{(d,r,n)}RPC(d,r,n)

Open
MixedCloning.Optimal.rpc_exists

by dmitry · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

quantum-channelsquantum-cloningrandom-purification

Fix integers d≥1d\ge1d≥1, 1≤r≤d1\le r\le d1≤r≤d and n≥0n\ge0n≥0. Let A1,…,AnA_1,\dots,A_nA1​,…,An​ be copies of Cd\mathbb C^dCd and B1,…,BnB_1,\dots,B_nB1​,…,Bn​ copies of Cr\mathbb C^rCr. There exists a quantum channel (a linear, completely positive, trace-preserving map, given by a normalized Kraus family)

RPC(d,r,n): L((Cd)⊗n)→L((Cd⊗Cr)⊗n)\mathrm{RPC}^{(d,r,n)}:\ \mathrm{L}\big((\mathbb C^d)^{\otimes n}\big)\to\mathrm{L}\big((\mathbb C^d\otimes\mathbb C^r)^{\otimes n}\big)RPC(d,r,n): L((Cd)⊗n)→L((Cd⊗Cr)⊗n)

with the following property. For every state ρ\rhoρ on Cd\mathbb C^dCd of rank at most rrr, and every unit vector ∣ρ0⟩∈Cd⊗Cr|\rho_0\rangle\in\mathbb C^d\otimes\mathbb C^r∣ρ0​⟩∈Cd⊗Cr with tr⁡B∣ρ0⟩⟨ρ0∣=ρ\operatorname{tr}_B|\rho_0\rangle\langle\rho_0|=\rhotrB​∣ρ0​⟩⟨ρ0​∣=ρ,

RPC(d,r,n)(ρ⊗n)=∫U(r)((I⊗U) ∣ρ0⟩⟨ρ0∣ (I⊗U†))⊗n dU,\mathrm{RPC}^{(d,r,n)}\big(\rho^{\otimes n}\big)=\int_{\mathrm U(r)}\Big((I\otimes U)\,|\rho_0\rangle\langle\rho_0|\,(I\otimes U^\dagger)\Big)^{\otimes n}\,dU,RPC(d,r,n)(ρ⊗n)=∫U(r)​((I⊗U)∣ρ0​⟩⟨ρ0​∣(I⊗U†))⊗ndU,

where dUdUdU is the normalized Haar measure on the unitary group U(r)\mathrm U(r)U(r).

This is the random purification channel of Tang, Wright and Zhandry, as stated in Section 2.3 of the source. It maps nnn copies of a mixed state of rank at most rrr to nnn copies of a consistent but Haar-random purification on Cd⊗Cr\mathbb C^d\otimes\mathbb C^rCd⊗Cr. It is the first stage of the purify–clone–trace (PCT) cloner and is exactly the second clause of Theorem 1.

Formalization Note The specification is the platform predicate IsRPC d r n R. The displayed identity is required for every purification ∣ρ0⟩|\rho_0\rangle∣ρ0​⟩ in Cd⊗Cr\mathbb C^d\otimes\mathbb C^rCd⊗Cr, not just for one fixed choice, matching the source, where ∣ρ0⟩|\rho_0\rangle∣ρ0​⟩ may be any fixed purification of ρ\rhoρ. Tensor registers are ordered as (A1B1)⋯(AnBn)(A_1B_1)\cdots(A_nB_n)(A1​B1​)⋯(An​Bn​), and the case n=0n=0n=0 is included, where the empty tensor power is one-dimensional.

Differences from the source:

  • restriction: any r≥1r\ge1r≥1 → 1≤r≤d1\le r\le d1≤r≤d; reason: matches the parameter range of Theorem 1, whose second clause this statement is; Section 2.3 itself imposes no upper bound on rrr
  • generalization: n≥1n\ge1n≥1 copies → every n≥0n\ge0n≥0; reason: for n=0n=0n=0 both sides are the trivial one-dimensional state, matching clause 2 of Theorem 1
  • encoding: the action for one fixed purification ∣ρ0⟩|\rho_0\rangle∣ρ0​⟩ → the same identity for every unit purification in Cd⊗Cr\mathbb C^d\otimes\mathbb C^rCd⊗Cr; reason: the source allows any fixed purification, so the channel must satisfy the identity for each choice
Preamble
import Definitions.Def_MixedCloning_Optimal_Model

noncomputable section
open Matrix MeasureTheory
open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise
Formal statement
namespace MixedCloning.Optimal
attribute [local instance] Classical.propDecidable Classical.decEq

/-- Section 2.3 (PDF p.12), citing Tang–Wright–Zhandry [TWZ25]: for every number of
copies `n` there is a random purification channel `RPC^{(d,r,n)}`, i.e. a channel whose
action on every `ρ^{⊗n}` with `rank ρ ≤ r` is the Haar average of `n` copies of a random
purification of `ρ` in `ℂ^d ⊗ ℂ^r` (the specification `IsRPC`). -/
theorem rpc_exists (d r n : ℕ) (hd : 1 ≤ d) (hr : 1 ≤ r) (hrd : r ≤ d) :
    ∃ R : QAlgorithms.Superop (Word (Fin d) n) (Word (Fin d × Fin r) n), IsRPC d r n R := by sorry

end MixedCloning.Optimal
Source
Dmitry Grinko, Marco Fanizza, Thilo Scharnhorst, Jack Spilecki, Optimal cloning of mixed states, STOC 2027 submission #243 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/243.pdf, p. 12, Section 2.3 (existence of RPC(d,r,n), attributed to [TWZ25] E. Tang, J. Wright, M. Zhandry, Conjugate queries can help, 2025); this is clause 2 of Theorem 1 (p. 4).

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