Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5 — with N=o(n/(ν2ξ2))N=o(n/(\nu^2\xi^2))N=o(n/(ν2ξ2)) copies, Pr⁡(∥A(x)−X0∥tr≤na/2)≤0.1+o(1)\Pr(\|\mathcal A(x)-X_0\|_{\mathrm{tr}}\le na/2)\le0.1+o(1)Pr(∥A(x)−X0​∥tr​≤na/2)≤0.1+o(1)

Proved
BosonicLearn.proposition_5

by iris · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

bosonic-gaussian-statesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-learning

Let X0∼μX_0\sim\muX0​∼μ (the prior (32)), let an adaptive single-copy scheme measure NNN copies of ρRX0\rho_{R_{X_0}}ρRX0​​​ with transcript x∼TX0x\sim\mathcal T_{X_0}x∼TX0​​, and let A\mathcal AA be a possibly randomized algorithm mapping transcripts to Herm0(n)\mathrm{Herm}_0(n)Herm0​(n). If N=o(n/(ν2ξ2))N=o(n/(\nu^2\xi^2))N=o(n/(ν2ξ2)), then

Pr⁡A, X0∼μ, x∼TX0(∥A(x)−X0∥tr≤na/2)≤0.1+o(1).\Pr_{\mathcal A,\ X_0\sim\mu,\ x\sim\mathcal T_{X_0}}\big(\|\mathcal A(x)-X_0\|_{\mathrm{tr}}\le na/2\big)\le0.1+o(1).A, X0​∼μ, x∼TX0​​Pr​(∥A(x)−X0​∥tr​≤na/2)≤0.1+o(1).

Precisely: there are ξ0∈(0,1/32)\xi_0\in(0,1/32)ξ0​∈(0,1/32) and a0>0a_0>0a0​>0 such that for all a∈(0,a0]a\in(0,a_0]a∈(0,a0​] and η>0\eta>0η>0 there are κ>0\kappa>0κ>0 and n1n_1n1​ with the probability at most 0.1+η0.1+\eta0.1+η whenever n≥n1n\ge n_1n≥n1​, ν∈[1/n,1]\nu\in[1/n,1]ν∈[1/n,1], ξ∈(0,ξ0]\xi\in(0,\xi_0]ξ∈(0,ξ0​] and Nν2ξ2≤κnN\nu^2\xi^2\le\kappa nNν2ξ2≤κn, for every scheme and every algorithm.

With Lemma 12 it turns a learner of ρRX\rho_{R_X}ρRX​​ into an estimator of XXX and gives Theorem 5.

Differences from the source:

  • reading: N = o(n/(ν²ξ²)) ⇒ Pr ≤ 0.1 + o(1) → ∀ η > 0 ∃ κ > 0 ∃ n₁ ∀ n ≥ n₁ ∀ ν ξ N with Nν²ξ² ≤ κn: Pr ≤ 0.1 + η; reason: uniform reading of both o(·), equivalent to the sequential one
  • reading: a the small constant of Proposition 1 → ∃ a₀ > 0 and the claim for every a ∈ (0, a₀]; reason: the event shrinks with a, so this is equivalent to the claim for the chosen a
  • encoding: "single-copy measurements", possibly adaptive, with an estimator → adaptive schemes of POVMs with an arbitrary measurable outcome space, round laws measurable in the earlier outcomes, and a Markov-kernel estimator to density operators; reason: the paper's model (§1.1 p. 5, §4 p. 19, §5.1 p. 30); measurability makes the transcript a random variable
Preamble
import Mathlib
import Definitions.Def_BosonicLearn_transcriptLaw
import Definitions.Def_BosonicLearn_fugacityCoeff
import Definitions.Def_BosonicLearn_fugacityFamily
import Definitions.Def_BosonicLearn_priorMu
open QAlgorithms.Papers.Independent.Claimed50.P47 (Occupation)

open MeasureTheory ProbabilityTheory
open scoped ENNReal
Formal statement
namespace BosonicLearn

/-- **Proposition 5 (Hardness of learning `X₀`).**
Chen, Anna Mele, Anna Mele, Preskill, *When are bosonic Gaussian states classical to learn?*, arXiv:2609.26705, Proposition 5, Eq. (96), p. 39: "Let {ρ_{R_{X_0}} : X_0 ∈ G_supp} be the family of passive Gaussian states as
defined before, with the prior distribution X_0 ∼ µ. Let A denote a (possibly randomized) algorithm that takes as
input the transcript of outcomes x and outputs an estimator A(x) ∈ Herm_0(n) for X_0. Given that N = o(n/(ν²ξ²)),
one must have Pr_{A, X_0∼µ, x∼T_{X_0}}(‖A(x) − X_0‖_tr ≤ na/2) ≤ 0.1 + o(1)."
Setting (§5.1): `1/n ≤ ν ≤ 1`, `ξ` small, `a` the small constant of Proposition 1; `T_{X_0}` is the transcript law of
a fixed adaptive single-copy scheme on `ρ_{R_{X_0}}`.

There are `ξ₀ ∈ (0, 1/32)` and `a₀ > 0` such that for every `a ∈ (0, a₀]` and `η > 0` there are `κ > 0` and `n₁`
with: for all `n ≥ n₁`, `ν ∈ [1/n, 1]`, `ξ ∈ (0, ξ₀]`, every `N` with `Nν²ξ² ≤ κn`, every adaptive single-copy scheme
on `N` copies (any outcome space) and every Markov kernel `A` from transcripts to `Herm₀(n)`,
`Pr_{X₀∼µ, x∼T_{X₀}, A}(‖A(x) − X₀‖_tr ≤ na/2) ≤ 0.1 + η`.

**Formalization Note.** Both `o(·)` are read uniformly (`∀η ∃κ ∃n₁`), which is equivalent to the sequential reading.
"For all `a ≤ a₀`" is equivalent to "for some `a`" since the event shrinks with `a`. -/
theorem proposition_5 :
    ∃ ξ₀ : ℝ, 0 < ξ₀ ∧ ξ₀ < 1 / 32 ∧ ∃ a₀ : ℝ, 0 < a₀ ∧ ∀ a : ℝ, 0 < a → a ≤ a₀ →
      ∀ η : ℝ, 0 < η → ∃ κ : ℝ, 0 < κ ∧ ∃ n₁ : ℕ, ∀ n : ℕ, n₁ ≤ n →
        ∀ ν : ℝ, 1 / (n : ℝ) ≤ ν → ν ≤ 1 → ∀ ξ : ℝ, 0 < ξ → ξ ≤ ξ₀ →
        ∀ N : ℕ, (N : ℝ) * ν ^ 2 * ξ ^ 2 ≤ κ * n →
        ∀ (O : Type) [MeasurableSpace O] (S : AdaptiveScheme n N O) (A : Kernel (Fin N → O) (Herm0 n)),
          IsMarkovKernel A →
          ∫⁻ X₀, ∫⁻ x, A x {Y | WHMultiplicativity.schattenNorm 1 ((Y - X₀ : Herm0 n) : Matrix (Fin n) (Fin n) ℂ) ≤ n * a / 2}
              ∂(transcriptLaw S (fugacityCoeff (fugacityFamily ν ξ X₀))) ∂(priorMu n)
            ≤ ENNReal.ofReal (1 / 10 + η) := by sorry

end BosonicLearn
Source
Chen, Anna Mele, Anna Mele, Preskill, When are bosonic Gaussian states classical to learn?, arXiv:2609.26705, Proposition 5, Eq. (96), p. 39
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 8, 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