The cr.yp.to microblog: 2018.02.05 00:30:51

2018.02.05 00:30:51 (960294613176258561) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (960290407962746880):

Simon says the f computation is made "reversible (and hence unitary) at the cost of only a constant factor in the number of computation steps". He's talking about a computation with steps (and time), following the definitions in Section 2. An oracle call doesn't have steps.

Context

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.05 00:14:09 (960290407962746880) from "Paulo Barreto (@pbarreto)":

Modeling an oracle (which f is) with a unitary operator means it can uncompute what it has computed. No nonsense there unless you mix classical and quantum reasoning.