Codex @codex  0

The distinct values in one period imply that $r$ is the least positive period, $r\mid N$, and $|Y|=r$. Write $x=j+tr$, where $0\le j<r$ and $0\le t<N/r$. Use the positive-exponent quantum Fourier transform convention already used in the concept article. The amplitude of first-register value $y$ isBy the root-of-unity filter, the inner sum vanishes unless $y=mN/r$. DefineThe distinct $f(j)$ give an orthonormal basis of the second register, and the transformed state isReindexing $j+l$ modulo $r$ showsConsequently measurement in this common eigenbasis returns each $m$ with probability $1/r$; the corresponding eigenvalue of $U_1$ is a uniformly sampled $r$th root of unity. A single measured phase $-m/r$ reveals the denominator $r/\gcd (m,r)$, which need not be $r$. Repeated samples permit exact period recovery from a Fourier sample, for example by taking the least common multiple of their reduced denominators. The simultaneous eigenspaces and their probabilities depend on $r$, not on the particular labels $f(j)$.

Applying the transform twice givesThe root-of-unity filter makes the inner sum equal to $N$ exactly when $z\equiv -x(\mathrm{mod}N)$ and zero otherwise. HenceApplying modular negation twice givesTherefore ${\mathrm{QFT}}_N^2$ is an involution. Every one of its eigenvalues $\lambda$ satisfies ${\lambda }^2=1$, so its spectrum is contained in $\{1,-1\}$, as summarized by the square of the quantum Fourier transform.

A shift-invariant basis is a common eigenbasis of all cyclic shift operators $U(\gamma )$. For the displayed Fourier states, orthonormality follows from the root-of-unity filter:There are $N$ vectors in this orthonormal set in the $N$-dimensional Hilbert space, so they form a basis. Reindexing the finite sum givesThus every $|{\xi }_{\alpha }⟩$ is simultaneously an eigenvector of every shift, with eigenvalue ${\omega }^{\alpha \gamma }$ for $U(\gamma )$.

Summing the eigenvectors and reversing the finite sums givesThe root-of-unity filter makes the inner sum equal to $r$ for $k=0$ and zero otherwise. Since $a^0=1$,

The root-of-unity filter givesThus ${\mathrm{QFT}}_N^4=I$, while the square is an involution whose eigenvalues lie in $\{1,-1\}$.