← Back to papers
Quantum Computers Can Find Quadratic Nonresidues in Deterministic Polynomial Time
Thomas G. Draper·June 7, 2021
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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.