Lemma 6.5 — subspace tomography
OpenNuclearTensor.Membership.Supplement.lemma_6_5computational-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationseparability
Let be an unknown -party state of local dimension . A known subspace has an explicitly supplied orthonormal product basis , with projector . For every , a quantum algorithm outputs a classical operator supported on , with
It uses at most copies and total time polynomial in . This is the subspace-tomography support for LocalSearch and Theorem 6.1.
Formalization Note The classical output is a coefficient matrix in the given basis, so an exponential ambient matrix is not written. At this represents the zero operator and requires no copies.
Differences from the source:
- encoding: finite complex Hilbert spaces and Hilbert–Schmidt geometry → row-major complex matrices on Fin (d^k), explicit pure-product hull, and an extended-nonnegative Frobenius-distance infimum; reason: these coordinates cover every finite-dimensional source instance; no density or norm restriction is added to the classical Hermitian input
- reading: algorithms with classical arithmetic and quantum copy access → finite arithmetic/spectral programs and elementary H,T,CX programs with Born-rule execution, charged fresh copies, and explicit classical outputs; reason: makes the computational model and all resource claims operational; neither global optimization nor a desired quantum subroutine is a primitive
- encoding: O and polynomial resource notation → positive integer multiplicative constants and degrees quantified before varying instance parameters; reason: preserves the indicated parameter dependencies and ties each bound to actual executed charges
- encoding: positive failure parameters and logarithmic confidence factors → all positive failure parameters, using L(x)=1+max(0,log(1/x)) in resource bounds; reason: agrees with logarithmic confidence scaling in the nontrivial range and accommodates the vacuous-success branch for x at least one
Preamble
import Definitions.Def_NuclearTensor_Membership_Supplement_Tasks set_option autoImplicit false noncomputable section
Formal statement
namespace NuclearTensor.Membership.Supplement
theorem lemma_6_5 :
∃ P : QProgram, ∀ (σ : Spectral) (A r : ℕ), 0 < A → 0 < r →
∃ B C : ℕ, 0 < B ∧ 0 < C ∧
∀ d m D : ℕ, 0 < d → 0 < m → ∀ ε δ : ℝ, 0 < ε → 0 < δ →
∀ V : ProductSubspace d m D, ∀ ω : CMat (d ^ m), IsDensity ω →
quantumAlgorithm ω σ A r P [d, m, D] ([ε, δ] ++ V.encode)
(B * (D : ℝ) ^ 2 * ε⁻¹ ^ 2 * confidence δ)
(B * (1 + m + d + D + ε⁻¹ + confidence δ) ^ C) δ
(tomographyOutput ω V ε) (returnsMatrix D) := by sorry
end NuclearTensor.Membership.Supplement
Source
Martino Bernasconi, Giulio Malavolta, STOC 2027 submission #945 (October 2026), p. 23, Lemma 6.5; supporting proof in p. 38.