Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 10, proof step — the PCT fidelity is at least the worst purification bound

Proved
MixedCloning.Optimal.pct_fidelity_ge_of_purifications

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

fidelityquantum-cloningrandom-purification

Fix natural numbers d,r,n,kd,r,n,kd,r,n,k. Let RRR be a random purification channel, that is, a channel satisfying the specification of Section 2.3:

R(ρ⊗n)=∫U(r)((I⊗U)∣ρ0⟩⟨ρ0∣(I⊗U†))⊗ndUR\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}dUR(ρ⊗n)=∫U(r)​((I⊗U)∣ρ0​⟩⟨ρ0​∣(I⊗U†))⊗ndU

for every state ρ\rhoρ of rank at most rrr and every unit purification ∣ρ0⟩∈Cd⊗Cr|\rho_0\rangle\in\mathbb C^d\otimes\mathbb C^r∣ρ0​⟩∈Cd⊗Cr of ρ\rhoρ. Let τ\tauτ be any matrix on (Cd⊗Cr)⊗(n+k)(\mathbb C^d\otimes\mathbb C^r)^{\otimes(n+k)}(Cd⊗Cr)⊗(n+k), let CW\mathcal C_WCW​ be Werner's cloner completed by τ\tauτ, and let CPCT=tr⁡B∘ CW∘R\mathcal C_{\mathrm{PCT}}=\operatorname{tr}_B\circ\,\mathcal C_W\circ RCPCT​=trB​∘CW​∘R be the PCT map. Let FFF be the squared fidelity.

Let ρ\rhoρ be a state on Cd\mathbb C^dCd of rank at most rrr, and let c∈Rc\in\mathbb Rc∈R. Suppose that every unit vector ∣ψ⟩∈Cd⊗Cr|\psi\rangle\in\mathbb C^d\otimes\mathbb C^r∣ψ⟩∈Cd⊗Cr with tr⁡B∣ψ⟩⟨ψ∣=ρ\operatorname{tr}_B|\psi\rangle\langle\psi|=\rhotrB​∣ψ⟩⟨ψ∣=ρ satisfies

c ≤ F(tr⁡B CW(∣ψ⟩⟨ψ∣⊗n), ρ⊗(n+k)).c\ \le\ F\Big(\operatorname{tr}_B\,\mathcal C_W\big(|\psi\rangle\langle\psi|^{\otimes n}\big),\ \rho^{\otimes(n+k)}\Big).c ≤ F(trB​CW​(∣ψ⟩⟨ψ∣⊗n), ρ⊗(n+k)).

Then

c ≤ F(CPCT(ρ⊗n), ρ⊗(n+k)).c\ \le\ F\Big(\mathcal C_{\mathrm{PCT}}\big(\rho^{\otimes n}\big),\ \rho^{\otimes(n+k)}\Big).c ≤ F(CPCT​(ρ⊗n), ρ⊗(n+k)).

This packages the first steps of the proof of Proposition 10. The PCT output is the expectation, over Haar-random purifications ∣ρ⟩|\rho\rangle∣ρ⟩, of tr⁡BCW(∣ρ⟩⟨ρ∣⊗n)\operatorname{tr}_B\mathcal C_W(|\rho\rangle\langle\rho|^{\otimes n})trB​CW​(∣ρ⟩⟨ρ∣⊗n). Concavity of the square-root fidelity [Wat18, Corollary 3.26] then bounds the fidelity of the average from below by the average fidelity. As the source puts it, a bound that holds for all ∣ρ⟩|\rho\rangle∣ρ⟩ therefore transfers to the PCT output.

Formalization Note The specification of RRR is the platform predicate IsRPC d r n R. The hypothesis quantifies over all unit purifications in Cd⊗Cr\mathbb C^d\otimes\mathbb C^rCd⊗Cr, which contains every (I⊗U)∣ρ0⟩(I\otimes U)|\rho_0\rangle(I⊗U)∣ρ0​⟩. The bound is stated for squared fidelity; for c<0c<0c<0 it is trivial, and for c≥0c\ge0c≥0 it follows from the square-root form.

Differences from the source:

  • encoding: the expectation-form inequality for F\sqrt FF​ followed by 'since this holds for all ∣ρ⟩|\rho\rangle∣ρ⟩' → a single implication from a pointwise lower bound ccc to the same bound on the PCT output; reason: this is exactly how the source combines the steps
  • encoding: Werner's map on the symmetric subspace → the map completed by an arbitrary τ\tauτ; reason: the completion term vanishes on the random purifications
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

/-- Proof of Proposition 10 (PDF p.16), first displays: the PCT output is the average over random
purifications of the traced Werner output, so by concavity of the square-root fidelity
[Wat18, Corollary 3.26] a lower bound valid for every purification transfers to the PCT output. -/
theorem pct_fidelity_ge_of_purifications (d r n k : ℕ)
    (R : QAlgorithms.Superop (Word (Fin d) n) (Word (Fin d × Fin r) n)) (hR : IsRPC d r n R)
    (tau : Op (Word (Fin d × Fin r) (n+k)))
    (rho : Op (Fin d)) (hrho : IsState rho) (hrank : rho.rank ≤ r) (c : ℝ)
    (hc : ∀ u : EuclideanSpace ℂ (Fin d × Fin r), ‖u‖ = 1 →
      (fun i j => ∑ z : Fin r, pure u (i,z) (j,z)) = rho →
      c ≤ fidelity (partialTrace (n+k) (werner (Fin d × Fin r) n k tau (tensorPower n (pure u))))
        (tensorPower (n+k) rho)) :
    c ≤ fidelity (pct d r n k R tau (tensorPower n rho)) (tensorPower (n+k) rho) := 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. 16, proof of Proposition 10: first display (C_PCT(rho^{⊗n}) = E_{|rho>} Tr_B C_W(|rho><rho|^{⊗n})), concavity of the square-root fidelity [Wat18, Corollary 3.26], and 'Since this holds for all |rho>, we obtain ...'; RPC specification from Section 2.3, p. 12.

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