  We investigate the power of quantum computers when they are required to
return an answer that is guaranteed correct after a time that is upper-bounded
by a polynomial in the worst case. In an oracle setting, it is shown that such
machines can solve problems that would take exponential time on any classical
bounded-error probabilistic computer.
