Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§IV, unnumbered: asymptotically tight classical preparation cost

Open
QAlgorithms.Papers.Independent.Intakenext100.P61.harmonic_classical_cost

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

prove2quantum

Let εn≥0\varepsilon_n\ge0εn​≥0 tend to zero, and let ∣μn⟩=Hn−1/2∑i=1ni−1/2∣i,i⟩|\mu_n\rangle=H_n^{-1/2}\sum_{i=1}^ni^{-1/2}|i,i\rangle∣μn​⟩=Hn−1/2​∑i=1n​i−1/2∣i,i⟩, where Hn=∑i=1n1/iH_n=\sum_{i=1}^n1/iHn​=∑i=1n​1/i. For every slack s>0s>0s>0, there is N≥2N\ge2N≥2, uniform over EPR supplies and deterministic classical-only preparation protocols, such that for all n≥Nn\ge Nn≥N, unconditional squared fidelity at least 1−εn1-\varepsilon_n1−εn​ requires

C≥(1−s)log⁡2n.C\ge(1-s)\log_2 n.C≥(1−s)log2​n.

Equivalently, the universal asymptotic lower ratio is at least one. This interprets the printed 1−o(1)1-o(1)1−o(1) coefficient in the asymptotically faithful regime; Lo's cited upper bound is not restated as a new theorem.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P61
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P61

open scoped Matrix ComplexConjugate

open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)

open QAlgorithms.Papers.Independent.Dependency50.P35 (supportRank)

open QAlgorithms.Papers.Independent.Bridge50.P40 (entropyInfinity)

open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)

attribute [local instance] Classical.propDecidable

/-- PDF p.8, unnumbered classical preparation bound: the printed (1-o(1))
coefficient is interpreted in the asymptotically faithful regime epsilon_n -> 0,
not at fixed nonzero error. Lo's upper bound is background, not a new assertion.
The displayed eventual bound is the universal liminf >= 1 formulation. -/
theorem harmonic_classical_cost (epsilon : ℕ → ℝ) (hzero : ∀ n, 0 ≤ epsilon n)
    (hfaithful : Filter.Tendsto epsilon Filter.atTop (nhds 0)) :
    ∀ slack : ℝ, 0 < slack → ∃ N : ℕ, 2 ≤ N ∧ ∀ n ≥ N, ∀ (k : ℕ) (cost : ℝ),
      ClassicalPrepares (eprPairs k) (harmonicState n) (epsilon n) cost →
      (1 - slack) * logTwo n ≤ cost := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P61

end
Source
On the communication cost of entanglement transformations, arXiv:quant-ph/0204092v3, PDF p. 8, §IV, unnumbered: asymptotically tight classical preparation cost
Read-back

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

For every sequence ϵ:N→R\epsilon:\mathbb N\to\mathbb Rϵ:N→R with ϵn≥0\epsilon_n\ge0ϵn​≥0 for every nnn and ϵn→0\epsilon_n\to0ϵn​→0 as n→∞n\to\inftyn→∞, and every real slack s>0s>0s>0, there exists a natural number N≥2N\ge2N≥2 such that, for every natural number n≥Nn\ge Nn≥N, every natural number kkk (including zero), and every real cost ccc, the following implication holds. Define

∣Ek⟩=2−k/2∑j=02k−1∣j,j⟩,∣hn⟩=∑j=0n−1∣j,j⟩(j+1)∑i=1n1/i.|E_k\rangle=2^{-k/2}\sum_{j=0}^{2^k-1}|j,j\rangle,\qquad |h_n\rangle=\sum_{j=0}^{n-1} \frac{|j,j\rangle}{\sqrt{(j+1)\sum_{i=1}^{n}1/i}}.∣Ek​⟩=2−k/2j=0∑2k−1​∣j,j⟩,∣hn​⟩=j=0∑n−1​(j+1)∑i=1n​1/i​∣j,j⟩​.

Suppose an output matrix σ\sigmaσ on Cn⊗Cn\mathbb C^n\otimes\mathbb C^nCn⊗Cn can be obtained from ∣Ek⟩⟨Ek∣|E_k\rangle\langle E_k|∣Ek​⟩⟨Ek​∣ by a finite classical execution of cost ccc, and

(Re⁡tr⁡σ ∣hn⟩⟨hn∣ σ)2≥1−ϵn.\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\sigma}\,|h_n\rangle\langle h_n|\,\sqrt{\sigma}}\right)^2 \ge1-\epsilon_n.(Retrσ​∣hn​⟩⟨hn​∣σ​​)2≥1−ϵn​.

Here ∣v⟩⟨v∣|v\rangle\langle v|∣v⟩⟨v∣ has entries vivj‾v_i\overline{v_j}vi​vj​​, and square roots use continuous functional calculus. A classical execution is generated by identity and local Kraus maps of cost zero, sequential composition with addition of costs, and either party’s finite messages as follows: a message has m>0m>0m>0 outcomes and local Kraus operators Kj,ℓK_{j,\ell}Kj,ℓ​ satisfying ∑j,ℓKj,ℓ†Kj,ℓ=I\sum_{j,\ell}K_{j,\ell}^\dagger K_{j,\ell}=I∑j,ℓ​Kj,ℓ†​Kj,ℓ​=I; each outcome’s unnormalized branch undergoes a further classical execution, the final output is the sum of the branch outputs, and the assigned cost is log⁡2m+b\log_2m+blog2​m+b, where bbb is any real upper bound on every branch’s continuation cost. Local registers may have arbitrary finite dimensions and are identified with enumerated coordinate registers. Under these assumptions,

(1−s)log⁡2n≤c.(1-s)\log_2n\le c.(1−s)log2​n≤c.

Here log⁡2x=log⁡x/log⁡2\log_2x=\log x/\log2log2​x=logx/log2. No upper bound on individual ϵn\epsilon_nϵn​ is assumed, and the conclusion allows every s>0s>0s>0, including s≥1s\ge1s≥1.

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

    Confirmed by the moderator at approval.

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