QuantumMaxCutEnergy.agm_sdp_certificate_solver_poly
OpenThis is the solver core of the classical numerical routine for the Max-Cut semidefinite relaxation, stated for an explicit polynomial-time function on edge lists, with the Turing-machine input/output plumbing removed.
Let be a graph on vertices with nonnegative rational weights for . Its canonical edge list lists the triples for all pairs in lexicographic order. Let be the symmetric weight matrix with for and , and let . The Max-Cut SDP of Ben-Tal–Nemirovski (4.3.15) maximizes
over real symmetric with unit diagonal.
Theorem. There is a function that sends an edge list to a pair , where is a list of rational rows and is a list of rationals. is polynomial-time computable in the runtime library's Poly sense (a Boolean-stack program with polynomial running time on the library's canonical encodings). For every weighted graph , write for the rational matrix read from the rows of and for the length- vector read from its second component, with missing entries read as . Then:
- is SDP-feasible: and for all ;
- is dual feasible: ;
- the duality gap is small:
The solver therefore outputs exact rational primal and dual certificates for the classical Max-Cut SDP to additive accuracy . This is the only algorithmic ingredient of the numerical lower-value routine in the classical estimator of Anshu–Gosset–Morenz (TQC 2020, Theorem 3). Evaluating , the sign condition , and the compilation to the campaign's Turing-machine encodings are handled separately.
The statement includes , empty edge sets and zero weights.
Formalization Note Poly is OAI.MetricKMedian.Binary.Automatic.Poly from the imported runtime definition, using its Coding encodings for natural numbers, rationals, pairs and lists. is QMCNumericRuntime.inputEdges G. Matrix rows are read with List.getD, with default .
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_ModernConvex_Relaxations_SignRelaxations import Mathlib open scoped BigOperators
theorem QuantumMaxCutEnergy.agm_sdp_certificate_solver_poly :
∃ Solve : List QMCNumericRuntime.NumericEdge → List (List ℚ) × List ℚ,
OAI.MetricKMedian.Binary.Automatic.Poly Solve ∧
∀ G : QuantumMaxCutEnergy.Input,
ModernConvex.Relaxations.IsUnitDiagPSD
(Matrix.of fun i j : Fin G.n =>
((((Solve (QMCNumericRuntime.inputEdges G)).1[i.val]?.getD [])[j.val]?.getD 0 : ℚ) : ℝ)) ∧
(Matrix.diagonal (fun i : Fin G.n =>
(((Solve (QMCNumericRuntime.inputEdges G)).2[i.val]?.getD 0 : ℚ) : ℝ)) +
(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 ∧
(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 : Fin G.n, (((Solve (QMCNumericRuntime.inputEdges G)).2[i.val]?.getD 0 : ℚ) : ℝ) -
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)
(Matrix.of fun i j : Fin G.n =>
((((Solve (QMCNumericRuntime.inputEdges G)).1[i.val]?.getD [])[j.val]?.getD 0 : ℚ) : ℝ))
≤ (∑ e, (G.weights e : ℝ)) / 10000 := by sorry