We published a new blog post on our explore-quantum page, describing how three algorithmic insights make rank-1 spectral methods practical at extreme scale for Max-3-Cut.

The key ideas: (1) incremental scoring reduces the phase sweep from O(n^2) to O(n*degree), enabling million-node graphs on a single CPU; (2) 2-eigenvector complex rounding fixes a degeneracy that was losing one-third of the solution space for K=3; (3) using the rank-1 solution as a warm-start for greedy local search (the “hybrid” solver) beats greedy on 100% of the 45 instances tested, from 10K to 1M nodes across synthetic and real-world graphs.

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.