An exact quantum polynomial-time algorithm for Simon's problem
An exact quantum polynomial-time algorithm for Simon's problem
We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas …