Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

First-order QNTK gradient-descent evolution

Proved
QAlgorithms.Papers.Independent.Intakenext100.P88.linearized_gradient_law

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

prove2quantum

The circuit acts on a nonzero finite-dimensional complex Hilbert space H=ChH=\mathbb C^hH=Ch and has the ordered form U(θ)=∏ℓ=1LWℓexp⁡(iθℓXℓ)U(\theta)=\prod_{\ell=1}^L W_\ell\exp(i\theta_\ell X_\ell)U(θ)=∏ℓ=1L​Wℓ​exp(iθℓ​Xℓ​), with fixed unitary WℓW_\ellWℓ​, Hermitian XℓX_\ellXℓ​, and real angles. Products are written in increasing index order and the rightmost factor acts first. Feature vectors ϕ(x)\phi(x)ϕ(x) have norm one. For Hermitian observables OiO_iOi​, put zx,i(θ)=⟨U(θ)ϕ(x),OiU(θ)ϕ(x)⟩∈Rz_{x,i}(\theta)=\langle U(\theta)\phi(x),O_iU(\theta)\phi(x)\rangle\in\mathbb Rzx,i​(θ)=⟨U(θ)ϕ(x),Oi​U(θ)ϕ(x)⟩∈R.

Let AAA be a finite training subset, III a finite observable family, yby_byb​ real labels, ϵb=zb−yb\epsilon_b=z_b-y_bϵb​=zb​−yb​, and η>0\eta>0η>0. Use the unaveraged loss 12∑b∈A×Iϵb2\frac12\sum_{b\in A\times I}\epsilon_b^221​∑b∈A×I​ϵb2​. For the real gradient step Δθℓ=−η∑bϵb∂ℓzb\Delta\theta_\ell=-\eta\sum_b\epsilon_b\partial_\ell z_bΔθℓ​=−η∑b​ϵb​∂ℓ​zb​, its first Taylor output increment satisfies

∑ℓ∂ℓza Δθℓ=−η∑b∈A×IKabϵb.\sum_\ell\partial_\ell z_a\,\Delta\theta_\ell=-\eta\sum_{b\in A\times I}K_{ab}\epsilon_b.ℓ∑​∂ℓ​za​Δθℓ​=−ηb∈A×I∑​Kab​ϵb​.

For complex amplitude outputs, duplicate residuals and outputs into conjugate pairs, and form the complex Gram kernel K\mathcal KK of the doubled real-parameter derivatives. The analogous real gradient of 12∑∣z−y∣2\frac12\sum|z-y|^221​∑∣z−y∣2 gives Δ(1)zμ=−(η/2)∑ν∈A×{0,1}×HKμνϵν\Delta^{(1)}\mathcal z_\mu=-(\eta/2)\sum_{\nu\in A\times\{0,1\}\times H}\mathcal K_{\mu\nu}\mathcal\epsilon_\nuΔ(1)zμ​=−(η/2)∑ν∈A×{0,1}×H​Kμν​ϵν​. The scalar formula is the singleton-data, singleton-observable case. These identities describe first Taylor increments and provide the evolution laws used in the frozen models.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P88
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P88

open scoped BigOperators ComplexConjugate Topology NNReal ComplexOrder

open MeasureTheory ProbabilityTheory Filter

/-- PDF pp.2,5,23 Eqs.(4),(25)-(28),(88)-(93), and pp.28-29 Eqs.(132)-(140).
This is the first Taylor increment induced by the real gradient of the unaveraged squared
loss. It is not equality with an exact nonlinear one-step circuit increment. Unit data and
Unit observables recover the scalar optimization law. -/
theorem linearized_gradient_law {D T I : Type*} [Fintype T] [Fintype I]
    {h L : ℕ} (M : ExpectationNetwork D I h L) (embed : T ↪ D)
    (theta : Fin L → ℝ) (y : T × I → ℝ) (eta : ℝ) (heta : 0 < eta) :
    (let e := fun b : T × I => expectationOutput M theta (trainingIndex embed b) - y b
     let dp := fun l => -eta * ∑ b, e b *
       coordinateDerivative (fun u => expectationOutput M u (trainingIndex embed b)) theta l
     ∀ a, (∑ l, coordinateDerivative (fun u => expectationOutput M u a) theta l * dp l) =
       -eta * ∑ b, expectationKernel M theta a (trainingIndex embed b) * e b) ∧
    (∀ (N : AmplitudeModel D h L) (labels : T × Fin h → ℂ),
      let e := fun b : T × Fin h => basisAmplitude N theta (embed b.1, b.2) - labels b
      let dp := fun l => -eta * (∑ b, e b *
        star (coordinateDerivative (fun u => basisAmplitude N u (embed b.1, b.2)) theta l)).re
      let de := fun b : T × Bool × Fin h =>
        if b.2.1 then star (e (b.1, b.2.2)) else e (b.1, b.2.2)
      ∀ a, (∑ l, coordinateDerivative (fun u => doubledAmplitude N u a) theta l * (dp l : ℂ)) =
        -(eta / 2 : ℝ) • (∑ b : T × Bool × Fin h,
          amplitudeKernel N theta a (embed b.1, b.2.1, b.2.2) * de b)) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P88

end
Source
Representation Learning via Quantum Neural Tangent Kernels, arXiv:2111.04225v3, PDF p. 2, Eq.(4); Eqs.(25)-(28); SM Eqs.(132)-(140)
Read-back

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

Let D,T,ID,T,ID,T,I be types with TTT and III finite, let h,Lh,Lh,L be natural numbers, and let MMM consist of h>0h>0h>0, unitary matrices Wl∈Ch×hW_l\in\mathbb C^{h\times h}Wl​∈Ch×h, Hermitian matrices Xl∈Ch×hX_l\in\mathbb C^{h\times h}Xl​∈Ch×h, unit vectors ϕx∈Ch\phi_x\in\mathbb C^hϕx​∈Ch for x∈Dx\in Dx∈D, and Hermitian observables Oi∈Ch×hO_i\in\mathbb C^{h\times h}Oi​∈Ch×h for i∈Ii\in Ii∈I. Define U(θ)=∏l=0L−1Wlexp⁡(iθlXl)U(\theta)=\prod_{l=0}^{L-1}W_l\exp(i\theta_lX_l)U(θ)=∏l=0L−1​Wl​exp(iθl​Xl​) in increasing index order, and f(x,i)(θ)=Re⁡⟨U(θ)ϕx,OiU(θ)ϕx⟩f_{(x,i)}(\theta)=\operatorname{Re}\langle U(\theta)\phi_x,O_iU(\theta)\phi_x\ranglef(x,i)​(θ)=Re⟨U(θ)ϕx​,Oi​U(θ)ϕx​⟩. Let ι:T↪D\iota:T\hookrightarrow Dι:T↪D be injective, write (t,i)^=(ι(t),i)\widehat{(t,i)}=(\iota(t),i)(t,i)​=(ι(t),i), and fix arbitrary θ∈RL\theta\in\mathbb R^Lθ∈RL, labels y:T×I→Ry:T\times I\to\mathbb Ry:T×I→R, and η>0\eta>0η>0. All coordinate derivatives below are with respect to real parameters. Define eb=fb^(θ)−ybe_b=f_{\widehat b}(\theta)-y_beb​=fb​(θ)−yb​, pl=−η∑b∈T×Ieb ∂lfb^(θ)p_l=-\eta\sum_{b\in T\times I}e_b\,\partial_lf_{\widehat b}(\theta)pl​=−η∑b∈T×I​eb​∂l​fb​(θ), and Kθ(a,c)=∑l∂lfa(θ)∂lfc(θ)K_\theta(a,c)=\sum_l\partial_lf_a(\theta)\partial_lf_c(\theta)Kθ​(a,c)=∑l​∂l​fa​(θ)∂l​fc​(θ). Then, for every a∈D×Ia\in D\times Ia∈D×I, ∑l∂lfa(θ)pl=−η∑b∈T×IKθ(a,b^)eb\sum_l\partial_lf_a(\theta)p_l=-\eta\sum_{b\in T\times I}K_\theta(a,\widehat b)e_b∑l​∂l​fa​(θ)pl​=−η∑b∈T×I​Kθ​(a,b)eb​. In addition, for every amplitude model NNN of the same dimensions—consisting of its own unitary WlNW_l^NWlN​, Hermitian XlNX_l^NXlN​, and unit vectors ϕxN\phi_x^NϕxN​—and every complex label function yN:T×{0,…,h−1}→Cy^N:T\times\{0,\ldots,h-1\}\to\mathbb CyN:T×{0,…,h−1}→C, define Bx,j(θ)=(∏lWlNexp⁡(iθlXlN)ϕxN)jB_{x,j}(\theta)=(\prod_lW_l^N\exp(i\theta_lX_l^N)\phi_x^N)_jBx,j​(θ)=(∏l​WlN​exp(iθl​XlN​)ϕxN​)j​, Ax,false,j=Bx,jA_{x,\mathrm{false},j}=B_{x,j}Ax,false,j​=Bx,j​, Ax,true,j=Bx,j‾A_{x,\mathrm{true},j}=\overline{B_{x,j}}Ax,true,j​=Bx,j​​, ϵt,j=Bι(t),j(θ)−yt,jN\epsilon_{t,j}=B_{\iota(t),j}(\theta)-y^N_{t,j}ϵt,j​=Bι(t),j​(θ)−yt,jN​, plN=−η Re⁡∑t,jϵt,j∂lBι(t),j(θ)‾p_l^N=-\eta\,\operatorname{Re}\sum_{t,j}\epsilon_{t,j}\overline{\partial_lB_{\iota(t),j}(\theta)}plN​=−ηRe∑t,j​ϵt,j​∂l​Bι(t),j​(θ)​, and dt,false,j=ϵt,jd_{t,\mathrm{false},j}=\epsilon_{t,j}dt,false,j​=ϵt,j​, dt,true,j=ϵt,j‾d_{t,\mathrm{true},j}=\overline{\epsilon_{t,j}}dt,true,j​=ϵt,j​​. With KθN(a,c)=∑l∂lAa(θ)∂lAc(θ)‾K_\theta^N(a,c)=\sum_l\partial_lA_a(\theta)\overline{\partial_lA_c(\theta)}KθN​(a,c)=∑l​∂l​Aa​(θ)∂l​Ac​(θ)​, every a∈D×{false,true}×{0,…,h−1}a\in D\times\{\mathrm{false},\mathrm{true}\}\times\{0,\ldots,h-1\}a∈D×{false,true}×{0,…,h−1} satisfies ∑l∂lAa(θ)plN=−η2∑t,σ,jKθN(a,(ι(t),σ,j))dt,σ,j\sum_l\partial_lA_a(\theta)p_l^N=-\frac{\eta}{2}\sum_{t,\sigma,j}K_\theta^N(a,(\iota(t),\sigma,j))d_{t,\sigma,j}∑l​∂l​Aa​(θ)plN​=−2η​∑t,σ,j​KθN​(a,(ι(t),σ,j))dt,σ,j​. Empty parameter and training sums are allowed; TTT and III need not be nonempty.

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