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.03 23:51:34 (959922336114839553) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959910645415202816):
Simon's method (Section 3.1 of Simon's paper) is an explicit construction of a quantum circuit using expected time "O(n T_f(n) + G(n))" to find the n-bit period s of f; T_f is the time to compute f; G is linear-algebra time. You don't have an explicit fast construction, right?
2018.02.04 00:27:13 (959931307601137664) from "Niklas Johansson (@Niklas_Skans)":
We do have an explicit construction. T_f(n) in our case would be the circuit depth of fig. 6.b.
2018.02.04 00:44:41 (959935704536174592) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959931307601137664):
You don't have an explicit fast construction _where the input to the construction is a fast circuit for f_, correct? You need an extra input (basically s), or a massive slowdown (unless f has some special structure making it easy), right?
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?