The microblog: 2018.02.04 12:38:18

2018.02.04 12:38:18 (960115292595777536) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (960066660215422977):

Simon's algorithm is presented in Section 3.1 of Simon's paper and is completely explicit, invoking a Lecerf/Bennett subroutine to efficiently convert a time-T_f circuit for f into a time-O(T_f) quantum circuit for f. It has no oracles and no other cheats.


2018.02.04 01:19:36 (959944490835501057) from "Niklas Johansson (@Niklas_Skans)":

This is so far from Simon's problem, and outside the oracle paradigm, so we have not considered this. But for the sake of the discussion, can you prove that there exist fast circuits obeying Simon's problem without any special structure making the problem easy, you can't right?

2018.02.04 02:21:52 (959960162017710081) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959944490835501057):

Your obfuscation has deceived people regarding the performance of the (useless, trivial) algorithm that you published. Whether you can come up with a fast ad-hoc algorithm for any particular special case is irrelevant.

2018.02.04 09:19:35 (960065283397423105) from "Niklas Johansson (@Niklas_Skans)":

This is of course nonsense. Requiring anything else immediately forces us outside the black-box paradigm. We make it abundantly clear in our article, which you might consider reading in full before accusing us to deceive people, that we only consider this in the black box model.

2018.02.04 09:25:03 (960066660215422977) from "Niklas Johansson (@Niklas_Skans)", replying to "Niklas Johansson (@Niklas_Skans)" (960065283397423105):

You are of course free to think of our algorithm as useless and trivial, in a sense I actually agree. I don't find solutions stated relative to an oracle very useful at all. Raising this question, in my opinion, is the main part of the papers conclusion.