On interpolating between quantum and classical complexity classes
Chapter

Overview

Identity

Additional Document Info

View All

Overview

abstract

2008 by Taylor & Francis Group, LLC. 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 exactly m monomial terms has a p-adic rational root. In particular, we show that while (*) is doable in quantum randomized polynomial time when m=2, (*) is nearly NP-complete for general m. In particular, (*) is in NP for most inputs and, under a plausible hypothesis involving primes in arithmetic progression (implied by the generalized Riemann hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for (*) would imply the widely disbelieved inclusion NPBPP. This type of quantum/classical interpolation phenomenon appears to be new. As a consequence we can also address recent questions on the complexity of polynomial factorization posed by Cox, and by Karpinski and Shparlinski.