Phase estimation on $|0\rangle^{\otimes 2n}|\psi_j\rangle$: output $|\phi_j\rangle|\psi_j\rangle$ with $p_k \ge 4/\pi^2$ at the optimal $k$

Let $1 < a < N$ with $\gcd(a,N)=1$, $r = \operatorname{ord}_N(a)$, $n = \lceil\log_2 N\rceil$, and $0 \le j < r$. Apply the phase estimation circuit for the modular-multiplication gate, with a $2n$-qubit first register, to $|0\rangle^{\otimes 2n}|\psi_j\rangle$. Then there is a state $|\phi_j\rangle$ of the first register such that:

1. the output is the product state $|\phi_j\rangle|\psi_j\rangle$;
2. for every $k \in \{0,\dots,2^{2n}-1\}$ with $\left|\frac{k}{2^{2n}} - \frac{j}{r}\right| \le \frac{1}{2^{2n+1}}$ (a nearest integer to $2^{2n}j/r$),

This is the guarantee of quantum phase estimation specialised to the eigenstates of $U$.

Formalization Note The article writes $p_{2^{2n}j/r}$, which is meaningful only when $2^{2n}j/r$ is an integer; it is formalized as the probability of any nearest integer $k$ to $2^{2n}j/r$, the "optimal bitstring" of the section Choosing the size of the first register.