A Number Theoretic Interpolation Between Quantum and Classical Complexity Classes

J. Maurice Rojas

We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with…