2018.02.04 13:23:56 (960126777208328192) from Daniel J. Bernstein, replying to "Jan-Åke Larsson (@JanAAkeLarsson)" (960118087315001346):
"Simon's paper is completely within the oracle paradigm": Not even close. Here's the paper: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5477&rep=rep1&type=pdf Section 3.2 studies an oracle, but this is after a _real_ algorithm (Simon's algorithm!) appears in Section 3.1, using the real computational model in Section 2.
2018.02.04 03:51:16 (959982660050288642) from "Paulo Barreto (@pbarreto)":
By extra input you mean function g() as defined in Eq. 7? For it's the only difference with the original Simon oracle for f(). Equivalently, U_f can't be fully general as in Simon's case; it must have the structure in Fig. 6(b) even allowing for a black-box U'_f, is that it?
2018.02.04 12:08:02 (960107676209500160) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (959982660050288642):
6a computes s using U_f. 6b constructs U_f using U_s. 7 constructs U_s using v, which is defined in terms of s. Useless. The circularity is obfuscated through abstraction and uninstantiated generalization: if you had a different construction of U_f then you could use it instead.
2018.02.04 12:14:32 (960109310633226240) from Daniel J. Bernstein:
For comparison, Simon's paper starts from a fast conventional circuit to compute f. It explicitly and efficiently builds a composition of Hadamard and Toffoli gates that quickly computes s. As soon as we have enough Hadamard and Toffoli gates, we can actually run this algorithm.
2018.02.04 12:49:24 (960118087315001346) from "Jan-Åke Larsson (@JanAAkeLarsson)":
Simon's paper is completely within the oracle paradigm. As is ours. Don't read in things that aren't there. We simply conclude "the question arises whether oracle separation really can distinguish quantum computation from classical computation." Aimed at Simon's theorem.