We published a new blog post on our explore-quantum page, describing our work on exploiting low-rank structure in Max-K-Cut problems.

The Max-K-Cut problem is a fundamental combinatorial optimization problem with applications in clustering, scheduling, and VLSI design. Our approach leverages the low-rank structure of the objective matrix to decompose the exponential search space into manageable subproblems, enabling exact solutions for low-rank instances and high-quality approximations for general graphs.

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

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