2018.02.04 17:39:41 (960191137792385024) from Daniel J. Bernstein, replying to "Jan-Åke Larsson (@JanAAkeLarsson)" (960163759082876928):
Do you continue to claim that "Simon's paper is completely within the oracle paradigm"? The claim is simply not true. Simon gives an explicit and efficient conversion from a time-T circuit for f into a time-O(T+poly) quantum circuit to find the period s.
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.
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 15:50:53 (960163759082876928) from "Jan-Åke Larsson (@JanAAkeLarsson)":
(It seems we indeed are talking about the same paper.) Section 3.1 of that paper only speaks about a general U_f, not specifics, and refers to Bennett's trick for making a circuit reversible. The algorithm itself (the extra Hadamard's and the inputs and outputs) is explicit.