2018.02.04 21:58:15 (960256208518176770) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960253616714993664):
You're confused. Simon's algorithm is a complete explicit quantum computation, without any oracles. This is exactly what makes the algorithm work on a quantum computer (unlike the algorithm you've been citing). The complexity that he states is the number of quantum gates he uses.
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 20:08:41 (960228635566157825) from "Paulo Barreto (@pbarreto)":
U_s appears there only as an example (this is even stated in the text), but *any* black box U'_f (no mention to s or pi) is enough to solve the problem classically, since it computes projections of vectors of your choice on a secret basis. This is not what U_f does, of course.
2018.02.04 21:31:19 (960249429616922624) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960228635566157825):
This is "print s" rephrased in one useless way after another. Simon's accomplishment is much more interesting: an efficient, explicit conversion of (1) a size-T _circuit for f_ into (2) a size-O(T+poly) Hadamard/Toffoli composition that _computes s_.
2018.02.04 21:47:57 (960253616714993664) from "Paulo Barreto (@pbarreto)":
Well, of course it isn't any more of a "rephrasing" than any oracle query is (and repeating Simon's complexity as a red herring indefinitely won't make it so). Then again, I'll bet you'll keep repeating it anyway, so why bother...