Classical 0.562 approximation of Quantum Max-Cut energy
OpenQuantumMaxCutEnergy.exists_0562_approximationapproximation-algorithmsclassical-algorithmsenergy-estimationquantum-max-cut
There exists one uniform randomized classical polynomial-time algorithm that, for every finite graph with nonnegative rational edge weights, returns a nonnegative rational estimate using its internal fair random bits . For each fixed input graph,
Here for , with the optimum over all normalized quantum states. The expectation is the uniform finite average over the algorithm's prescribed polynomial-length random tapes, separately for every input. Running time is polynomial on every run. This is an expected approximation ratio; a high-probability ratio would require an additional probability statement. Empty graphs and zero weights are included.
Preamble
import Definitions.Def_QuantumMaxCutEnergyEstimationModel
Formal statement
theorem QuantumMaxCutEnergy.exists_0562_approximation :
∃ A : QuantumMaxCutEnergy.Algorithm,
QuantumMaxCutEnergy.PolynomialTime A ∧
QuantumMaxCutEnergy.ApproximationRatio A (0.562 : ℝ) := by sorrySource
Lee22; general-graph benchmark 0.562 in https://marwahaha.github.io/quantum-maxcut-reference/problems/qmc. Lee (ISAAC 2022), Theorem 12, analyzes randomized circuit parameters. For this numerical target, the efficiently computable energy lower bound in Lemma 11, Eq. (15), supplies the classical-output route. Sources: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.48. The exact finite-bit classical energy-estimation statement is the campaign target; it is not an assertion that the cited construction has been formalized.