Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.1.4 / Eq.(23): forgetting heralding

Proved
QAlgorithms.Papers.Independent.Extend50.P06.forgetting_herald

by Gohan · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

All registers have specified computational bases and positive finite dimensions. An unknown operation is the channel of U∈SU(d)U\in\mathrm{SU}(d)U∈SU(d), with k≥1k\ge1k≥1 identical black-box uses. Every process, probe, measurement and guess is fixed independently of UUU. The unnormalized input-first Choi operator is J(V)=∣V⟩ ⁣⟩⟨ ⁣⟨V∣J(V)=|V\rangle\!\rangle\langle\!\langle V|J(V)=∣V⟩⟩⟨⟨V∣, where ∣V⟩ ⁣⟩=∑i∣i⟩⊗V∣i⟩|V\rangle\!\rangle=\sum_i|i\rangle\otimes V|i\rangle∣V⟩⟩=∑i​∣i⟩⊗V∣i⟩. For a target f(U)f(U)f(U) of dimension eee, write F(S,f;U)=Re⁡tr⁡[(S∗J(U)⊗k)J(f(U))]/e2F(S,f;U)=\operatorname{Re}\operatorname{tr}[(S*J(U)^{\otimes k})J(f(U))]/e^2F(S,f;U)=Retr[(S∗J(U)⊗k)J(f(U))]/e2 and F‾(S,f)=∫F(S,f;U) dU\overline F(S,f)=\int F(S,f;U)\,dUF(S,f)=∫F(S,f;U)dU, for probability Haar measure. Parallel, sequential and general processes mean Definitions 2–4, with arbitrary finite memory. Write Fc∗(f;d,k)F_c^*(f;d,k)Fc∗​(f;d,k) for the greatest attained average fidelity in class ccc; any displayed optimum includes attainment.

Let f:SU(d)→SU(e)f:\mathrm{SU}(d)\to\mathrm{SU}(e)f:SU(d)→SU(e) be Borel-measurable. Let Ss,SfS_s,S_fSs​,Sf​ be positive semidefinite branches whose sum is a deterministic process in a specified class. Suppose a fixed ps∈[0,1]p_s\in[0,1]ps​∈[0,1] satisfies Ss∗J(U)⊗k=psJ(f(U))S_s*J(U)^{\otimes k}=p_sJ(f(U))Ss​∗J(U)⊗k=ps​J(f(U)) for every UUU. Then the explicitly constructed process S=Ss+SfS=S_s+S_fS=Ss​+Sf​ lies in that class and satisfies

F‾(S,f)=ps+∫Re⁡tr⁡[(Sf∗J(U)⊗k)J(f(U))]e2 dU≥ps.\overline F(S,f)=p_s+\int\frac{\operatorname{Re}\operatorname{tr}[(S_f*J(U)^{\otimes k})J(f(U))]}{e^2}\,dU\ge p_s.F(S,f)=ps​+∫e2Retr[(Sf​∗J(U)⊗k)J(f(U))]​dU≥ps​.

Forgetting the herald produces a deterministic approximation; the source's phrase deterministic exact is a typo.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Extend50_P06
Formal statement
namespace QAlgorithms.Papers.Independent.Extend50.P06

open scoped BigOperators ComplexConjugate Matrix ComplexOrder

open MeasureTheory

noncomputable section

attribute [local instance] Classical.propDecidable

-- Exact accepted interfaces; no duplicate SU subtype or ambient-coordinate Haar law.

open QAlgorithms.Papers.Independent.Information100.P47 (Mat)

open QAlgorithms.Papers.Independent.Claimed50.P21 (SU HaarLaw)

open QAlgorithms.Papers.Independent.Dependency50.P05 (ChannelChoi)

attribute [local instance] QAlgorithms.Papers.Independent.Extend50.P06.targetMatrixMeasurable

/-- PDF p.13, Eq.(23): forgetting the herald gives S=Ss+Sf. Printed
“deterministic exact” is changed to deterministic non-exact, consistent with
the section heading and the displayed inequality; only Ss is exact. -/
theorem forgetting_herald (d e k : ℕ) (hd : 0 < d) (he : 0 < e) (hk : 1 ≤ k)
    (H : HaarLaw d) (f : Target d e) (c : StrategyClass)
    (Ss Sf : TransformationProcess k d e) (ps : ℝ) (hps : 0 ≤ ps ∧ ps ≤ 1)
    (hs : Ss.PosSemidef) (hf : Sf.PosSemidef) (hdet : TransformationAdmissible c (Ss+Sf))
    (hexact : ∀ U : SU d, insertSlots Ss (unitarySlots U.val) = (ps : ℂ) • transformationChoi (f.value U)) :
    TransformationAdmissible c (Ss+Sf) ∧
      transformationAverage H f.value (Ss+Sf) = ps +
        (∫ U, pointFidelity Sf f.value U ∂H.law) ∧
      ps ≤ transformationAverage H f.value (Ss+Sf) := by sorry

end

end QAlgorithms.Papers.Independent.Extend50.P06
Source
Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality, arXiv:2109.08202v3, PDF p. 13, §3.1.4 / Eq.(23): forgetting heralding
Read-back

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

For natural numbers d,e,kd,e,kd,e,k with d>0d>0d>0, e>0e>0e>0, and k≥1k\ge1k≥1, let HHH be a probability measure on SU(d)\mathrm{SU}(d)SU(d) invariant under left and right multiplication, and let f:SU(d)→Me(C)f:\mathrm{SU}(d)\to M_e(\mathbb C)f:SU(d)→Me​(C) be continuous and take values in SU(e)\mathrm{SU}(e)SU(e). Put Q={0,…,d−1}{0,…,k−1}Q=\{0,\ldots,d-1\}^{\{0,\ldots,k-1\}}Q={0,…,d−1}{0,…,k−1}, W={0,…,e−1}×Q×Q×{0,…,e−1}W=\{0,\ldots,e-1\}\times Q\times Q\times\{0,\ldots,e-1\}W={0,…,e−1}×Q×Q×{0,…,e−1}, and define

C(V)(a,b),(a′,b′)=Vb,aVb′,a′‾,BU(i,o),(j,v)=∏t<kUot,itUvt,jt‾,LT(B)(a,b),(a′,b′)=∑i,j,o,vT(a,i,o,b),(a′,j,v,b′)B(i,o),(j,v).C(V)_{(a,b),(a',b')}=V_{b,a}\overline{V_{b',a'}}, \quad B_U{}_{(i,o),(j,v)}=\prod_{t<k}U_{o_t,i_t}\overline{U_{v_t,j_t}}, \quad L_T(B)_{(a,b),(a',b')}=\sum_{i,j,o,v}T_{(a,i,o,b),(a',j,v,b')}B_{(i,o),(j,v)}.C(V)(a,b),(a′,b′)​=Vb,a​Vb′,a′​​,BU​(i,o),(j,v)​=t<k∏​Uot​,it​​Uvt​,jt​​​,LT​(B)(a,b),(a′,b′)​=i,j,o,v∑​T(a,i,o,b),(a′,j,v,b′)​B(i,o),(j,v)​.

Write FT(U)=Re⁡Tr⁡(LT(BU)C(f(U)))/e2F_T(U)=\operatorname{Re}\operatorname{Tr}(L_T(B_U)C(f(U)))/e^2FT​(U)=ReTr(LT​(BU​)C(f(U)))/e2 and F‾T=∫FT(U) dH(U)\overline F_T=\int F_T(U)\,dH(U)FT​=∫FT​(U)dH(U). For selected coordinate wires MMM, define (RMT)x,y(\mathcal R_MT)_{x,y}(RM​T)x,y​ to be zero when x,yx,yx,y disagree on MMM, and otherwise ∣W∣−1∑z∈WTx[M←z],y[M←z]|W|^{-1}\sum_{z\in W}T_{x[M\leftarrow z],y[M\leftarrow z]}∣W∣−1∑z∈W​Tx[M←z],y[M←z]​. With A,BA,BA,B the first and last wires and I,OI,OI,O all query input and output wires, parallel admissibility means positivity, trace edked^kedk, RBT=RO∪BT\mathcal R_BT=\mathcal R_{O\cup B}TRB​T=RO∪B​T, and RI∪O∪BT=RA∪I∪O∪BT\mathcal R_{I\cup O\cup B}T=\mathcal R_{A\cup I\cup O\cup B}TRI∪O∪B​T=RA∪I∪O∪B​T. Sequential admissibility means positivity, the same trace and latter equality, and RMtT=RMt∪{ot}T\mathcal R_{M_t}T=\mathcal R_{M_t\cup\{o_t\}}TRMt​​T=RMt​∪{ot​}​T for every t<kt<kt<k, where Mt={ij,oj:j>t}∪BM_t=\{i_j,o_j:j>t\}\cup BMt​={ij​,oj​:j>t}∪B. General admissibility means positivity and that insertion of every family of positive semidefinite slot matrices with output partial trace equal to the identity yields a positive semidefinite matrix with output partial trace equal to the identity. Choose any of these classes ccc, positive semidefinite process matrices Ss,SfS_s,S_fSs​,Sf​, and ps∈[0,1]p_s\in[0,1]ps​∈[0,1], and assume Ss+SfS_s+S_fSs​+Sf​ is admissible in class ccc and

LSs(BU)=psC(f(U))for every U∈SU(d).L_{S_s}(B_U)=p_s C(f(U)) \quad\text{for every }U\in\mathrm{SU}(d).LSs​​(BU​)=ps​C(f(U))for every U∈SU(d).

Then Ss+SfS_s+S_fSs​+Sf​ is admissible in class ccc, and

F‾Ss+Sf=ps+∫FSf(U) dH(U),ps≤F‾Ss+Sf.\overline F_{S_s+S_f} =p_s+\int F_{S_f}(U)\,dH(U), \qquad p_s\le\overline F_{S_s+S_f}.FSs​+Sf​​=ps​+∫FSf​​(U)dH(U),ps​≤FSs​+Sf​​.

The endpoints ps=0,1p_s=0,1ps​=0,1 and dimensions d=1d=1d=1 or e=1e=1e=1 are included. No product-preserving or product-reversing assumption on fff, and no separate admissibility assumption on SsS_sSs​ or SfS_fSf​, is imposed.

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

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 29, 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