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 01:19:36 (959944490835501057) from "Niklas Johansson (@Niklas_Skans)":
This is so far from Simon's problem, and outside the oracle paradigm, so we have not considered this. But for the sake of the discussion, can you prove that there exist fast circuits obeying Simon's problem without any special structure making the problem easy, you can't right?
2018.02.04 02:21:52 (959960162017710081) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959944490835501057):
Your obfuscation has deceived people regarding the performance of the (useless, trivial) algorithm that you published. Whether you can come up with a fast ad-hoc algorithm for any particular special case is irrelevant.
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?