Exact binary QFT circuit

Input: an $n$-qubit register with ordered wires $q_{n-1},\dots ,q_0$, $n\ge 0$. The input integer is encoded by $x={\sum }_{j=0}^{n-1}{x}_j{2}^j$ in the computational basis, as specified by Big-endian encoding of ordered bit strings.

Output: the following finite gate list, defining a unitary by the circuit semantics of Denotational semantics of a finite layered circuit on the ordered-register syntax of Finite circuit syntax and ordered wire labels, and using no ancillas.

1. For $j=n-1,n-2,\dots ,0$, complete the following block before proceeding to the next $j$: apply $H$ to target $q_j$; then, for $i=0,1,\dots ,j-1$ in that order, apply ${\mathrm{C}\mathrm{P}}_{j-i+1}$ to the pair $(q_i,q_j)$, with $q_i$ as control and $q_j$ as target. Here ${\mathrm{C}\mathrm{P}}_s$ is the ideal controlled phase defined in QFT ideal and finite-set gate-cost models.
2. After completing every block in the descending $j$ loop, for $j=0,1,\dots ,\lfloor n\mathrm{/}2\rfloor -1$, swap $q_j$ with $q_{n-1-j}$.

The chronological order is exactly the order listed. If $n=0$, all loops are empty and the output is the empty circuit, i.e. the identity on the one-dimensional register.