Positive semidefiniteness of intersection-transform Gram matrices
ProvedQuantumLTF.Majority.intersection_rank_one_posSemidefadversary-methodlinear-algebrasection-4
For a fixed Boolean query string , the exact-support adversary matrix with entries
is positive semidefinite. It is a nonnegative scalar multiple of the rank-one Gram matrix formed by the vector .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Majority_AdversaryModel
Formal statement
namespace QuantumLTF.Majority open QAlgorithms theorem intersection_rank_one_posSemidef : ∀ n r : ℕ, ∀ W : Fin (r+1) → ℝ, ∀ S : Qubits n, Matrix.PosSemidef (fun A B : ExactSupports n r => (2:ℝ)^(-n:ℤ) * W (intersectionIndex A S) * W (intersectionIndex B S)) := by sorry end QuantumLTF.Majority
Source
Rank-one Gram-matrix observation in the exact-support adversary construction of Krivcenko, Nguyen, de Wolf, arXiv:2609.40331v3, Section 4.2.