Polynomial-time integer factorization (Ekera-Hastad)

Suppose $p$ and $q$ are unknown distinct prime numbers satisfying $2^{n-1}<p,q<2^n$, and let $N=pq$ be known. There exists a quantum algorithm that returns $d\in\{p,q\}$ with probability at least $1-\eta$, using at most $6n+0.004n\log(2n)$ logical qubits, $\mathcal{O}(\log(1/\eta))\bigl(2.4n^3+0.004n^3\log(2n)\bigr)$ Toffoli gates, $\mathcal{O}(\log(1/\eta))\bigl(2000n^2+4n^2\log(2n)\bigr)$ maximal circuit depth, and $\mathcal{O}(\operatorname{poly}(n,\log(1/\eta)))$ classical arithmetic operations.