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

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

In most-significant-bit-first order, let $x=x_1\cdots x_n$ and $0.x_j\cdots x_n={\sum }_{l=j}^n{x}_l{2}^{-(l-j+1)}$. On a computational-basis state, process wire $j$ with a Hadamard gate, then controlled phase gates $R_{l-j+1}$ controlled by unprocessed wire $l$ for each $l>j$. Wire $j$ becomes $(|0⟩+e^{2\pi i0.x_j\cdots x_n}|1⟩)/\sqrt{2}$. Reversing the final wire order yields the positive-exponent quantum Fourier transform. There are $n$ Hadamard gates and $n(n-1)/2$ controlled phase gates. Physical reversal costs $\lfloor n/2\rfloor$ swap operators, each expressible as three controlled-NOT gates, themselves implemented with Hadamard gates and a Controlled-Z gate. Thus the entire construction uses $O(n^2)$ gates from the specified family.

Write the integer label in most-significant-bit-first order as $l={\sum }_j{b}_j{2}^{n-j}$. The phase factors as $e^{i\varphi l}={\prod }_j{e}^{i\varphi b_j{2}^{n-j}}$, giving the displayed product state. For dyadic Fourier phases this explains why the Fourier basis states are unentangled even though a general quantum Fourier transform can create entanglement.

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\}$.

For an unknown nonzero period, a collision $f(x)=f(y)$ reveals the period $x\oplus y$. Birthday problem sampling finds one using $O(2^{n/2})$ queries with bounded error. A matching lower bound follows by choosing the period and output labels randomly: without a collision, $q$ queries rule out at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ candidate periods. For $q=o(2^{n/2})$, almost all periods remain consistent with the transcript. The exponential separation is in query complexity, compared with Simon's algorithm's linear quantum query count.

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.

To solve Simon's problem, prepare a uniform quantum superposition, evaluate the function coherently into a second quantum register, and perform Simon Fourier sampling on the first. Each run produces a uniform binary string $z$ with $z\cdot s=0$ over the two-element field. Once the observed rows have matrix rank $n-1$, Gaussian elimination recovers $s$ as the unique nonzero element of their kernel. The random spanning of a binary vector space bounds the required number of runs.

Apply the Hadamard transform to a Simon coset state. The probability amplitude of $|z⟩$ is $2^{-(n+1)/2}(-1{)}^{x\cdot z}[1+(-1{)}^{s\cdot z}]$. Destructive quantum interference eliminates exactly those $z$ with $z\cdot s=1$. A computational-basis measurement therefore samples the kernel $s^{\perp }$ uniformly, independently of the representative $x$.

In Simon's algorithm, conditioning on a function value leaves the first quantum register in an equal coherent sum of its two preimages. This is a pure state, even though discarding the second quantum register without retaining its outcome generally leaves a mixed state. The label $x$ depends on the measured value; the period $s$ does not.

With a nonzero hidden period, Simon's algorithm samples uniformly from its $(n-1)$-dimensional orthogonal complement over the binary field. At rank $k$, a new sample raises the rank with probability $1-2^{k-(n-1)}$. Summing the geometric waiting times gives an expected $n-1+{\sum }_{j=1}^{n-1}(2^j-1{)}^{-1}<n+1$ queries. After $n-1+c$ samples, the probability of insufficient rank is less than $2^{-c}$, by a union bound over the nonzero linear functionals that could annihilate all samples.

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.

Let $L=2^t$, let $j_0$ be the nearest label to $L\varphi$, and let $m\ge 2$. The exact quantum phase estimation amplitude is $L^{-1}{\sum }_{a=0}^{L-1}{e}^{2\pi ia(\varphi -j/L)}$. The sine bound on circular distances gives probability at most $1/(4d_j^2)$, where $d_j$ is the centered distance from $j$ to $L\varphi$. At label distance $\ell$ from $j_0$, $|d_j|\ge \ell -1/2$, with at most two labels for each $\ell$. Since $(\ell -1/2{)}^{-2}\le [(\ell -1)\ell {]}^{-1}$, the tail telescopes to the displayed bound. Adding $u$ control qubits beyond $b$ desired phase bits gives circular accuracy below $2^{-b}$ with failure probability at most $[2(2^u-1){]}^{-1}$.

For register size $N=2^t$ and eigenphase $\varphi =2\pi n/N+ϵ$, the amplitude of decoded label $m$ is $N^{-1}{\sum }_{k=0}^{N-1}{e}^{ik(\varphi -2\pi m/N)}$. The finite geometric series gives $P(n)={\sin }^2(Nϵ/2)/[N^2{\sin }^2(ϵ/2)]$. If $N|ϵ|\ll 1$, this is $1-(N^2-1){ϵ}^2/12+O(N^4{ϵ}^4)$. Thus the nearest exactly representable phase is returned with probability near one, not with certainty unless the offset vanishes.

// Target: quantum-error-correction.bigb

Use CNOT gates to encode one logical qubit and $r-1$ zero ancillas into the repetition subspace spanned by $|0^r⟩,|1^r⟩$. Apply the phase gate in parallel to all $r$ physical qubits, then undo the encoding. The logical phase is multiplied by $r$ in one oracle-time layer. This copies computational-basis labels coherently rather than cloning an arbitrary quantum state. Blocks of sizes $1,2,4,\dots ,2^{n-1}$ prepare a dyadic Fourier phase state using $2^n-1$ parallel oracle applications.

For a $d$-dimensional unitary operator $V={\sum }_{j=1}^d{e}^{i{\varphi }_j}|v_j⟩⟨v_j|$, a maximally mixed state $I/d$ on its target is the equal mixture of these orthonormal eigenvectors. Therefore quantum phase estimation with register size $L$ produces label $m$ with probabilityThis follows by linearity of unitary time evolution and the Born rule on the spectral mixture. If every eigenphase has an exact $L$-grid label, that label has probability equal to its multiplicity divided by $d$. Otherwise the exact distribution has tails, and the nearest labels are guaranteed only the nearest-integer success bound for quantum phase estimation weighted by the corresponding spectral probabilities.

For a unitary operator eigenphase $\varphi$, an $n$-qubit quantum phase estimation register of size $L=2^n$ has output probability amplitudeChoose the nearest integer label $m$ to $L\varphi /(2\pi )$, with labels understood modulo $L$, and put $d=L\varphi /(2\pi )-m$, taking the representative $|d|\le 1/2$. The finite geometric series gives $|a_m|=|\sin (\pi d)|/[L|\sin (\pi d/L)|]$. For $0<|d|\le 1/2$, concavity of sine gives $|\sin (\pi d)|\ge 2|d|$, while $|\sin (\pi d/L)|\le \pi |d|/L$. Thus the probability of the nearest label is at least $4/{\pi }^2$. At $d=0$ it is exactly one. If two labels tie for nearest, each satisfies the bound.

For the phase gate $R_a=\mathrm{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\dots ,R_a$ to a uniform quantum superposition on $n$ qubits. Binary positional weights multiply the phases into $e^{2\pi iax/2^n}$ on basis vector $|x⟩$. The inverse quantum Fourier transform returns $|a⟩$ exactly, by orthogonality of roots of unity. Preparing the powers by repeated applications uses $2^n-1$ copies of $R_a$; this does not claim a number of gate calls polynomial in $n$. If $a$ is odd, its powers generate the entire set of dyadic phase gates because $a$ has a modular inverse modulo $2^n$.

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.