Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unassisted codes embed in cpp codes

Proved
QAlgorithms.Papers.Independent.Support50.P04.unassisted_in_cpp

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let N:A→B\mathcal N:A\to BN:A→B be a CPTP channel on finite positive-dimensional complex Hilbert spaces with fixed orthonormal bases. Write R^(n;ε)\widehat R(n;\varepsilon)R(n;ε) and R^cpp(n;ε)\widehat R^{\mathrm{cpp}}(n;\varepsilon)Rcpp(n;ε) for the maximum unassisted and classical-post-processing assisted entanglement-transmission rates. A code has a positive integer message dimension MMM, rate log⁡2M/n\log_2 M/nlog2​M/n, and squared fidelity to the normalized maximally entangled target at least 1−ε1-\varepsilon1−ε. A cpp encoder may retain sender memory; its decoder is LOCC across that memory and the receiver outputs, with its final quantum output at the receiver and no preshared entanglement. For every actual unassisted encoder/decoder code CCC for one possibly blocked channel N\mathcal NN, there is an actual cpp code DDD with

dim⁡QD=1,MD=MC,F(N,D)=F(N,C).\dim Q_D=1,\qquad M_D=M_C,\qquad F(\mathcal N,D)=F(\mathcal N,C).dimQD​=1,MD​=MC​,F(N,D)=F(N,C).

Thus every feasible unassisted rate/error pair remains feasible with cpp assistance.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P04
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder

open QAlgorithms

namespace QAlgorithms.Papers.Independent.Support50.P04

variable {A B E : Type} [Fintype A] [DecidableEq A]

variable [Fintype B] [DecidableEq B] [Fintype E] [DecidableEq E]

/-- arXiv:1504.04617v2, PDF p.10: every actual unassisted code is a cpp code
with one-dimensional sender memory, preserving the SAME message size and fidelity. -/
theorem unassisted_in_cpp [Nonempty A] [Nonempty B]
    (N : Superop A B) (hN : IsChannel N) (C : QAlgorithms.Papers.Independent.Information100.P80.TransmissionCode A B) :
    ∃ D : CppCode A B, D.q = 1 ∧ D.M = C.M ∧
      cppFidelity N D = QAlgorithms.Papers.Independent.Information100.P80.transmissionFidelity N C := by sorry

end QAlgorithms.Papers.Independent.Support50.P04

end
Source
Quantum Coding with Finite Resources, arXiv:1504.04617v2, PDF p. 10, §III.B, final paragraph
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let A,BA,BA,B be arbitrary finite nonempty types with decidable equality, let N\mathcal NN be a channel from matrices on AAA to matrices on BBB, and let CCC consist of a positive integer MMM, a channel E:M→A\mathcal E:M\to AE:M→A, and a channel D:B→M\mathcal D:B\to MD:B→M. Here a channel is a map with a finite Kraus representation X↦∑jEjXEj†X\mapsto\sum_jE_jXE_j^\daggerX↦∑j​Ej​XEj†​, ∑jEj†Ej=I\sum_jE_j^\dagger E_j=I∑j​Ej†​Ej​=I. Define

FC=Re⁡tr⁡ ⁣[ΦM(id⊗(D∘N∘E))(ΦM)],ΦM=M−1∑i,j∣i,i⟩⟨j,j∣.F_C=\operatorname{Re}\operatorname{tr}\!\left[ \Phi_M\bigl(\mathrm{id}\otimes(\mathcal D\circ\mathcal N\circ\mathcal E)\bigr)(\Phi_M) \right], \qquad \Phi_M=M^{-1}\sum_{i,j}|i,i\rangle\langle j,j|.FC​=Retr[ΦM​(id⊗(D∘N∘E))(ΦM​)],ΦM​=M−1i,j∑​∣i,i⟩⟨j,j∣.

The theorem asserts that there is another code DDD with retained-memory dimension exactly q=1q=1q=1, logical dimension exactly MMM, a channel A:M→(A×q)\mathcal A:M\to(A\times q)A:M→(A×q), and a channel B:(q×B)→M\mathcal B:(q\times B)\to MB:(q×B)→M, whose fidelity is exactly FCF_CFC​, where its effective map first applies A\mathcal AA, swaps the output factors, applies idq⊗N\mathrm{id}_q\otimes\mathcal Nidq​⊗N, and then applies B\mathcal BB, and its fidelity uses the same displayed expression with that effective map. In addition, B\mathcal BB must satisfy the receiver restriction: there exist positive integers a,ba,ba,b, isometries W:q→aW:q\to aW:q→a, V:B→bV:B\to bV:B→b, a map L\mathcal LL on a×ba\times ba×b, and a channel F:b→M\mathcal F:b\to MF:b→M, such that B(X)=F(tr⁡aL((W⊗V)X(W⊗V)†))\mathcal B(X)=\mathcal F(\operatorname{tr}_a\mathcal L((W\otimes V)X(W\otimes V)^\dagger))B(X)=F(tra​L((W⊗V)X(W⊗V)†)). The condition on L\mathcal LL is a limit of compatible finite local histories: an instrument has completely positive complex-linear branches, summable branch outputs for every matrix, and a trace-preserving total; complete positivity requires positivity under every finite identity amplification. A local round has tensor-product branches, one party’s maps forming a countable-outcome instrument and the other party’s maps being channels conditional on that outcome. Raw histories start with one local round and extend by an outcome-dependent local round on every previous history, with the fixed pairing of natural-number labels. There must be raw instruments KjK_jKj​, each with a positive finite number of rounds and with Kj+1K_{j+1}Kj+1​ extending KjK_jKj​ by one round, and single-outcome instruments AjA_jAj​ coarse-grained from KjK_jKj​ by summing over fibers of outcome-label functions, such that

sup⁡ω density on (a×b)⊗(a×b)∥(id⊗(Aj−L))(ω)∥1⟶0.\sup_{\omega\text{ density on }(a\times b)\otimes(a\times b)} \|(\mathrm{id}\otimes(A_j-\mathcal L))(\omega)\|_1\longrightarrow0.ω density on (a×b)⊗(a×b)sup​∥(id⊗(Aj​−L))(ω)∥1​⟶0.

Here ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. The assertion is exact equality of fidelities and dimensions; no error parameter or asymptotic limit is involved.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

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