QuantumMaxCutEnergy.agm_classical_sdp_certificate_tm2
OpenThis is the certificate form of polynomial-time solvability for the Max-Cut semidefinite relaxation, in the numerical setting of Anshu–Gosset–Morenz.
Let be a graph on vertices with nonnegative rational edge weights for , and let be the symmetric weight matrix with for and . Write for the total weight. The Max-Cut SDP of Ben-Tal–Nemirovski (4.3.15) has objective
maximized over real symmetric with for all . A vector is dual feasible when
and its dual value is , which equals .
Theorem. There is a function from weighted graphs to nonnegative rationals, computed by a polynomial-time multi-tape Turing machine (Mathlib's Turing.TM2ComputableInPolyTime) on the campaign input encoding QuantumMaxCutEnergy.encodeRequest (graph followed by an ignored random tape) and output encoding QuantumMaxCutEnergy.encodeValue, such that for every graph there exist a rational matrix and a rational vector with:
- is feasible for the SDP: and for every ;
- is dual feasible: ;
- , that is, the output is the exact primal value of ;
- the duality gap of the pair is small:
The certificates are not part of the output; only their existence is asserted.
By weak duality, every such output satisfies , which is the numerical lower-value routine required by the classical energy-estimation algorithm of Anshu–Gosset–Morenz (TQC 2020, Theorem 3). The point of the certificate form is that both positive-semidefiniteness conditions and the gap are finite rational facts, so the analytic content (existence and characterization of the SDP value) is separated from the algorithmic content (an ellipsoid or interior-point solver with rounding to rational primal and dual points, as in Grötschel–Lovász–Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer 1988, and Alizadeh, SIAM J. Optim. 5 (1995) 13–51, using strict feasibility of and of large for Slater's condition).
The statement includes empty graphs, and zero weights; then , and give gap .
Formalization Note Rational certificates are coerced entrywise to real matrices. Positive semidefiniteness is Mathlib's Matrix.PosSemidef over , and feasibility is ModernConvex.Relaxations.IsUnitDiagPSD. The dual value is stated as rather than .
import Definitions.Def_QuantumMaxCutEnergyEstimationModel import Definitions.Def_ModernConvex_Relaxations_SignRelaxations import Mathlib open scoped BigOperators
theorem QuantumMaxCutEnergy.agm_classical_sdp_certificate_tm2 :
∃ L : QuantumMaxCutEnergy.Input → ℚ≥0,
Nonempty (Turing.TM2ComputableInPolyTime QuantumMaxCutEnergy.encodeRequest
QuantumMaxCutEnergy.encodeValue
(fun request : QuantumMaxCutEnergy.Input × List Bool => L request.1)) ∧
∀ G : QuantumMaxCutEnergy.Input,
∃ (X : Matrix (Fin G.n) (Fin G.n) ℚ) (y : Fin G.n → ℚ),
ModernConvex.Relaxations.IsUnitDiagPSD (X.map (fun q : ℚ => (q : ℝ))) ∧
(Matrix.diagonal (fun i => (y i : ℝ)) + (1 / 4 : ℝ) •
(Matrix.of fun i j : Fin G.n =>
if h : i < j then (G.weights ⟨(i, j), h⟩ : ℝ)
else if h : j < i then (G.weights ⟨(j, i), h⟩ : ℝ) else 0)).PosSemidef ∧
(L G : ℝ) = ModernConvex.Relaxations.maxcutRelaxationObjective
(Matrix.of fun i j : Fin G.n =>
if h : i < j then (G.weights ⟨(i, j), h⟩ : ℝ)
else if h : j < i then (G.weights ⟨(j, i), h⟩ : ℝ) else 0)
(X.map (fun q : ℚ => (q : ℝ))) ∧
(1 / 4 : ℝ) * (∑ i, ∑ j, (Matrix.of fun i j : Fin G.n =>
if h : i < j then (G.weights ⟨(i, j), h⟩ : ℝ)
else if h : j < i then (G.weights ⟨(j, i), h⟩ : ℝ) else 0) i j) +
∑ i, (y i : ℝ) - (L G : ℝ) ≤ (∑ e, (G.weights e : ℝ)) / 10000 := by sorry