On the power of quantum computation

The journal version of Simon's algorithm, cited from the complexity table. The conference version is FOCS 1994. Under the promise that f(x) equals f(y) exactly when x plus y, bitwise, is 0 or a hidden string s, the quantum algorithm uses O(n) queries and a bounded-error classical algorithm needs exponentially many, on the order of 2 to the n/2. The result is an oracle separation. It is not itself an algorithm for factoring. This library does not yet have an algorithm page for it.