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.03 22:19:47 (959899238187532289) from "Niklas Johansson (@Niklas_Skans)":
What? no, I think! Let's say that I give you a black-box and make Simon's function promise, and also that I've implemented it with QSL gates. Then you can run Simon's algorithm using the QSL-H and measurements. After O(n) queries you have a linear ind. set and can find s.
2018.02.03 22:28:46 (959901502444720128) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959899238187532289):
If I show you a small circuit to compute f, how long will it take you to show me a small QSL black box suitable as input to your algorithm? The only answer I see in your paper is to first compute s (presumably by Simon or a very slow non-quantum computation). Any better answer?
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.