Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unnumbered absence of narrow gorges under inverse-polynomial loss variance

Proved
QAlgorithms.Papers.Independent.Support50.P30.noNarrowGorges

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

prove2quantum

Consider a family of noiseless layered equivariant circuits, density-matrix inputs ρn\rho_nρn​, and Hermitian equivariant observables OnO_nOn​ with a uniform spectral bound ∥On∥op≤K\|O_n\|_{\mathrm{op}}\le K∥On​∥op​≤K, where K>0K>0K>0 is fixed before nnn. Let ℓn(θ)=Tr⁡(Un(θ)ρnUn(θ)†On)\ell_n(\theta)=\operatorname{Tr}(U_n(\theta)\rho_nU_n(\theta)^\dagger O_n)ℓn​(θ)=Tr(Un​(θ)ρn​Un​(θ)†On​), with parameters uniform on [0,2π]Ln[0,2\pi]^{L_n}[0,2π]Ln​. Assume an eventual inverse-polynomial lower bound: for some c>0c>0c>0, integer k≥0k\ge0k≥0, and NNN,

Var⁡θ(ℓn)≥cn−k(n≥N).\operatorname{Var}_\theta(\ell_n)\ge c n^{-k}\quad(n\ge N).Varθ​(ℓn​)≥cn−k(n≥N).

Then this loss family has no narrow gorge. A narrow gorge means the conjunction of below-mean points at inverse-polynomial separation and a tail envelope Pr⁡(∣ℓn−Eℓn∣≥d)≤C/(bnd2)\Pr(|\ell_n-\mathbb E\ell_n|\ge d)\le C/(b^n d^2)Pr(∣ℓn​−Eℓn​∣≥d)≤C/(bnd2) for fixed C>0C>0C>0, b>1b>1b>1, all sufficiently large nnn, and every d>0d>0d>0. The conclusion retains the explicit loss-variance premise of Eq. (96); it does not assert the incorrect probability-tends-to-one estimate of Eq. (100).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30
Formal statement
noncomputable section

open MeasureTheory

open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P30

attribute [local instance] LieRing.ofAssociativeRing

/-- PDF pp.7,33-34: qualitative no-gorge result with the loss-variance
premise (96). The incorrect anti-concentration estimate (100) is deferred. -/
theorem noNarrowGorges (K : ℝ) (hK : 0 < K) (L : ℕ → ℕ)
    (H : (n : ℕ) → Fin (L n) → QnnOperator n) (hH : ∀ n j, (H n j).IsHermitian)
    (hHeq : ∀ n j, PermutationEquivariant (H n j))
    (rho : (n : ℕ) → QnnDensity n) (O : (n : ℕ) → QnnOperator n)
    (hO : ∀ n, (O n).IsHermitian) (hOeq : ∀ n, PermutationEquivariant (O n))
    (hbound : ∀ n, specNorm (O n) ≤ K)
    (hvariance : InversePolynomialLower
      (fun n => variance (uniformParameters (L n)) (fun t => qnnLoss (circuit (H n) t) (rho n).val (O n)))) :
    ¬ HasNarrowGorge L (fun n t => qnnLoss (circuit (H n) t) (rho n).val (O n)) := by sorry

end QAlgorithms.Papers.Independent.Support50.P30

end
Source
Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks, arXiv:2210.09974v3, PDF p. 34, Unnumbered absence of narrow gorges under inverse-polynomial loss variance
Read-back

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

Let K>0K>0K>0 be a real number, let L:N→NL:\mathbb N\to\mathbb NL:N→N be arbitrary, and, for every natural number nnn and every j<L(n)j<L(n)j<L(n), let Hn,jH_{n,j}Hn,j​ be a Hermitian complex matrix indexed by length-nnn Boolean strings that commutes with every permutation of the qubits. Let ρn\rho_nρn​ be any positive semidefinite trace-one matrix on that space, and let OnO_nOn​ be Hermitian, commute with every qubit permutation, and satisfy ∥On∥op≤K\|O_n\|_{\mathrm{op}}\le K∥On​∥op​≤K for every nnn. Here the permutation corresponding to ppp sends a basis string xxx to x∘p−1x\circ p^{-1}x∘p−1. Define

Un(t)=e−itL(n)−1Hn,L(n)−1⋯e−it0Hn,0,Fn(t)=Re⁡tr⁡(Un(t)ρnUn(t)†On),U_n(t)=e^{-it_{L(n)-1}H_{n,L(n)-1}}\cdots e^{-it_0H_{n,0}}, \qquad F_n(t)=\operatorname{Re}\operatorname{tr}(U_n(t)\rho_nU_n(t)^\dagger O_n),Un​(t)=e−itL(n)−1​Hn,L(n)−1​⋯e−it0​Hn,0​,Fn​(t)=Retr(Un​(t)ρn​Un​(t)†On​),

using the identity for an empty product, and let μn\mu_nμn​ be the product of L(n)L(n)L(n) normalized Lebesgue measures on [0,2π][0,2\pi][0,2π]. Suppose there exist a real c0>0c_0>0c0​>0 and natural numbers k0,N0k_0,N_0k0​,N0​ such that, for every n≥N0n\ge N_0n≥N0​,

c0nk0≤∫Fn(t)2 dμn(t)−(∫Fn(t) dμn(t))2.\frac{c_0}{n^{k_0}} \le \int F_n(t)^2\,d\mu_n(t) -\left(\int F_n(t)\,d\mu_n(t)\right)^2.nk0​c0​​≤∫Fn​(t)2dμn​(t)−(∫Fn​(t)dμn​(t))2.

Then the following two properties cannot both hold: there exist a function g:N→Rg:\mathbb N\to\mathbb Rg:N→R, a real c1>0c_1>0c1​>0, and natural numbers k1,N1,N2k_1,N_1,N_2k1​,N1​,N2​ such that c1/nk1≤g(n)c_1/n^{k_1}\le g(n)c1​/nk1​≤g(n) for all n≥N1n\ge N_1n≥N1​ and, for every n≥N2n\ge N_2n≥N2​, some θ∈RL(n)\theta\in\mathbb R^{L(n)}θ∈RL(n) satisfies Fn(θ)≤∫Fn dμn−g(n)F_n(\theta)\le\int F_n\,d\mu_n-g(n)Fn​(θ)≤∫Fn​dμn​−g(n); and there exist real C>0C>0C>0, b>1b>1b>1, and a natural number N3N_3N3​ such that, for all n≥N3n\ge N_3n≥N3​ and all real d>0d>0d>0,

μn{θ:d≤∣Fn(θ)−∫Fn dμn∣}≤Cbnd2.\mu_n\left\{\theta: d\le\left|F_n(\theta)-\int F_n\,d\mu_n\right|\right\} \le\frac{C}{b^n d^2}.μn​{θ:d≤​Fn​(θ)−∫Fn​dμn​​}≤bnd2C​.

The parameter vector witnessing the first property may lie anywhere in RL(n)\mathbb R^{L(n)}RL(n). All matrix hypotheses range over every nnn, including 000; L(n)L(n)L(n) is unrestricted and may be zero, and the inverse-polynomial inequalities use 00=10^0=100=1 and division by zero equal to zero.

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