We propose and numerically study the performance of an all-optical machine for tackling combinatorial clustering, one of the unsupervised machine learning problems. A problem instance is encoded into the phase of time-multiplexed optical pulses, which are coupled repulsively through optical delay lines. To maintain uniform pulse amplitudes, we utilize a nonlinear amplifier with gain saturation, enabling our optical architecture to emulate the classical XY-spin system. This solver, called the coherent XY machine, leads to the formation of clusters in an optical phase space and allows us to efficiently identify the solution with post-processing. Additionally, we implement momentum in our solver to provide a powerful mechanism for escaping local minima and searching for the global optimum. Benchmarking our approach with a most advanced Ising-spin-based solver reveals a two-orders-of-magnitude improvement in the time-to-solution of the algorithm. Furthermore, our approach exhibits scaling advantages for larger problems, which will facilitate time- and energy-efficient data clustering.