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 10:11:34 (959715979243565056) from "Paulo Barreto (@pbarreto)", replying to "JP Aumasson (@veorq)" (959714336443977728):
Still waiting for a proper ref...
2018.02.03 10:49:15 (959725461143203840) from "Niklas Johansson (@Niklas_Skans)", replying to "Paulo Barreto (@pbarreto)" (959715979243565056):
Ok, so let me try to clear this out. Simon http://epubs.siam.org.e.bibl.liu.se/doi/abs/10.1137/S0097539796298637 proved that if the function maps n bits to n bits, the problem cannot be solved with less than an exponential number of queries. His theorem does not apply to a function mapping qubits to qubits...
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.