2018.02.04 23:31:39 (960279714186358785) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960274472228962304):
Fourier-twice does not call an oracle. It is a QTM (as Simon says explicitly), not an oracle QTM. Its time (which Simon states explicitly) is the time for the reversible f computation created by Lecerf--Bennett (as Simon states explicitly) + linear algebra, with no oracle calls.
2018.02.04 23:33:59 (960280299098857473) from Daniel J. Bernstein:
Simon is completely explicit when he switches to the oracle version in Section 3.2 ("Relativized Hardness of our Problem"). Section 3.1 is the real algorithm (in particular for poly-time f, which he highlights), and Section 3.2 has a random oracle (which can't be poly-time).
2018.02.04 23:44:13 (960282875714260993) from Daniel J. Bernstein:
Simon says that the "computation of (x,f(x)) from x in time T_f(n) in step 2" of the real algorithm can be made "reversible (and hence unitary) at the cost of only a constant factor in the number of computation steps". If f were an oracle (it isn't!) then this would be nonsense.
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)
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 23:10:49 (960274472228962304) from "Paulo Barreto (@pbarreto)":
Strawman (the oracle is in the actual routine Fourier-twice, which is what I pointed out).