Quantum Fourier Transform

The quantum Fourier transform on an $n$-qubit register is the unitary discrete Fourier transform of the register’s amplitudes over the cyclic group $\mathbb Z_{2^n}$. Its short circuit is useful because it turns carefully encoded phase structure into interference, not because it prints a classical table of Fourier coefficients. We will derive its Hadamard–controlled-phase circuit, explain the final bit-reversal swaps, and estimate the error from omitting small rotations.

Here QFT means quantum Fourier transform. The full circuit derivation concerns $N=2^n$ and the cyclic group $\mathbb Z_{2^n}$; other finite groups require different encodings and constructions.

Helpful background. Controlled operations explains coherent branch phases; single-qubit gates gives the Hadamard and phase matrices.

Fourier transformation of quantum amplitudes

Fix an input Hilbert space with computational basis

$$\{ \lvert x\rangle : x=0,\ldots,N-1 \}, \qquad N=2^n.$$

Using the positive exponential convention, the transform acts on

$$|\psi\rangle=\sum_{x=0}^{N-1}a_x|x\rangle.$$

By linearity,

$$F_N\lvert\psi\rangle = \sum_{y=0}^{N-1} \left( \frac{1}{\sqrt N} \sum_{x=0}^{N-1} a_x e^{2\pi ixy/N} \right) \lvert y\rangle.$$

Those transformed amplitudes are not a freely readable array. One measurement returns one outcome sampled from their squared magnitudes. Recovering phase information or many coefficients requires a separate interference, estimation, or tomography protocol with its own access and repetition costs.

Integers, Endianness, and Fourier Sign

Use tensor order

$$Q = q_{n-1}\otimes\cdots\otimes q_0$$

with $q_{n-1}$ displayed on the left and $q_0$ on the right. The same convention fixes the integer map:

$$x = \sum_{j=0}^{n-1} 2^j x_j, \qquad \lvert x\rangle = \lvert x_{n-1}\cdots x_0\rangle.$$

Thus $q_{n-1}$ is the most-significant wire and $q_0$ the least-significant wire. This convention is not “big-endian” or “little-endian” in isolation: the ket order, wire order, memory order, and integer interpretation must be stated together.

Define

$$\omega_N = e^{2\pi i/N}.$$

This page uses the positive-sign forward transform

$$\langle y\rvert F_N\lvert x\rangle = \frac{1}{\sqrt N} \omega_N^{xy},$$

so rows are indexed by output $y$ and columns by input $x$:

$$F_N\lvert x\rangle = \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \omega_N^{xy}\lvert y\rangle.$$

The inverse has the negative exponent,

$$F_N^\dagger\lvert y\rangle = \frac{1}{\sqrt N} \sum_{x=0}^{N-1} \omega_N^{-xy}\lvert x\rangle.$$

Some mathematics and software references assign the negative sign to the forward transform. Neither choice changes the content, but silently mixing them turns an intended inverse into a modular-negation operation. Fourier Transform Conventions compares the sign and normalization choices used in other settings.

The QFT as a Finite Unitary

For two computational-basis columns,

$$\begin{aligned} \langle x'\rvert F_N^\dagger F_N\lvert x\rangle &= \frac{1}{N} \sum_{y=0}^{N-1} \omega_N^{(x-x')y}. \end{aligned}$$

If $x=x'$, every summand is one. Otherwise the ratio $r=\omega_N^{x-x'}$ obeys $r^N=1$ but $r\neq1$, so the finite geometric sum is

$$\sum_{y=0}^{N-1}r^y = \frac{1-r^N}{1-r} = 0.$$

Therefore

$$\frac{1}{N} \sum_{y=0}^{N-1} \omega_N^{(x'-x)y} = \delta_{x,x'}, \qquad F_N^\dagger F_N = I.$$

Applying the transform twice gives another useful convention check:

$$\begin{aligned} F_N^2\lvert x\rangle &= \frac{1}{N} \sum_{z=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{y(x+z)} \lvert z\rangle \\ &= \lvert -x\bmod N\rangle. \end{aligned}$$

Consequently,

$$F_N^4 = I.$$

These identities check normalization and the modular-negation action, but they do not distinguish the positive- and negative-exponent transforms: both obey them. To test the sign, compare a complex Fourier column or decode a known phase-gradient state, as in the exercises. Wire permutations require a separate check.

The cyclic transform is also a change between the group-element basis of $\mathbb Z_N$ and its character basis. Direct products of finite cyclic groups motivate finite Abelian extensions, but their register layouts and algorithms must be specified separately. General representation theory and non-Abelian Fourier transforms are not silently covered by the power-of-two circuit derived here.

Binary-Fraction Factorization

Write the output integer as

$$y = \sum_{k=0}^{n-1} 2^k y_k.$$

Then the Fourier phase factorizes:

$$\omega_{2^n}^{xy} = \prod_{k=0}^{n-1} \exp\left( \frac{2\pi i x y_k}{2^{n-k}} \right).$$

Only the fractional part of $x/2^{n-k}$ matters. Define

$$0.x_jx_{j-1}\cdots x_0 := \sum_{r=0}^{j} \frac{x_r}{2^{j-r+1}}.$$

For example,

$$0.x_2x_1x_0 = \frac{x_2}{2} + \frac{x_1}{4} + \frac{x_0}{8}.$$

Substituting the binary expansion of $y$ into the Fourier sum and distributing the independent sums over $y_k\in\{0,1\}$ gives

$$F_{2^n}\lvert x\rangle = \bigotimes_{j=0}^{n-1} \frac{ \lvert0\rangle_{q_{n-1-j}} + e^{2\pi i\,0.x_jx_{j-1}\cdots x_0} \lvert1\rangle_{q_{n-1-j}} }{\sqrt2}.$$

The first written factor belongs to $q_{n-1}$ and depends only on $x_0$; the last belongs to $q_0$ and depends on all input bits. This reversed dependency pattern is why the natural radix-two gate sequence produces a bit-reversed wire order before its final swaps.

For a general superposition the QFT need not be a product state. The factorization above is a column formula for a basis input, used to derive the circuit; linearity then determines the action on arbitrary inputs.

Exact Hadamard–Controlled-Phase Circuit

The phase gates used here are not the site’s Bloch-sphere rotations $R_k(\theta)$. Define instead

$$P_\ell := \operatorname{diag} \left( 1, e^{2\pi i/2^\ell} \right),$$

and

$$CP_\ell := \operatorname{diag} \left( 1, 1, 1, e^{2\pi i/2^\ell} \right).$$

The controlled-phase matrix is symmetric under exchanging its two wires. Naming a control and target is nevertheless useful when following how each input bit contributes to a binary fraction.

Use left-to-right time order in the following construction. For each target wire $q_r$, starting at $r=n-1$ and descending to $r=0$:

1. apply $H$ to $q_r$;
2. for $k=r-1,r-2,\ldots,0$, apply $CP_{r-k+1}$ with control $q_k$ and target $q_r$.

The three-qubit circuit reads left to right, with $q_2$ the most-significant wire. Here $P_2=\operatorname{diag}(1,i)$ and $P_3=\operatorname{diag}(1,e^{i\pi/4})$. The final SWAP restores the mathematical output order; omitting it gives $B_3F_8$.

Finally swap

$$q_r \longleftrightarrow q_{n-1-r}, \qquad 0\leq r<\left\lfloor\frac n2\right\rfloor.$$

For a basis input, $H$ supplies the leading half-turn and the controlled phases supply the remaining binary-fraction digits. Before the swaps, the phase $0.x_rx_{r-1}\cdots x_0$ resides on $q_r$. After the swaps, it resides on the mathematical output wire required by the product formula.

Let $U_{\mathrm{core}}$ denote the no-swap circuit and define bit reversal by

$$B_n \lvert y_{n-1}\cdots y_0\rangle = \lvert y_0\cdots y_{n-1}\rangle.$$

Then

$$U_{\mathrm{core}} = B_nF_N, \qquad F_N = B_nU_{\mathrm{core}},$$

because $B_n^{-1}=B_n$.

The exact logical counts in the alphabet $\{H,CP_\ell,\mathrm{SWAP}\}$ are

$$N_H = n, \qquad N_{CP} = \sum_{r=1}^{n-1}r = \frac{n(n-1)}{2},$$

and

$$N_{\mathrm{SWAP}} = \left\lfloor\frac n2\right\rfloor.$$

These are counts, not a minimum depth or a native-hardware cost. Universal Gate Sets explains why an abstract continuous phase alphabet and a finite fault-tolerant alphabet are different resource models.

Bit reversal and the inverse circuit

Omitting $B_n$ changes the coherent unitary from $F_N$ to $B_nF_N$. If the register is measured immediately in the computational basis, software may reverse the recorded bits. If a later coherent operation consumes the register, that consumer must be rewritten to absorb $B_n$ or the swaps must be performed. Classical relabeling cannot act retroactively on a coherent state.

The inverse circuit follows from

$$F_N^\dagger = U_{\mathrm{core}}^\dagger B_n.$$

Thus it reverses the exact forward gate order, conjugates every controlled phase, and retains the declared swap convention. A positive-phase $CP_\ell$ becomes

$$CP_\ell^\dagger = \operatorname{diag} \left( 1, 1, 1, e^{-2\pi i/2^\ell} \right).$$

For a basis input, both the exact circuit and its truncated versions below have uniform computational-basis probabilities. Those probabilities can agree even when the relative phases are wrong. A useful test compares complex amplitudes with the analytic matrix, checks the no-swap result against $B_nF_N$, and recombines the result with the intended inverse. Unitarity by itself checks only that a circuit is reversible, not that it is the desired Fourier transform.

Approximate QFT and Error Budgets

A truncated or approximate quantum Fourier transform (AQFT) drops selected small-angle controlled phases under an explicit error budget. It is a different ideal unitary, not a noise model.

Choose an integer cutoff

$$1 \leq m \leq n$$

and retain only $CP_\ell$ with

$$2 \leq \ell \leq m.$$

This rule keeps all Hadamards and the same declared swaps. It retains

$$\begin{aligned} N_{CP}^{(m)} &= \sum_{\ell=2}^{m} (n-\ell+1) \\ &= \frac{(m-1)(2n-m)}{2}, \end{aligned}$$

and omits

$$\begin{aligned} N_{\mathrm{omit}} &= \sum_{\ell=m+1}^{n} (n-\ell+1) \\ &= \frac{(n-m)(n-m+1)}{2}. \end{aligned}$$

For an omitted controlled phase with angle

$$\theta_\ell = \frac{2\pi}{2^\ell},$$

the unitary difference from the identity has operator norm

$$\left\| CP_\ell-I \right\|_{\mathrm{op}} = \left| e^{i\theta_\ell}-1 \right| = 2\sin\left( \frac{\pi}{2^\ell} \right).$$

Insert one omitted gate at a time between otherwise unitary prefixes and suffixes. Unitary invariance of the operator norm and the triangle inequality give the phase-sensitive telescoping bound

$$\left\| F_N-\widetilde F_{n,m} \right\|_{\mathrm{op}} \leq \sum_{\ell=m+1}^{n} (n-\ell+1) 2\sin\left( \frac{\pi}{2^\ell} \right),$$

provided exact and approximate circuits use identical swaps.

This is a worst-case operator-norm bound with the matrix phase fixed. It is not the fidelity of one selected input, a measured distribution distance, or an algorithm’s success probability. Physical noise and the approximation of retained rotations by a finite gate set are additional errors.

The simpler inequality $\sin x\leq x$ gives

$$\|F_N-\widetilde F_{n,m}\|_{\rm op} \leq 2\pi n\sum_{\ell=m+1}^{\infty}2^{-\ell} =\frac{2\pi n}{2^m}.$$

For $0<\epsilon<1$, choosing $m=\min\{n,\lceil\log_2(2\pi n/\epsilon)\rceil\}$ therefore suffices: if the minimum selects $n$, no phase is omitted. Otherwise the retained controlled-phase count is $O(n\log(n/\epsilon))$. This is a sufficient cutoff, not necessarily the best one for a particular input or algorithm.

What the short circuit does and does not provide

The exact circuit uses $O(n^2)$ logical gates for $n=\log_2N$ qubits. Those counts assume exact controlled rotations and do not include preparing an arbitrary amplitude-encoded input, routing distant qubits, compiling rotations into Clifford+$T$, or extracting many classical coefficients. Gate decomposition treats the synthesis cost. A classical FFT instead accepts a stored array and returns a readable array; these are different input/output tasks.

The coherent transform is used in phase estimation and Shor’s algorithm, whose advantages depend on the rest of the algorithm as well. For a terminal QFT measurement, the semiclassical construction of Griffiths and Niu replaces coherent controlled phases with ordered measurements and classical feedforward. It reproduces the relevant measured output, not a reusable coherent QFT state; mid-circuit measurement explains the distinction.

Worked example: three qubits

Use $q_2q_1q_0$ order and prepare $x=5=101_2$. The circuit applies, in time order,

$$\begin{gathered} H_{q_2},\quad CP_2(q_1,q_2),\quad CP_3(q_0,q_2),\\ H_{q_1},\quad CP_2(q_0,q_1),\quad H_{q_0},\\ \operatorname{SWAP}(q_2,q_0). \end{gathered}$$

It uses three Hadamards, three controlled phases and one logical SWAP; the two initial $X$ gates used to prepare $101$ are separate preparation costs.

For $x=5$, the analytic output in increasing $y$ order is

$$F_8\lvert5\rangle = \frac{1}{\sqrt8} \begin{pmatrix} 1\\ e^{5\pi i/4}\\ i\\ e^{7\pi i/4}\\ -1\\ e^{\pi i/4}\\ -i\\ e^{3\pi i/4} \end{pmatrix}.$$

The binary-fraction form gives the same column as

$$\frac{ \lvert0\rangle-\lvert1\rangle }{\sqrt2} \otimes \frac{ \lvert0\rangle+i\lvert1\rangle }{\sqrt2} \otimes \frac{ \lvert0\rangle+e^{5\pi i/4}\lvert1\rangle }{\sqrt2}.$$

Every consecutive non-wrapping amplitude ratio is

$$\frac{ \langle y+1\rvert F_8\lvert5\rangle }{ \langle y\rvert F_8\lvert5\rangle } = e^{5\pi i/4}, \qquad y=0,\ldots,6.$$

That phase-sensitive check complements

$$U_{\mathrm{core}} = B_3F_8$$

and

$$F_8^\dagger F_8\lvert5\rangle = \lvert5\rangle.$$

Worked example: truncating a six-qubit transform

Compare $F_{64}$ with cutoff $m=4$, keeping identical final swaps. Both circuits use six Hadamards and three SWAPs. The exact circuit has fifteen controlled phases; the truncated one retains twelve, omitting two $CP_5$ gates and one $CP_6$ gate. In this logical alphabet the total decreases from $24$ to $21$ gates.

The exact and retained controlled-phase counts are

$$N_{CP} = \frac{6\cdot5}{2} = 15, \qquad N_{CP}^{(4)} = \frac{(4-1)(12-4)}{2} = 12.$$

The three omissions give

$$\begin{aligned} \left\| F_{64}-\widetilde F_{6,4} \right\|_{\mathrm{op}} &\leq 4\sin\left( \frac{\pi}{32} \right) + 2\sin\left( \frac{\pi}{64} \right) \\ &= 0.49020390997. \end{aligned}$$

A dense singular-value calculation gives

$$\left\| F_{64}-\widetilde F_{6,4} \right\|_{\mathrm{op}} = 0.48596035981.$$

For $x=45$, the two nonzero omitted binary-fraction tails are $\pi/16$ and $\pi/32$. The exact-to-truncated column overlap is

$$\left\langle F_{64}45 \middle| \widetilde F_{6,4}45 \right\rangle = 0.98322758570 - 0.14584803490i,$$

and its squared magnitude is

$$\begin{aligned} \left| \left\langle F_{64}45 \middle| \widetilde F_{6,4}45 \right\rangle \right|^2 &= \cos^2\left( \frac{\pi}{32} \right) \cos^2\left( \frac{\pi}{64} \right) \\ &= 0.98800813457. \end{aligned}$$

The fidelity is close to one for this column, but only the operator-norm bound establishes a worst-case budget such as $0.50$. A different input superposition can be more sensitive to coherent phase errors.

The numerical values above follow from building the analytic Fourier matrix and the stated gate sequence, then taking the largest singular value of their difference. A Frobenius norm or largest matrix entry is a different quantity. The overlap can also be checked directly from the product of the two omitted phase factors.

Exercises

Build F₄ and Check Its Powers

Construct the positive-sign four-point transform. Verify unitarity and determine its second and fourth powers.

Solution

With $\omega_4=i$ and rows $y$, columns $x$,

$$F_4 = \frac12 \begin{pmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i \end{pmatrix}.$$

The inner product of columns $x$ and $x'$ is

$$\frac14 \sum_{y=0}^{3} i^{(x-x')y} = \delta_{x,x'},$$

so $F_4^\dagger F_4=I$. The general power identity gives

$$F_4^2\lvert x\rangle = \lvert-x\bmod4\rangle.$$

In particular,

$$F_4^2\lvert1\rangle = \lvert3\rangle.$$

Applying modular negation twice is the identity, hence $F_4^4=I$.

Factor a Basis Column

Factor $F_8\lvert3\rangle$ in order $q_2\otimes q_1\otimes q_0$, then expand the product and match the analytic Fourier column.

Solution

The input bits are $x_2x_1x_0=011$. The three binary fractions are

$$0.x_0 = \frac12, \qquad 0.x_1x_0 = \frac34, \qquad 0.x_2x_1x_0 = \frac38.$$

Therefore

$$F_8\lvert3\rangle = \frac{\lvert0\rangle-\lvert1\rangle}{\sqrt2} \otimes \frac{\lvert0\rangle-i\lvert1\rangle}{\sqrt2} \otimes \frac{\lvert0\rangle+e^{3\pi i/4}\lvert1\rangle}{\sqrt2}.$$

For $y=y_2y_1y_0$, the product coefficient is

$$(-1)^{y_2} (-i)^{y_1} e^{3\pi i y_0/4} = e^{3\pi i y/4}.$$

Thus the expanded vector is

$$\frac{1}{\sqrt8} \begin{pmatrix} 1\\ e^{3\pi i/4}\\ -i\\ e^{\pi i/4}\\ -1\\ e^{7\pi i/4}\\ i\\ e^{5\pi i/4} \end{pmatrix},$$

which is exactly the column with entries $e^{2\pi i3y/8}/\sqrt8$.

Count Exact Logical Resources

Count the exact logical QFT gates for $n=7$. Then translate only the logical SWAP count into CNOTs.

Solution

The formulas give

$$N_H = 7, \qquad N_{CP} = \frac{7\cdot6}{2} = 21, \qquad N_{\mathrm{SWAP}} = \left\lfloor\frac72\right\rfloor = 3.$$

In the declared abstract alphabet the total is

$$7+21+3 = 31.$$

If each logical SWAP is later decomposed as three CNOTs, report nine CNOTs in place of the three SWAPs. The resulting gate count is seven Hadamards, twenty-one controlled phases, and nine CNOTs. No depth follows without a schedule and connectivity model.

Repair Bit Reversal

An intended terminal result is $y=11=1011_2$ on four qubits. Determine the raw no-swap label and state when classical repair is valid.

Solution

The no-swap core applies $B_4$ to the mathematical output:

$$B_4\lvert1011\rangle = \lvert1101\rangle.$$

Interpreted with the original significance convention, the raw label is

$$1101_2 = 13.$$

Applying $B_4$ restores $\lvert1011\rangle$. If computational-basis measurement is immediate, software may instead reverse the recorded bits and report $11$. That relabeling is invalid before a coherent downstream consumer unless the consumer itself is rewritten to absorb $B_4$.

Distinguish Forward and Inverse QFT

Let

$$\lvert\psi_3\rangle = \frac{1}{\sqrt8} \sum_{y=0}^{7} e^{2\pi i3y/8} \lvert y\rangle.$$

Compare the correct inverse with a mistaken application of the forward transform.

Solution

By definition,

$$\lvert\psi_3\rangle = F_8\lvert3\rangle.$$

The declared inverse therefore gives

$$F_8^\dagger \lvert\psi_3\rangle = F_8^\dagger F_8 \lvert3\rangle = \lvert3\rangle.$$

Using the positive-sign forward transform instead gives

$$F_8 \lvert\psi_3\rangle = F_8^2 \lvert3\rangle = \lvert-3\bmod8\rangle = \lvert5\rangle.$$

The wrong sign does not merely add a global phase; it changes the decoded integer.

Truncate a Twelve-Qubit Circuit

For $n=12$ and cutoff $m=5$, count exact, retained, and omitted controlled phases. Evaluate the telescoping bound and test a $0.5$ operator-norm budget.

Solution

The exact count is

$$N_{CP} = \frac{12\cdot11}{2} = 66.$$

The retained and omitted counts are

$$\begin{aligned} N_{CP}^{(5)} &= \frac{(5-1)(24-5)}{2} = 38, \\ N_{\mathrm{omit}} &= \frac{(12-5)(12-5+1)}{2} = 28. \end{aligned}$$

The circuit also has twelve Hadamards and six logical SWAPs. Its phase-sensitive telescoping bound is

$$\begin{aligned} \sum_{\ell=6}^{12} (13-\ell) 2\sin\left( \frac{\pi}{2^\ell} \right) &= 1.17932228487. \end{aligned}$$

Because $1.17932228487>0.5$, this bound does not certify the proposed budget. The actual operator norm might be smaller, but that possibility is not a pass; a tighter proof or a direct worst-case calculation is required.

What does uniform readout establish?

A report observes uniform computational-basis probabilities after transforming a basis state and quotes an $O(n^2)$ logical QFT count. It concludes that the phases and an exponential end-to-end speedup have both been verified. Explain why neither conclusion follows.

Solution

Neither conclusion follows from these observations.

Uniform probabilities establish only

$$\left| \langle y\rvert\psi_{\mathrm{out}}\rangle \right|^2 = \frac1N.$$

They do not determine the relative phases. Verification needs an inverse-reconstruction test, amplitude-ratio comparison, or another interference-sensitive experiment with declared tolerances.

The $O(n^2)$ count applies only to the abstract transform on $n=\log_2N$ coherently encoded qubits. An end-to-end claim must also account for input preparation or oracle access, repetitions, output measurement, classical postprocessing, synthesis, routing, and the success criterion of the surrounding algorithm. No exponential speedup follows from the primitive count alone.

One omitted phase

Take $n=4$, cutoff $m=3$ and input $x=11=1011_2$. Count the omitted gates, calculate the exact operator-norm error, and find the probability that applying the exact inverse to the approximate output returns $11$. Does the approximation meet worst-case budgets $0.40$ and $0.10$?

Solution

The exact circuit has four Hadamards, six controlled phases and two SWAPs. The truncated circuit omits only $CP_4$ and retains the other eleven logical gates. Because a single gate differs between otherwise identical unitary prefixes and suffixes, norm invariance gives the exact error

$$\|F_{16}-\widetilde F_{4,3}\|_{\rm op} =\|CP_4-I\|_{\rm op} =2\sin(\pi/16)\simeq0.39018064403.$$

It meets the $0.40$ budget and fails the $0.10$ budget. For input $1011$, the omitted conditional phase is active and changes one factor of the product output by $\pi/8$. The squared overlap of exact and approximate outputs is

$$\left|\frac{1+e^{-i\pi/8}}2\right|^2 =\cos^2(\pi/16)\simeq0.96193976626.$$

This is the probability of returning $11$ after the exact inverse. Both forward outputs alone still have uniform computational-basis probabilities. Thus a high selected-state fidelity and a visibly nonzero worst-case error are compatible.

References

• A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary Gates for Quantum Computation”, Physical Review A 52, 3457–3467 (1995).
• A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä, “Approximate Quantum Fourier Transform and Decoherence”, Physical Review A 54, 139–146 (1996).
• R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, “Quantum Algorithms Revisited”, Proceedings of the Royal Society A 454, 339–354 (1998).
• J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series”, Mathematics of Computation 19, 297–301 (1965).
• D. Coppersmith, “An Approximate Fourier Transform Useful in Quantum Factoring”, IBM Research Report RC19642 (1994), arXiv reprint (2002).
• R. B. Griffiths and C.-S. Niu, “Semiclassical Fourier Transform for Quantum Computation”, Physical Review Letters 76, 3228–3231 (1996).
• L. Hales and S. Hallgren, “An Improved Quantum Fourier Transform Algorithm and Applications”, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 515–525 (2000).
• R. Jozsa, “Quantum Algorithms and the Fourier Transform”, Proceedings of the Royal Society A 454, 323–337 (1998).
• D. Maslov, “Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with No Auxiliary Qubits in Finite Neighbor Quantum Architectures”, Physical Review A 76, 052310 (2007).
• Y. Nam, Y. Su, and D. Maslov, “Approximate Quantum Fourier Transform with O(n log n) T Gates”, npj Quantum Information 6, 26 (2020).
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press (2010).
• P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134 (1994).