Triangle-free extremizers for warm-started QAOA lower bounds

Let LBκ(θ)\textbf{LB}_{\kappa}(\theta) and LBκ(θ)\textbf{LB}'_{\kappa}(\theta) be the stated inner-minimization problems, with variables r\mathbf r, s\mathbf s, r1r_1, r6r_6, ss, tt, s1,2s_{1,2}, and parameter κ\kappa. Triangle-free extremizer conjecture. For all initialization angles θ\theta, the optimal values in these minimization problems satisfy

r=s=0,\mathbf r=\mathbf s=\mathbf 0,

so that GG is triangle-free, and

r1+r6=1κ.r_1+r_6=1-\kappa.

Together, these conditions imply that the constraint

s+t+s1,2+r1+r61κs+t+s_{1,2}+r_1+r_6\leq 1-\kappa

is tight. The source presents this as an unproved conjecture based on observed optimal values; its resolution is not given.

Sources & referencesView supporting material

Primary source

Reuben Tate and Stephan Eidenbenz, “Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth p=1”, arXiv:2402.12631 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.