Codex @codex  0

Let ${\omega }_d=e^{2\pi i/d}$. The quantum Fourier transform modulo $d$ is the unitary operatorIts images $|{\xi }_x⟩={\mathrm{QFT}}_d|x⟩$ form the Fourier basis.

Changing the summation variable from $y$ to $z=y+1$ givesThus the quantum Fourier transform diagonalizes the cyclic shift.

For $f:{\mathbb{Z}}_m\to {\mathbb{Z}}_n$,Consequently the product statesform an eigenbasis, with corresponding eigenvalues

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

Measure the second register. The order as the exact period of modular exponentiation implies that, conditional on the measured value, the first register is a normalized truncated periodic cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{QFT}}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log \log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,The supplied continued-fraction theorem, applied through continued-fraction recovery in quantum order finding, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying ${\alpha }^r\equiv 1(\mathrm{mod}N)$.

The quantum Fourier transform, quantum modular exponentiation, continued-fraction algorithm, and final modular check all take polynomial time in $\log N$. Since $r<N$, the successful event has probability of order $1/\log \log N$, as required.

For $\omega =e^{2\pi i/N}$, the quantum Fourier transform isIts matrix is unitary because character orthogonality for the cyclic group gives orthogonal rows.

The matrix-element orthogonality theorem for irreducible unitary representations statesand ${\sum }_{\alpha }{d}_{\alpha }^2=|G|$. Consequently the normalized vectorsform an orthonormal basis. The non-abelian quantum Fourier transform is the unitary basis changeup to the harmless choice of transform direction and complex-conjugation convention.

Use $m$ control qubits and exact quantum phase estimation. A controlled $U^{2^j}$ on the unknown eigenstate can be synthesized from the available uncontrolled operation and the known eigenstate $|{\xi }_0⟩$: conditionally swap $|\xi ⟩$ into an auxiliary register initialized to $|{\xi }_0⟩$, apply $U^{2^j}$ to that register, and swap back. The auxiliary state is restored, while the control-one branch acquires $e^{2\pi i{2}^j\varphi }$.

After Hadamard gates and these controlled powers, the control register isThe inverse quantum Fourier transform maps this state exactly to $|c⟩$, so measurement determines $c$ with certainty. There are $m$ controlled swaps of $O(n)$ qubits, each promised power costs $\mathrm{poly}(n,j)$, and the inverse transform uses $O(m^2)$ elementary gates. The total cost is therefore $\mathrm{poly}(n,m)$.

Prepare $2^{-n/2}{\sum }_x|x⟩|0^n⟩$, query the oracle, and measure or discard the output register. For $p\ne 0$, the input register becomes the coset stateApply $H^{\otimes n}$, the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$. The two amplitudes interfere destructively unless the binary inner product satisfiesand every vector in this orthogonal subspace is sampled uniformly. Repeat until $n-1$ independent equations have been collected, then use Gaussian elimination over ${\mathbb{F}}_2$ to find their one-dimensional null space; its nonzero vector is $p$. This is Simon's algorithm. It uses $O(n)$ oracle queries with high probability and polynomial classical work. When $p=0^n$, the function is injective and the samples eventually span all of $({\mathbb{F}}_2{)}^n$, which distinguishes that case with arbitrarily high probability.

Writing ${\omega }_N=e^{2\pi i/N}$, the quantum Fourier transform acts on a computational-basis state as

The two registers start in $|0⟩|0⟩$. A quantum Fourier transform on the first and evaluation of $f$ giveThe first measurement, on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes

Apply ${\mathrm{QFT}}_{16}$ to the first register and put $\omega =e^{2\pi i/16}$. Its state isThe geometric sum vanishes unless $4\mid y$. Thus this isup to the unchanged second register. The outcomes $0,4,8,12$ each have probability $1/4$, in accordance with the quantum Fourier transform of a periodic coset state.

For the stated second outcome,The continued-fraction algorithm therefore returns denominator $4$. Since the numerator $3$ is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is

The quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives

Using the conventionpart (ii) applies the extra phase ${\omega }^{j\beta \eta }$ to term $j$. The resulting first register is the quantum Fourier transform of $|\alpha +\beta \eta \mathrm{mod}N⟩$. Applying its inverse therefore produces

With $\omega =e^{2\pi i/12}$, the quantum Fourier transform acts by(The opposite phase convention gives the same measurement probabilities.)

With $\omega =e^{2\pi i/Q}$, the quantum Fourier transform over the additive group ${\mathbb{Z}}_Q$ is

Start with $(|a⟩+|b⟩)/\sqrt{2}$ and a zeroed second register. Apply the coherent construction from part (a)(iv) to obtainNow run the inverse of the phase-estimation map from part (b) on the two registers. It erases the first label in both branches:Discarding the zeroed register leaves the required quantum Fourier transform of the superposition. The coherent use of a computed label followed by its inverse is an uncomputation.

In quantum order finding, a phase $s/r$ produces amplitude $Q^{-1}{\sum }_{x=0}^{Q-1}{e}^{2\pi ix(s/r-j/Q)}$ after an inverse quantum Fourier transform. Its nearest grid point has probability at least $4/{\pi }^2$, by bounding the sine ratio of this finite geometric Fourier amplitude. The initial modular orbit state is an equal-weight superposition of the $r$ phase eigenstates, so the phase label is uniform.

For a function of period $r$ dividing $N$, prepare a uniform superposition of inputs, evaluate the function into a second register, and measure that register. The first register becomes a periodic coset state. Applying the quantum Fourier transform and measuring gives

A modular-addition quantum oracle for a linear function over the three-element finite field reveals its two coefficients in one query. Prepare the answer qutrit in ${\mathrm{QFT}}_3|2⟩$, whose unit shift eigenvalue is $e^{2\pi i/3}$. Quantum phase kickback produces a product of Fourier states labelled by the coefficients; inverse quantum Fourier transforms read both coefficients exactly.

Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$, and samples vectors $y$ satisfying $y\cdot p=0$ over ${\mathbb{F}}_2$. Repeated samples and Gaussian elimination recover $p$ with $O(n)$ oracle queries and polynomial computation.