We published a new blog post on our explore-quantum page, introducing a 3-phase spectral pipeline for Max-3-Cut that outperforms simulated annealing on half of the graph families tested.

The method — eigensolve, randomized rank-2 sampling, greedy refinement — beats SA on 6 out of 12 real-world and synthetic graph families, including social networks (+1.96% on soc-Epinions1), web graphs (+1.90% on web-Google), and product networks (+0.12% on Amazon). The sample complexity appears constant in n: the same 10^6 random samples work from n=250 to n=1,400,000. We also tested rank-3 (negligible improvement over rank-2 at 7x the cost) and verified the rank-2 ceiling via partial exact enumeration.

Read the full blog post here, check out the code, and the paper on arXiv.

Joint work with Ria Stevens, Fangshuo Liao, Barbara Su, and Jianqiang Li.