Computing square vs computing square-root? Time complexity
There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$.  Do this a few times for a few random primes $p$.  (You can even pick a random number $p$ without requiring it be prime.)  If there is any error in your square root, then it is likely that it will be detected by this test.  The chances of failing to detect an error is exponentially small.