We initiate the algorithmic study of the Quantum Max-(d)-Cut problem, a quantum generalization of the well-known Max-(d)-Cut problem. The Quantum Max-(d)-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, (d)-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the (SU(d))-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with (d \geq 3).