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 02:54:10 (959968289102417920) from Daniel J. Bernstein:
Simon's algorithm, as presented in Simon's paper (Section 3.1), is constructed explicitly and efficiently from an f circuit. You can't claim to have a replacement for Simon's algorithm if your construction needs extra inputs that you have no idea how to compute efficiently.
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 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.