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.03 23:04:08 (959910398970548224) from "Niklas Johansson (@Niklas_Skans)":
The reason as to why you only see that answer in the paper is because its not part of the problem of finding s, that's about how to generate an oracle. And again we start with the oracle and does not include analysis of its circuit (inner structure)...
2018.02.03 23:05:06 (959910645415202816) from "Niklas Johansson (@Niklas_Skans)", replying to "Niklas Johansson (@Niklas_Skans)" (959910398970548224):
... since that takes us out of the oracle paradigm and there the theorem of Simon does not apply.
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.