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 20:53:28 (959877515669106694) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959729315960229888):
Your Simon-replacement algorithm is defined in terms of the v's, which are defined in terms of the period s, right? How is the user supposed to find s in the first place? Simon's method gives a uniform constructive quantum answer to this, whereas your replacement sounds useless.
2018.02.03 21:09:13 (959881482725621760) from "Niklas Johansson (@Niklas_Skans)":
You use the subroutine in the same way as you would a quantum implementation. You get to sample from the same distributions. Uniformly and independent bit-vectors orthogonal to s.
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.