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 21:18:24 (959883793627860994) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959881482725621760):
I start with a (quick) conventional circuit to compute f. I then feed this circuit to Simon's method, which (quickly) outputs a composition of Toffoli and Hadamard gates to (quickly) compute the period s. Your Simon replacement has a different data flow, taking s as input, right?
2018.02.03 21:24:38 (959885362645565442) from "Niklas Johansson (@Niklas_Skans)":
No, the algorithm is not defined in terms of the v's (and therefore s) , that is just part of our constructive proof that there exist an oracle relative to which Simon's algorithm runs in QSL.
2018.02.03 21:52:11 (959892295117168647) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959885362645565442):
So you're saying that, for a user to run your algorithm and find the period s (or to find whether s exists), the user needs to provide an input that exists but that you don't claim any efficient method to find (basically, an obfuscated encoding of s). Did I get this 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.