Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 11: a projected unitary has a singular value decomposition over img Π\mathrm{img}\,\PiimgΠ and img Π~\mathrm{img}\,\widetilde\PiimgΠ

Proved
QSVT19.Main.definition_11_svd_exists

by mikedeng1 · Oct 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-computingquantum-signal-processingsingular-value-transformation

Let UUU be a unitary and Π,Π~\Pi,\widetilde\PiΠ,Π orthogonal projectors on a finite-dimensional Hilbert space, and A=Π~UΠA=\widetilde\Pi U\PiA=ΠUΠ. With d=rank⁡Πd=\operatorname{rank}\Pid=rankΠ, d~=rank⁡Π~\tilde d=\operatorname{rank}\widetilde\Pid~=rankΠ and dmin⁡=min⁡(d,d~)d_{\min}=\min(d,\tilde d)dmin​=min(d,d~), there are orthonormal bases (ψi)i∈[d](\psi_i)_{i\in[d]}(ψi​)i∈[d]​ of img Π\mathrm{img}\,\PiimgΠ and (ψ~i)i∈[d~](\tilde\psi_i)_{i\in[\tilde d]}(ψ~​i​)i∈[d~]​ of img Π~\mathrm{img}\,\widetilde\PiimgΠ, and reals ς1≥⋯≥ςdmin⁡≥0\varsigma_1\ge\dots\ge\varsigma_{d_{\min}}\ge0ς1​≥⋯≥ςdmin​​≥0, such that

A=∑i=1dmin⁡ςi ∣ψ~i⟩⟨ψi∣.A=\sum_{i=1}^{d_{\min}}\varsigma_i\,|\tilde\psi_i\rangle\langle\psi_i|.A=i=1∑dmin​​ςi​∣ψ~​i​⟩⟨ψi​∣.

This is the existence claim behind Definition 11; it guarantees that statements quantified over all such decompositions (Theorem 17, Corollary 18) are not vacuous.

Preamble
import Definitions.Def_QSVT19_Main_Setting

set_option autoImplicit false

open scoped ComplexOrder
open Polynomial Matrix
Formal statement
namespace QSVT19.Main

/-- Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, Definition 11, p. 15 (existence claim): "Let H_U be a finite-dimensional Hilbert space and
let U, Π, Π̃ ∈ End(H_U) be linear operators on H_U such that U is a unitary, and Π, Π̃ are
orthogonal projectors, and let A = Π̃UΠ. Let d := rank(Π), d̃ := rank(Π̃), d_min := min(d, d̃). By
singular value decomposition we know that there exist orthonormal bases (|ψ_i⟩ : i ∈ [d]),
(|ψ̃_i⟩ : i ∈ [d̃]) of the subspaces img(Π) and img(Π̃) respectively, such that
A = ∑_{i=1}^{d_min} ς_i|ψ̃_i⟩⟨ψ_i|, (17) and for all i ∈ [d_min]: ς_i ∈ R^+_0. Moreover,
ς_i ≥ ς_j for all i ≤ j ∈ [d_min]."

**Formalization Note.** `H_U` is `ι → ℂ` for a finite type `ι`, with inner product
`star v ⬝ᵥ w`; `Π, Π̃` are `Proj, Projt`; "unitary" is `U ∈ Matrix.unitaryGroup ι ℂ` and
"orthogonal projector" is `IsStarProjection` (self-adjoint idempotent). A term of `ProjUnitarySVD U Proj Projt` is exactly such a decomposition (see its
docstring); the statement also records `d = rank Π` and `d̃ = rank Π̃`. This claim shows that the
quantification over decompositions in Theorem 17 and Corollary 18 is not vacuous. -/
theorem definition_11_svd_exists {ι : Type*} [Fintype ι] [DecidableEq ι] (U Proj Projt : Matrix ι ι ℂ) (hU : U ∈ Matrix.unitaryGroup ι ℂ) (hProj : IsStarProjection Proj) (hProjt : IsStarProjection Projt) :
    ∃ S : ProjUnitarySVD U Proj Projt, S.d = Proj.rank ∧ S.dt = Projt.rank := by sorry

end QSVT19.Main
Source
Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p. 15, Definition 11, (17)
Human review
  • Endorsed by Shuze Chen · Oct 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 18, 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