Quantum Fourier-Transform Circuits

Fix any $\lambda$ with $\mathrm{\mid }\lambda \mathrm{\mid }=1$, and set $\alpha =U\psi$ and $\beta =\lambda V\psi$. By [F4], [F7] and $\mathrm{\mid }\lambda \mathrm{\mid }=1$, both vectors have norm $1$. Parseval [F6] makes their squared coordinate moduli nonnegative weights summing to $1$, so [F1] gives the output probability laws. For each $b\in B$, [F5] applied to ${\alpha }_b=({\alpha }_b-{\beta }_b)+{\beta }_b$ and then to the reversed pair gives $\mid \mathrm{\mid }{\alpha }_b\mathrm{\mid }-\mathrm{\mid }{\beta }_b\mathrm{\mid }\mid \le \mathrm{\mid }{\alpha }_b-{\beta }_b\mathrm{\mid }$. Factoring a difference of squares and applying [F2] gives $d_{\mathrm{T}\mathrm{V}}(p_U^{\psi },p_{\lambda V}^{\psi })\le \frac{1}{2}\mathrm{\parallel }\alpha -\beta {\mathrm{\parallel }}_2({\sum }_b(\mathrm{\mid }{\alpha }_b\mathrm{\mid }+\mathrm{\mid }{\beta }_b\mathrm{\mid }{)}^2{)}^{1\mathrm{/}2}$. Expanding the last squared sum and applying [F2] to the two nonnegative coordinate lists bounds its square root by $\mathrm{\parallel }\alpha {\mathrm{\parallel }}_2+\mathrm{\parallel }\beta {\mathrm{\parallel }}_2=2$, so the total variation is at most $\mathrm{\parallel }\alpha -\beta {\mathrm{\parallel }}_2$.

If ${\gamma }_b$ is the $b$-th coordinate of $V\psi$, then ${\beta }_b=\lambda {\gamma }_b$ and $\mathrm{\mid }{\beta }_b{\mathrm{\mid }}^2=\mathrm{\mid }\lambda {\mathrm{\mid }}^2\mathrm{\mid }{\gamma }_b{\mathrm{\mid }}^2=\mathrm{\mid }{\gamma }_b{\mathrm{\mid }}^2$ by modulus multiplicativity in [F5]. Hence $p_{\lambda V}^{\psi }=p_V^{\psi }$. Also $\mathrm{\parallel }\alpha -\beta {\mathrm{\parallel }}_2=\mathrm{\parallel }(U-\lambda V)\psi {\mathrm{\parallel }}_2\le \mathrm{\parallel }U-\lambda V\mathrm{\parallel }$ by [F3] and $\mathrm{\parallel }\psi {\mathrm{\parallel }}_2=1$. Combining with step 1.1 gives $d_{\mathrm{T}\mathrm{V}}(p_U^{\psi },p_V^{\psi })\le \mathrm{\parallel }U-\lambda V\mathrm{\parallel }$ for every unit scalar $\lambda$.

Taking the infimum over all $\mathrm{\mid }\lambda \mathrm{\mid }=1$ in step 2.1 gives $d_{\mathrm{T}\mathrm{V}}(p_U^{\psi },p_V^{\psi })\le d_{\mathrm{p}\mathrm{r}}(U,V)\le \epsilon$. No minimizing phase is required.

Let $x=\sqrt{2}$, so $x>0$ and $x^2=2$ by [F4]. For $k\ge 2$ put $a_k=x^{2k}\mathrm{/}(2k)!$; then $a_{k+1}\mathrm{/}{a}_k=2\mathrm{/}((2k+1)(2k+2))\le 1\mathrm{/}15<1$, so $(a_k{)}_{k\ge 2}$ decreases to zero. In the cosine series [F2], the terms for $k=0,1$ cancel because $1-x^2\mathrm{/}2=0$. Reindexing the remaining tail as an alternating series gives first two partial sums $a_2$ and $a_2-a_3$; [F3] bounds its sum below by $a_2-a_3>0$. Thus $\cos x>0$.

One has $x<2$: otherwise $x\ge 2$ and $x+2>0$ would imply $x^2-4=(x-2)(x+2)\ge 0$, contradicting $x^2=2<4$ from step 1.1. Hence $x\in (0,2)$.

By [F1], $\gamma =\pi \mathrm{/}2\in (0,2)$ and $\cos \gamma =0$. If $x\ge \gamma$, strict decrease of cosine on $[0,2]$ from [F2] would give $\cos x\le \cos \gamma =0$, contradicting step 1.1. Therefore $\sqrt{2}=x<\gamma =\pi \mathrm{/}2$.

For $n\ge 1$, bijectivity [F1] lets us index the output basis by all bit words $(y_{n-1},\dots ,y_0)$ in wire order; [F2] gives $y={\sum }_{j=0}^{n-1}{y}_j{2}^j$. Then $xy\mathrm{/}{2}^n={\sum }_j{y}_{j}x\mathrm{/}{2}^{n-j}$. In the term indexed by $y_j$, put $k=n-1-j$. The fractional part of $x\mathrm{/}{2}^{n-j}$ is ${\sum }_{i=0}^k{x}_i{2}^{-(k-i+1)}$: terms with $i>k$ are integers and the remaining powers have exactly these denominators. Thus the phase attached to output bit $y_j$ is the phase of $R_{n-1-j}$.

Consequently $e^{2\pi ixy\mathrm{/}{2}^n}={\prod }_j{e}^{2\pi i{y}_j{\sum }_{i=0}^{n-1-j}{x}_i{2}^{-(n-j-i)}}$. Summing over all bit strings $y$ factors as a tensor product of the two-term sums for the individual $y_j$; the normalization $2^{-n\mathrm{/}2}$ is the product of the $n$ factors $2^{-1\mathrm{/}2}$. By [F3], in wire order $q_{n-1},\dots ,q_0$ the factor sequence is $R_0\otimes \cdots \otimes R_{n-1}$, and [F4] identifies these coordinate factors with the corresponding kets.

In the descending-target circuit, the block on $q_j$ applies $H$ followed by $CP(2\pi \mathrm{/}{2}^{j-i+1})$ from each control $q_i$ with $i<j$. Before this block, all lower wires are still in the basis states $\mathrm{\mid }{x}_i⟩$: previous blocks target only higher wires, and [F6] leaves basis controls unchanged. By [F5], the Hadamard contributes relative phase $(-1{)}^{x_j}=e^{2\pi i{x}_j\mathrm{/}2}$; by [F6], the controlled phases multiply it by ${\prod }_{i<j}{e}^{2\pi i{x}_i\mathrm{/}{2}^{j-i+1}}$. Thus the block prepares $R_j$ without changing the lower wires or previously prepared higher factors. Induction down the finite loop gives $R_{n-1}\otimes \cdots \otimes R_0$ before reversal. By [F3], reversal gives the output of step 2.1. At $n=0$, the loop is empty, $N=1$, and both states are the empty tensor $1$.

Write the specified orthonormal bases as $f_0,\dots ,f_{a-1}$ for $S$ and $e_0,\dots ,e_{d-1}$ for $R$; $a,d\ge 1$. By [F1], $f_k\otimes e_j$ form an orthonormal basis of $S\otimes R$. Expand $v={\sum }_{k<a,j<d}{c}_{kj}{f}_k\otimes e_j$ and set $v_j={\sum }_{k<a}{c}_{kj}{f}_k$. Grouping this finite sum gives $v={\sum }_{j<d}{v}_j\otimes e_j$, while orthonormality gives $\parallel v{\parallel }^2={\sum }_{j<d}\parallel v_j{\parallel }^2$. By [F2], $(T\otimes I_R)v={\sum }_{j<d}T{v}_j\otimes e_j$. Hence [F3] gives $\parallel (T\otimes I_R)v{\parallel }^2={\sum }_{j<d}\parallel T{v}_j{\parallel }^2\le \parallel T{\parallel }^2{\sum }_{j<d}\parallel v_j{\parallel }^2=\parallel T{\parallel }^2\parallel v{\parallel }^2$, so $\parallel T\otimes I_R\parallel \le \parallel T\parallel$.

Choose a unit vector $s\in S$ attaining the maximum in [F3], and choose a unit vector $e\in R$. The product inner product gives $\parallel s\otimes e\parallel =1$, and [F2] gives $\parallel (T\otimes I_R)(s\otimes e)\parallel =\parallel Ts\parallel =\parallel T\parallel$. Thus $\parallel T\otimes I_R\parallel \ge \parallel T\parallel$, proving the first equality.

If the tensor register is zero-dimensional, both $A$ and $PA{P}^{-1}$ have operator norm $0$ by [F3], proving the conjugation equality. Otherwise [F5] shows that $P$ and $P^{-1}$ preserve norms, so each has operator norm $1$ by [F3]. Submultiplicativity [F4] gives $\parallel PA{P}^{-1}\parallel \le \parallel A\parallel$. Applying the same inequality to $A=P^{-1}(PA{P}^{-1})P$ gives the reverse inequality. Therefore $\parallel PA{P}^{-1}\parallel =\parallel A\parallel$ in every case.

Both CNOT maps are involutions: applying either twice uses $x\oplus x=0$ and returns every basis vector to itself, so their linear extensions permute the orthonormal basis [F3] and are exact unitary gates. Now for any $a,b\in \{0,1\}$, apply the three maps from right to left: $C_{12}\mathrm{\mid }a,b⟩=\mathrm{\mid }a,b\oplus a⟩$, then $C_{21}$ sends this to $\mathrm{\mid }a\oplus (b\oplus a),b\oplus a⟩=\mathrm{\mid }b,b\oplus a⟩$, and the final $C_{12}$ sends it to $\mathrm{\mid }b,(b\oplus a)\oplus b⟩=\mathrm{\mid }b,a⟩$. The last equalities use $a\oplus a=b\oplus b=0$.

This is exactly the action of $S$ in [F2] on every vector of the basis [F3]. Two linear maps agreeing on a basis agree on every vector, so $S=C_{12}{C}_{21}{C}_{12}$. The displayed product contains three CNOTs on the same two wires and uses no ancillary register.

If $n=0$, the exact algorithm has no gates, so [A1] gives the identity on the one-dimensional register; by [F1], ${\mathrm{QFT}}_1$ is also the identity. Thus the claimed basis action holds in this case. Now suppose $n\ge 1$ and fix a basis input $\mathrm{\mid }{x}_{n-1}\cdots x_0⟩$. In the descending loop, before the step targeting $q_j$, every lower wire $q_i$ with $i<j$ is still in its original basis state $\mathrm{\mid }{x}_i⟩$: earlier gates targeted only higher wires, and the lower wires occur only as controls, which the diagonal controlled-phase matrix in [F2] leaves unchanged. The local embedding action [F6] therefore leaves those control bits unchanged. The Hadamard on $q_j$ contributes relative phase $(-1{)}^{x_j}=e^{2\pi i{x}_j\mathrm{/}2}$, while the controlled phases from lower controls contribute $e^{2\pi i{\sum }_{i<j}{x}_i{2}^{-(j-i+1)}}$. Thus target $q_j$ has state $R_j$. The state before the final swaps is $R_{n-1}\otimes \cdots \otimes R_0$. The tensor order and coordinate-ket convention are [F3] and [F4]; interpreting this finite gate trace as the circuit's operator product requires [A1].

For $n\ge 1$, the final swaps reverse those ordered factors by [F3], producing $R_0\otimes \cdots \otimes R_{n-1}$; [F1] identifies this with the positive-sign Fourier output on $\mathrm{\mid }x⟩$. Together with the $n=0$ case established in step 1.1, the circuit agrees with ${\mathrm{QFT}}_{2^n}$ on every basis vector.

Both the circuit denotation and ${\mathrm{QFT}}_{2^n}$ are linear operators by [A1], so equality on the standard basis [F4] implies equality on every finite linear combination of basis vectors. Reversing the gate sequence and taking adjoints is its inverse by [F5]; the reverse list has the same number of gates, and each adjoint is still a Hadamard, controlled phase of opposite angle, or SWAP. The adjoint controlled phases have unit ideal cost by [F2], so the inverse QFT has the same ideal gate count and uses the negative-sign convention by [L1].

The loop has one Hadamard for each of the $n$ wires. Its controlled phases are indexed by pairs $(i,j)$ with $0\le i<j<n$; summing the $j$ possible lower controls for each target gives ${\sum }_{j=0}^{n-1}j=n(n-1)\mathrm{/}2$. The final reversal consists of exactly one swap for each pair $(j,n-1-j)$ with $j<\lfloor n\mathrm{/}2\rfloor$, hence $\lfloor n\mathrm{/}2\rfloor$ swaps.

By [F2], the ideal count is the displayed sum and there are no other gates or ancillas. For $n\ge 1$, the sum is at most $n+n(n-1)\mathrm{/}2+n\mathrm{/}2\le 3n^2\mathrm{/}2$, so it is $O(n^2)$; at $n=0$ all counts vanish. Replacing each counted SWAP by the exact identity [F3] gives exactly $3\lfloor n\mathrm{/}2\rfloor$ CNOTs.

For real $t$, [F7] and [F10] give $\mathrm{\mid }1-e^{it}{\mathrm{\mid }}^2=(1-\cos t{)}^2+{\sin }^{2}t=2(1-\cos t)=4{\sin }^2(t\mathrm{/}2)$. By [F8]–[F9], $\mathrm{\mid }\sin (t\mathrm{/}2)\mathrm{\mid }=\mathrm{\mid }\sin (t\mathrm{/}2)-\sin 0\mathrm{\mid }\le \mathrm{\mid }t\mathrm{\mid }\mathrm{/}2$, hence $\mathrm{\mid }1-e^{it}\mathrm{\mid }\le \mathrm{\mid }t\mathrm{\mid }$.

For an omitted gate at level $s$, set $t_s=2\pi \mathrm{/}{2}^s$ and $D_s={\mathrm{C}\mathrm{P}}_s-I$ on its two-qubit target. By [F2], $D_s$ has only one nonzero diagonal entry, $e^{i{t}_s}-1$, in the orthonormal basis [F15]. For any unit vector, Bessel's inequality [F16] bounds its $\mathrm{\mid }11⟩$ coordinate in modulus by $1$, so $\mathrm{\parallel }{D}_{s}v\mathrm{\parallel }\le \mathrm{\mid }{e}^{i{t}_s}-1\mathrm{\mid }$; equality is attained at $v=\mathrm{\mid }11⟩$. Thus $\mathrm{\parallel }{D}_s\mathrm{\parallel }=\mathrm{\mid }{e}^{i{t}_s}-1\mathrm{\mid }\le 2\pi \mathrm{/}{2}^s$ by step 1.1, and embedding it on the full register preserves this norm by [F13].

By [A1], let $G_1,\dots ,G_K$ be the embedded operators in chronological order, so the exact circuit product is $G_K\cdots G_1$ and the truncated product replaces omitted $G_r$ by ${\tilde{G}}_r=I$. The local embedding action is [F17]. By [F11], the exact product is ${\mathrm{QFT}}_{2^n}$. Their difference telescopes as ${\sum }_{r=1}^K{G}_K\cdots G_{r+1}(G_r-{\tilde{G}}_r){\tilde{G}}_{r-1}\cdots {\tilde{G}}_1$. Each $H$ is unitary by direct multiplication of its matrix in [F2]; each ${\mathrm{C}\mathrm{P}}_s$ is unitary because it is diagonal with unit-modulus entries by [F2,F7]; each SWAP is unitary by [F12], and each omitted gate is replaced by $I$. A local unitary $U$ tensored with $I$ has inverse $U^{-1}\otimes I$ by [F14], and conjugating by the unitary wire permutation preserves unitarity. Thus every outside product is unitary and has norm $1$ by [F3,F5]. For any operators $X,Y$, [F6] and the definition [F3] give $\mathrm{\parallel }X+Y\mathrm{\parallel }\le \mathrm{\parallel }X\mathrm{\parallel }+\mathrm{\parallel }Y\mathrm{\parallel }$; submultiplicativity [F4] therefore bounds the telescoping sum by the sum of the omitted-gate norms from step 2.1.

At level $s$, the pairs $0\le i<j<n$ satisfying $j-i+1=s$ have $i=0,\dots ,n-s$, so there are $n-s+1$ such gates. Summing step 2.1 over the omitted levels gives the first bound. Since $n-s+1\le n$ and ${\sum }_{s=m+1}^n{2}^{-s}\le 2^{-m}$, this is at most $2\pi n{2}^{-m}$.

If $m\ge n$, no gate is omitted by [F1], so the error is zero. Otherwise the displayed sum bound applies. For $m=\lceil {\log }_2(2\pi n\mathrm{/}\epsilon )\rceil <n$, $2^m\ge 2\pi n\mathrm{/}\epsilon$, hence $2\pi n{2}^{-m}\le \epsilon$; taking $m=\min \{n,\lceil {\log }_2(2\pi n\mathrm{/}\epsilon )\rceil \}$ selects either this case or $m=n$.

For each target $q_j$, the exact circuit has $j$ controlled phases. A retained denominator level $s$ corresponds to pairs with $j-i+1=s$, namely $i=0,\dots ,n-s$, and so has $n-s+1$ gates. The cutoff retains precisely $s=2,\dots ,\tilde{m}$. If $m\ge n$, then $\tilde{m}=n$ and every phase is retained.

There are $n$ target wires, $\lfloor n\mathrm{/}2\rfloor$ final swaps, and no other gates or ancillas by [F1]. Summing their costs by [F2] gives the formula. Since ${\sum }_{s=2}^{\tilde{m}}(n-s+1)\le n(\tilde{m}-1)$ and $\lfloor n\mathrm{/}2\rfloor \le n\mathrm{/}2$, the total is at most $n\tilde{m}+n\mathrm{/}2$, hence $O(n\tilde{m}+n)$. Under the cutoff in [F4] and $\epsilon \ge n^{-c}$, $m\le \lceil {\log }_2(2\pi n^{c+1})\rceil =O_c(\log n)$, so $\tilde{m}=O_c(\log n)$. The CNOT expansion is exact by [F3] and changes only the final reversal term; it does not compile any rotation.