Solving the Max-3-Cut Problem with Coherent Networks
Stella L. Harrison, Helgi Kjartan Sigurdsson, Sergey Alyatkin, Julian D. Töpfer, Pavlos G. Lagoudakis · Physical Review Applied · 2022
Many computational problems are intractable through classical computing and, as Moore's law is drawing to a halt, demand for finding alternative methods in tackling these problems is growing. Here, we realize a liquid light machine for the NP-hard max-3-cut problem based on a network of synchronized exciton-polariton condensates. We overcome the binary limitation of the decision variables in Ising machines using the continuous-phase degrees of freedom of a coherent network of polariton condensates. The condensate network dynamical transients provide optically fast annealing of the $XY$ Hamiltonian. We apply the Goemans and Williamson random hyperplane technique, discretizing the $XY$ ground-state spin configuration to serve as ternary decision variables for an approximate optimal solution to the max-3-cut problem. Applications of the presented coherent network are investigated in image-segmentation tasks and in circuit design.