Theorem 5.4 — classical Hermitian separability
OpenNuclearTensor.Membership.Supplement.theorem_5_4computational-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationseparability
For every , a deterministic algorithm accepts any Hermitian operator on that is fully separable, and rejects whenever its Frobenius distance from the fully separable density states is at least :
Its runtime is , uniformly in every positive and every Hermitian input. Positivity, trace one, and an input-norm bound are not assumed. This is the classical separability companion to nuclear-ball membership.
Formalization Note The actual program runs with no local-optimization oracle. The local greatest-eigenvalue optimizer and real Hermitian coordinate conversion must therefore be implemented in finite charged arithmetic/spectral code; their correctness is not an extra hypothesis.
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
Preamble
import Definitions.Def_NuclearTensor_Membership_Supplement_Tasks set_option autoImplicit false noncomputable section
Formal statement
namespace NuclearTensor.Membership.Supplement
theorem theorem_5_4 :
∀ η : ℝ, 0 < η → ∃ P : Program,
∀ (σ : Spectral) (A r : ℕ), 0 < A → 0 < r →
∃ B C : ℕ, 0 < B ∧ 0 < C ∧
∀ d k : ℕ, 0 < d → 0 < k → ∀ M : CMat (d ^ k), M.IsHermitian →
runsWithin σ none A r [] P [d, k] ([η] ++ encodeMatrix M)
(B * (d : ℝ) ^ (C * k))
(fun s => ∃ b : Bool, outputsDecision s b ∧ sepDecision η M b) := by sorry
end NuclearTensor.Membership.Supplement
Source
Martino Bernasconi, Giulio Malavolta, STOC 2027 submission #945 (October 2026), p. 21, Theorem 5.4; supporting proof in p. 22.