Polynomial-time elliptic-curve discrete logarithm

Let $p>3$ be prime, $E/\mathbb F_p$ be a short Weierstrass elliptic curve, $P\in E(\mathbb F_p)$ be a known point of known prime order $r$, $Q\in\langle P\rangle$ be a known point other than the point at infinity, and $0<\eta\leq1$. Set $f=\lceil\log_2p\rceil$, $t=\lceil\log_2(12r)\rceil$, and $k=\lceil\log\eta/ \log(1-r(r-1)/2^{2t+2})\rceil$. Given access to an oracle $U_{P,Q}$ satisfying $U_{P,Q}\ket{a,b,R}=\ket{a,b,R+[a]P-[b]Q}$, there exists a quantum algorithm that returns $m\in\{0,\ldots,r-1\}$ satisfying $Q=[m]P$ with probability at least $1-\eta$, using at most $2t+2f+1$ logical qubits, $k$ queries to $U_{P,Q}$, $k(2t^2+4t+6\lfloor t/2\rfloor)$ CNOT gates, $k(3t^2+25t+4f+3)$ single-qubit gates, $2t+2f+2+k\left(5t^2+248ft+721t+8f+6\lfloor t/2\rfloor+125\right)$ quantum computation time, $\max\{18t^2+70t+70,18f^2+72f+69\}+6f+4t+8$ classical bits, and $k(248ft+686t+119)+1$ classical operations.