Proof of Theorem 3.3 — trace distance of pure states at most their distance
ProvedSqrtQueries.pure_traceDist_leblack-box-separationp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitysquare-root-oracles
Let be unit vectors. Then
In the proof of Theorem 3.3 this is the step "this immediately implies the same bound for trace distance": the bound on the end states transfers to their trace distance.
Formalization Note is the matrix with entries , and the trace distance is half of WildeQIT.traceDist.
Differences from the source:
- reading: this immediately implies the same bound for trace distance → D(|ψ⟩⟨ψ|, |φ⟩⟨φ|) ≤ ‖ψ − φ‖ for unit vectors ψ, φ; reason: this is the general inequality the sentence applies to the two end states
Preamble
import Mathlib import Definitions.Def_WildeQIT_traceDist
Formal statement
namespace SqrtQueries
/-- **Pure-state trace distance** in the proof of Theorem 3.3 of Ma–Tang, *Square-root queries can help*, STOC 2027 submission manuscript (sha256 783868e7…c5f15a), p.18: the `L2` bound on the
end states "immediately implies the same bound for trace distance". For unit vectors `ψ`, `φ`,
`D(|ψ⟩⟨ψ|, |φ⟩⟨φ|) = ½‖|ψ⟩⟨ψ| − |φ⟩⟨φ|‖₁ ≤ ‖ψ − φ‖`.
**Formalization Note.** `|ψ⟩⟨ψ|` is `Matrix.vecMulVec ψ (star ψ)` (entries `ψ_i \overline{ψ_j}`),
the norm on vectors is the Euclidean norm, and the paper's trace distance is
`(1/2) * WildeQIT.traceDist` (the published `traceDist` has no factor `½`). -/
theorem pure_traceDist_le {n : Type} [Fintype n] [DecidableEq n] (ψ φ : EuclideanSpace ℂ n)
(hψ : ‖ψ‖ = 1) (hφ : ‖φ‖ = 1) :
(1 / 2) * WildeQIT.traceDist (Matrix.vecMulVec (WithLp.ofLp ψ) (star (WithLp.ofLp ψ)))
(Matrix.vecMulVec (WithLp.ofLp φ) (star (WithLp.ofLp φ))) ≤ ‖ψ - φ‖ := by sorry
end SqrtQueries
Source
Ma–Tang, Square-root queries can help, STOC 2027 submission (manuscript sha256 783868e7…c5f15a), proof of Theorem 3.3, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.