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 10:54:08 (959726689180966912) from "Niklas Johansson (@Niklas_Skans)", replying to "Niklas Johansson (@Niklas_Skans)" (959725461143203840):
Obviously, otherwise there would be no fast quantum algorithm for the problem. This clearly shows that qubits are richer systems than bits and that we can retrieve more information from the quantum oracle. Thus, a one-to-one comparison between qubits with bits is not fair.
2018.02.03 11:04:34 (959729315960229888) from "Niklas Johansson (@Niklas_Skans)", replying to "Niklas Johansson (@Niklas_Skans)" (959726689180966912):
We therefore built a logical framework that simulates the behavior of qubits (we called this QSL), for which Simon's theorem also do not apply. Simon's algorithm can run in this framework which further can be simulated with constant overhead by a classical Turing machine.
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.