On interpolating between quantum and classical complexity classes Chapter uri icon


  • 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.

author list (cited authors)

  • Rojas, J. M.

Book Title

  • Mathematics of Quantum Computation and Quantum Technology

publication date

  • January 2007