Quantum Fourier transform (${\mathrm{QFT}}_N$)

The quantum Fourier transform maps $|k⟩$ to $N^{-1/2}{\sum }_j{e}^{2\pi ijk/N}|j⟩$.

A Fourier sample is a computational-basis measurement outcome after applying a quantum Fourier transform $F$ to a quantum state $|\psi ⟩$. Its distribution is given by the squared Fourier amplitudes. For a uniform periodic coset of spacing $r\mid N$, samples are the multiples $sN/r$ with uniform $s\in {\mathbb{Z}}_r$. Samples need not individually reveal the whole period: a greatest common divisor can remove factors from a single reduced denominator, motivating two-sample exact period recovery.

For a finite abelian group $G$ with character group $\hat{G}$, the quantum Fourier transform isup to complex conjugation according to the transform convention.

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

Let $r$ divide $N$ andThe geometric sum in the quantum Fourier transform vanishes unless $c$ is a multiple of $N/r$. Thus measurement after the transform returns the $r$ valueswith equal probabilities $1/r$.

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

For the exact sample $c=sN/r$, reducingrecovers denominator $r/\gcd (s,r)$. Thus one sample reveals the full period exactly when $s$ is coprime to $r$; otherwise it reveals only a proper divisor and the algorithm must obtain more information.

Suppose a function has least period $r\mid N$ and distinct values on distinct period cosets. Two independent Fourier samples have the form $c_j=s_{j}N/r$ with uniform $s_j\in {\mathbb{Z}}_r$. The displayed candidate is $r/\gcd (r,s_1,s_2)$, so exact recovery occurs when no prime divisor of $r$ divides both residues. The Chinese remainder theorem gives probability ${\prod }_{\ell \mid r}(1-{\ell }^{-2})\ge 1/\zeta (2)=6/{\pi }^2$, using the Euler product. Unlike a single-sample coprimality probability, this bound is uniformly greater than one half. A candidate-period test makes successful recovery heralded when such a test is available.

Suppose a function on ${\mathbb{Z}}_N$ has least period $r\mid N$ and is injective on each period. A Fourier sample $c=sN/r$ gives the candidate denominator $q=r/\gcd (s,r)$. If equality of function values can be tested efficiently, then $q$ is the full period exactly when $f(q)=f(0)$, so each successful run is certified. A sample succeeds with probability $\phi (r)/r$, and an inverse-polylogarithmic lower bound for this ratio permits amplification to constant success probability with polynomially many repetitions.

The function $f(x)=3^x\mathrm{mod}10$ on ${\mathbb{Z}}_{12}$ has period four. Measuring function value $3$ in its uniform input-output state leaves $(|1⟩+|5⟩+|9⟩)/\sqrt{3}$. The quantum Fourier transform modulo twelve then returns each of $0,3,6,9$ with probability $1/4$.

The hidden subgroup problem asks for a subgroup $H\le G$ given an oracle $f:G\to X$ that is constant on each left coset of $H$ and takes different values on different cosets. Abelian instances are solved by preparing coset states and applying a group quantum Fourier transform.

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-b}$ hides the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$ of ${\mathbb{Z}}_M^2$. Each fiber is an affine coset $\{(yb+k,b):b\in {\mathbb{Z}}_M\}$. Measuring the function register gives its normalized coset state. Applying the positive-exponent quantum Fourier transform to both input registers gives amplitudeThe finite geometric series vanishes off $c_2=-y{c}_1$ and equals $M$ on that line. Thus each allowed output pair has probability $1/M$, independently of the coset offset. If $\gcd (c_1,M)=1$, a modular inverse recovers $y=-c_2{c}_1^{-1}$.

Let $d=\gcd (c_1,M)$. A supported sample guarantees $d\mid c_2$. Dividing its linear congruence by $d$ gives an invertible coefficient modulo $M/d$ and a unique residue $y_0$ there. The $d$ compatible discrete logarithms modulo $M$ are $y_0+jM/d$ for $0\le j<d$. Only $d=1$ determines the discrete logarithm from the sample alone; $(c_1,c_2)=(0,0)$ conveys no information for $M>1$.

For a finite group $G$, subgroup $H$, and $g\in G$, the coset state is the uniform superposition

For $r\mid N$, a periodic coset state in the computational basis of ${\mathbb{Z}}_N$ isIt is the coset state of the subgroup $r{\mathbb{Z}}_N$ translated by $x_0$.

For a finite abelian group $G$, $U(h)|g⟩=|g+h⟩$ defines the regular representation on the basis labelled by $G$. The linear characters give the common eigenbasisCharacter orthogonality proves orthonormality, and changing variables by the translation in a group proves the eigenvalue formula.

Measuring the coset state $|g_0+K⟩$ in the group shift operator eigenbasis samples uniformly from the annihilator of a subgroup of a finite abelian group $K^{\perp }$. Indeed,so the character-sum cancellation lemma gives probability $|K|/|G|$ on $K^{\perp }$ and zero elsewhere. The modulus of $\chi (g_0)$ is one, so the offset has no effect on the distribution.

Simon's problem asks for the hidden string $p\in \{0,1{\}}^n$ promised by $f(x)=f(y)$ exactly when $x\oplus y\in \{0^n,p\}$. It is the hidden subgroup problem on $({\mathbb{Z}}_2{)}^n$ with hidden subgroup $\{0^n,p\}$.

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.

If the hidden string is zero, one oracle-Hadamard run samples every $y\in {\mathbb{F}}_2^n$ with probability $2^{-n}$. If the hidden string is nonzero, it samples every $y$ satisfying $y\cdot p=0$ with probability $2^{-(n-1)}$ and every other string with probability zero. Pairing $x$ with $x\oplus p$ makes the forbidden amplitudes cancel.

For a subspace $W\le {\mathbb{F}}_2^n$, its orthogonal complement is $W^{\perp }=\{y:x\cdot y=0\text{ for every }x\in W\}$, where the dot product is evaluated modulo two.

For a group action $F:G\times X\to X$ and fixed $x$, the orbit map $f_x(g)=F(g,x)$ hides the stabilizer subgroup $G_x$: $f_x(g)=f_x(h)$ exactly when $h^{-1}g\in G_x$, equivalently when $g$ and $h$ lie in the same left coset of $G_x$.

On a basis indexed by ${\mathbb{Z}}_N$, a cyclic shift operator has the form $U(a)|b⟩=|a+b\mathrm{mod}N⟩$. The quantum Fourier transform simultaneously diagonalizes all such shifts.

For the cyclic shift $S|j⟩=|j+1\mathrm{mod}N⟩$ and the conventionthe Fourier states obeyConsequently $S={\mathrm{QFT}}_{N}D{\mathrm{QFT}}_N^{-1}$, where $D|k⟩=e^{-2\pi ik/N}|k⟩$.

Given controlled powers of a unitary $U$ and an eigenstate $U|\psi ⟩=e^{2\pi i\varphi }|\psi ⟩$, quantum phase estimation outputs an approximation to $\varphi$. If the input is a superposition of eigenstates, measurement selects an eigenphase with probability equal to the squared magnitude of its coefficient.

An eigenstate with phase $\varphi$ becomes an eigenstate with phase $n\varphi$ under the tensor product of $n$ copies of the unitary operator. A promise $0\le \varphi <1/n$ prevents modulo-one aliasing. For $n=2^s$ and dyadic $\varphi =x/2^m$, exact quantum phase estimation then needs $m-s$ phase bits and $2^{m-s}-1$ queries to a supplied joint controlled oracle. This is a saving in joint-oracle calls, not in the total number of individual oracle invocations needed to build that joint operation.

Choose eigenphase representatives $0\le {\varphi }_j<1$ for a unitary operator $U$ and a positive integer $M$. Its positive-phase fractional power acts on each eigenstate by $e^{2\pi i{\varphi }_j/M}$. This branch uses arguments in $[0,2\pi )$ and can differ from the usual complex principal branch using $(-\pi ,\pi ]$. For exactly dyadic phases, exact quantum phase estimation stores each label in a coherent phase register; bitwise phase gates multiply it by the required phase, and inverse phase estimation removes the labels. Keeping the phase register unmeasured preserves arbitrary eigenstate superpositions and resets the ancilla qubits. With only controlled-$U$ and controlled-$U^{-1}$ primitives, the direct method uses $2(2^n-1)$ oracle calls for $n$ exact phase bits.

Let a Hermitian operator $A$ have dyadic eigenvalues ${\lambda }_j=c_j/2^t$ in $[0,1)$ for known $t$, with controlled access to the unitary operator $U=e^{2\pi iA}$. This interval ensures that different eigenvalues have different eigenphases; exact representability alone would not exclude phase aliasing, as $0$ and $1$ both give phase zero. Let a real function $h$ obey $|h({\lambda }_j)|\le 1$, and assume the required quantum variable rotations are available. Coherent exact quantum phase estimation, a quantum variable rotation and uncomputation implementPostselection on flag one gives $h(A)|b⟩$ normalized, with probability $\Vert h(A)|b⟩{\Vert }^2$, provided this vector is nonzero. Erasing the eigenvalue label by uncomputation is essential to preserve coherence between different eigenvectors. On this dyadic spectrum, $U^{2^t}=I$ gives $U^{-1}=U^{2^t-1}$, so reversing the phase-estimation gates is possible using forward controlled-$U$ calls. The choice $h(\lambda )=\lambda$ multiplies by $A$; a scaled reciprocal gives the different filter used in the HHL algorithm.

If $|b⟩$ lies in the kernel of $A$, then $A|b⟩=0$ has no normalized quantum state. A request to produce that normalized vector with positive probability is consequently undefined. For example, $A=\mathrm{diag}(0,1/2)$ on one qubit has distinct dyadic eigenvalues, but annihilates $|0⟩$. The corrected filtering assertion requires $A|b⟩\ne 0$; it cannot be repaired by assigning a positive success probability to this input.

For $0\le A<I$ and normalized $|b⟩={\sum }_j{\beta }_j|u_j⟩$, filtering by $h(\lambda )=\lambda$ succeeds withThe inequality follows by replacing each nonnegative ${\lambda }_j^2$ by its minimum and using ${\sum }_j|{\beta }_j{|}^2=1$. Equality holds exactly when all occupied eigenvectors belong to the minimum-eigenvalue eigenspace. If ${\lambda }_{\min }=0$, success is positive exactly for inputs outside the kernel of $A$.

If $U|\psi ⟩=e^{2\pi ij/N}|\psi ⟩$, controlled powers of $U$ applied to a uniform $N$-state control register produceThese states are the Fourier basis. Applying the inverse quantum Fourier transform and measuring returns $j$ with probability one.