2018.02.04 22:29:52 (960264165855199234) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960257949829545985):
Read Simon's paper. 1. This isn't an oracle: it's the output of the Lecerf--Bennett conversion, a series of quantum gates. 2. The stated time counts these individual gates. 3. The whole algorithm is a "QTM", which by definition (see Section 2) is a composition of quantum gates.
2018.02.04 22:34:06 (960265228914176005) from Daniel J. Bernstein:
"In this paper, we present an expected polynomial-time algorithm for a quantum computer that distinguishes between two reasonably natural classes of polynomial-time computable function." No oracles here. Simon treats the oracle version separately and labels it explicitly.
2018.02.04 21:31:19 (960249429616922624) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960228635566157825):
This is "print s" rephrased in one useless way after another. Simon's accomplishment is much more interesting: an efficient, explicit conversion of (1) a size-T _circuit for f_ into (2) a size-O(T+poly) Hadamard/Toffoli composition that _computes s_.
2018.02.04 21:47:57 (960253616714993664) from "Paulo Barreto (@pbarreto)":
Well, of course it isn't any more of a "rephrasing" than any oracle query is (and repeating Simon's complexity as a red herring indefinitely won't make it so). Then again, I'll bet you'll keep repeating it anyway, so why bother...
2018.02.04 21:58:15 (960256208518176770) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960253616714993664):
You're confused. Simon's algorithm is a complete explicit quantum computation, without any oracles. This is exactly what makes the algorithm work on a quantum computer (unlike the algorithm you've been citing). The complexity that he states is the number of quantum gates he uses.
2018.02.04 22:05:10 (960257949829545985) from "Paulo Barreto (@pbarreto)":
Come again? No oracles? Routine Fourier-Twice in Simon's paper explicitly asks for the computation of f(), and you don't call that an oracle? And you say I am confused? (Surely you can do better than ad hominem)