Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§VII.C, Fig.7: a PPT and NS operation requiring quantum forward assistance

Open
QAlgorithms.Papers.Independent.Support50.P11.bonus_operation_requires_quantum_forward_channel

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

prove2quantum

Define a two-qubit-input bipartite operation Z\mathcal ZZ as follows. Bob measures his input in the computational basis to obtain bbb, chooses an independent uniform bit rrr, and outputs rrr. Alice measures her input in the computational basis when b=0b=0b=0 and the Hadamard basis when b=1b=1b=1, obtains aaa, and outputs a⊕ra\oplus ra⊕r. Then Z\mathcal ZZ is CPTP, PPT-preserving and non-signalling in both directions. For every exact forward realization of this fixed operation using positive finite side registers, CPTP encoder EEE, side channel FFF and decoder DDD,

Z=(id⁡⊗D)∘(id⁡⊗F⊗id⁡)∘(E⊗id⁡),\mathcal Z=(\operatorname{id}\otimes D)\circ(\operatorname{id}\otimes F\otimes\operatorname{id})\circ(E\otimes\operatorname{id}),Z=(id⊗D)∘(id⊗F⊗id)∘(E⊗id),

with the tensor reordering specified in the definition, there exist CPTP maps E0,D0E_0,D_0E0​,D0​ with

D0∘F∘E0=id⁡2.D_0\circ F\circ E_0=\operatorname{id}_2.D0​∘F∘E0​=id2​.

In particular FFF cannot be Horodecki. This is the separately defined operation of Fig.7, with a conclusion quantified over every exact forward implementation.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P11
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P11

open QAlgorithms.Papers.Independent.Information100.P34 (choi dephasing permutationMatrix)

open QAlgorithms.Papers.Independent.Information100.P21 (pt)

open QAlgorithms.Papers.Independent.Dependency50.P09 (tensorAction)

open QAlgorithms.Papers.Independent.Information100.P76 (swapMatrix)

open QAlgorithms.Papers.Independent.Information100.P69 (replacer)

open QAlgorithms.Papers.Independent.Gap20.P19 (wernerIsometry)

attribute [local instance] Classical.propDecidable

attribute [local instance] Classical.decEq

/-- PDF pp.12--13, section VII.C, Fig.7: this independently defined CPTP, PPT,
non-signalling operation forces every exact forward side channel to transmit a qubit
perfectly. This conclusion is not asserted for the different operation of Example 9. -/
theorem bonus_operation_requires_quantum_forward_channel :
    IsChannel bonusOperation ∧ NSBA bonusOperation ∧ NSAB bonusOperation ∧ PPTMap bonusOperation ∧
    ∀ q r : ℕ, 0 < q → 0 < r →
    ∀ E : Superop (Fin 2) (Fin 2 × Fin q),
    ∀ F : Superop (Fin q) (Fin r), ∀ D : Superop (Fin r × Fin 2) (Fin 2),
      IsChannel E → IsChannel F → IsChannel D → forwardOp E F D = bonusOperation →
        PerfectQubit F ∧ ¬ Horodecki F := by sorry

end QAlgorithms.Papers.Independent.Support50.P11

end
Source
On the power of PPT-preserving and non-signalling codes, arXiv:1406.7142v2, PDF p. 12, §VII.C, Fig.7: a PPT and NS operation requiring quantum forward assistance
Read-back

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

For indices a,b,i∈{0,1}a,b,i\in\{0,1\}a,b,i∈{0,1}, define m0ai=1i=am_{0ai}=\mathbf1_{i=a}m0ai​=1i=a​ and m1ai=(−1)ai/2m_{1ai}=(-1)^{ai}/\sqrt2m1ai​=(−1)ai/2​, and define a map B\mathcal BB on matrices indexed by {0,1}×{0,1}\{0,1\}\times\{0,1\}{0,1}×{0,1} by

B(X)u,v=1u=v 12∑b,a1u1=(a+u2) mod 2∑i,jmbai‾ X(i,b),(j,b) mbaj.\mathcal B(X)_{u,v} =\mathbf1_{u=v}\,\frac12 \sum_{b,a}\mathbf1_{u_1=(a+u_2)\bmod2} \sum_{i,j}\overline{m_{bai}}\,X_{(i,b),(j,b)}\,m_{baj}.B(X)u,v​=1u=v​21​b,a∑​1u1​=(a+u2​)mod2​i,j∑​mbai​​X(i,b),(j,b)​mbaj​.

This map is a channel: it has a finite representation B(X)=∑jKjXKj†\mathcal B(X)=\sum_jK_jXK_j^\daggerB(X)=∑j​Kj​XKj†​ with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. There exist channels E0,D0E_0,D_0E0​,D0​ such that, for every matrix XXX, tr⁡2B(X)=E0(tr⁡2X)\operatorname{tr}_2\mathcal B(X)=E_0(\operatorname{tr}_2X)tr2​B(X)=E0​(tr2​X) and tr⁡1B(X)=D0(tr⁡1X)\operatorname{tr}_1\mathcal B(X)=D_0(\operatorname{tr}_1X)tr1​B(X)=D0​(tr1​X); also Γ∘B∘Γ\Gamma\circ\mathcal B\circ\GammaΓ∘B∘Γ is a channel, where (ΓX)(a,b),(c,e)=X(a,e),(c,b)(\Gamma X)_{(a,b),(c,e)}=X_{(a,e),(c,b)}(ΓX)(a,b),(c,e)​=X(a,e),(c,b)​. Furthermore, for every pair of positive natural numbers q,rq,rq,r and every three maps

E:M2(C)→M2q(C),F:Mq(C)→Mr(C),D:M2r(C)→M2(C),E:M_2(\mathbb C)\to M_{2q}(\mathbb C),\qquad F:M_q(\mathbb C)\to M_r(\mathbb C),\qquad D:M_{2r}(\mathbb C)\to M_2(\mathbb C),E:M2​(C)→M2q​(C),F:Mq​(C)→Mr​(C),D:M2r​(C)→M2​(C),

if all three are channels and the map obtained by applying EEE to the first input subsystem, FFF to the qqq-dimensional part of its output, and DDD to that transmitted part together with the second input subsystem equals B\mathcal BB, then there exist channels E′:M2(C)→Mq(C)E':M_2(\mathbb C)\to M_q(\mathbb C)E′:M2​(C)→Mq​(C) and D′:Mr(C)→M2(C)D':M_r(\mathbb C)\to M_2(\mathbb C)D′:Mr​(C)→M2​(C) such that D′(F(E′(X)))=XD'(F(E'(X)))=XD′(F(E′(X)))=X for every complex 2×22\times22×2 matrix XXX. Precisely, the assumed composition is

(id⁡2⊗D)∘(id⁡2⊗F⊗id⁡2)∘(E⊗id⁡2),(\operatorname{id}_2\otimes D)\circ (\operatorname{id}_2\otimes F\otimes\operatorname{id}_2)\circ (E\otimes\operatorname{id}_2),(id2​⊗D)∘(id2​⊗F⊗id2​)∘(E⊗id2​),

with the factors reassociated in the indicated order. In addition, it is false that FFF is a channel whose Choi matrix JF(a,b),(c,e)=F(Eac)beJ_F{}_{(a,b),(c,e)}=F(E_{ac})_{be}JF​(a,b),(c,e)​=F(Eac​)be​ has positive semidefinite second-subsystem transpose ΓJF\Gamma J_FΓJF​; since FFF is already assumed to be a channel, this says ΓJF\Gamma J_FΓJF​ is not positive semidefinite.

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