For which kinds of group $G$, can we identify a square element efficiently? For a group $(G,\star)$, an element $x\in G$ is said to be square if there is $y\in G$ such that $x=y\star y$. 
My question is: For which kinds of group $G$, can we decide whether $x\in G$ is a square or not?
As for the multiplicative group $(\mathbb Z/n\mathbb Z)^*$ (where $n$ is a prime or the production of some primes), we know that this problem is equivalent to the so-called quadratic residue problem, and we have methods for dealing with this problem. More specifically, if and only if the factorization of $n$ is known, we can identify a sqaure element efficiently.
How about for other groups? If we cannot hope for a general answer, can we answer this question for certain special groups?
 A: You can decide whether a given element in a torsion-free hyperbolic group is a square. This class includes finitely generated free groups, torsion-free groups acting (nicely) on trees, and fundamental groups of closed surfaces with negative Euler characteristic.
Suppose $\Gamma=\langle a_1,\ldots,a_k\rangle$ and $a_0\in\Gamma$ is the element you're interested in. You can say $\Gamma=\langle a_0,a_1,\ldots,a_k\rangle$, so then the validity of following sentence can be decided by [Sela, §4]:
$$\exists x\ (a_0=x^2)$$
Technically this should begin with $\forall y$ to make an AE sentence, but the AE sentence 
$$\forall y\exists x\ (y=y)\wedge(a_0=x^2)$$
is equivalent. 
A: For a finite group $G$, there is a long-standing answer to this question using character theory. If $\chi$ is an irreducible complex character of $G$, then its Frobenius-Schur indicator $\nu(\chi)$ is defined by $\nu(\chi) = \frac{1}{|G|} \sum_{g \in G} \chi(g^{2}).$ It is known that $\nu(\chi) \in \{0,1,-1\},$ and that $\nu(\chi) = 0$ if $\chi$ is not real-valued,$\nu(\chi) = 1$ if $\chi$ is real-valued may be afforded by a representation over $\mathbb{R},$ while $\nu(\chi) = -1$ if $\chi$ is real-valued, but may not be afforded by any representation over $\mathbb{R}.$
It then follows from the orthogonality relations for group characters that for any $x \in G,$ the number of $g \in G$ such that $g^{2} = x$ is given by the formula $\sum_{\chi \in {\rm Irr}(G)} \nu(\chi)\chi(x)$, where ${\rm Irr}(G)$ is the set of complex irreducible characters of $G$. Note that $x$ is a square in $G$ if and only if this expression is non-zero.
A: To complete the picture, for an infinite finitely presented group, the answer can be "it is undecidable". That is, there exists a group $G$ given by a finite set of generators $X$ and a finite set of relations $R$ for which there is no algorithm to decide, given an element $g\in G$, if $g$ is a square in $G$. One example of such a group is Kharlampovich's group from MR0631441,  Kharlampovich, O. G., A finitely presented solvable group with unsolvable word problem. Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852--873 (one needs to take $p=2$ in her construction). Indeed, if an element belongs to the center of Kharlampovich's group with $p=2$, then it is a square in the group if and only if it is equal to 1, and Kharlampovich proved that this property is undecidable.  
A: A low-brow addendum to Geoff's answer: For a group of odd order, the answer is always YES.
