Suppose that we have an objective function that involves two binary variables, i.e. $x, y \in \lbrace 0,1 \rbrace$ ($x$ represents the assignment of category A to category B and $y$ represents the assignment of Category A to category C that is different from category B) that are multiplied by each other.
Can such problems be relaxed using semidefinite programming? I know that if $x$ is multiplied by itself like in $x^T Qx$ can be relaxed but if we have a different variable like $y$: is it still possible to be relaxed?
It is not clear if you are asking about the semidefinite relaxation of binary condition in general, or semidefinite relaxation of bilinear products of binary variables.
Bilinear products you have already in the expression $x^TQx$ which you refer to so obviously yes.
Binary constraint simply means you have the quadratic constraint $x_i(1-x_i) = 0$, which you thus incorporate in your semidefinite relaxation as any other polynomial constraint.