  An integer $a$ is a quadratic nonresidue for a prime $p$ if $x^2 \equiv a
\bmod p$ has no solution. Quadratic nonresidues may be found by probabilistic
methods in polynomial time. However, without assuming the Generalized Riemann
Hypothesis, no deterministic polynomial-time algorithm is known. We present a
quantum algorithm which generates a random quadratic nonresidue in
deterministic polynomial time.
