I've heard quantum computing doesn't reduce time complexity from exponential to polynomial, it merely reduces the degree of the polynomial.