arXiv:quant-ph/9612017
On The Power of Exact Quantum Polynomial Time
Gilles Brassard, Peter Høyer
Abstract
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.