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. This page fixes the signs, bit order, phase gates, swaps, resource currencies, and verification tests needed to make that statement precise.

Here, QFT always means quantum Fourier transform. Quantum field theory is spelled out when it is mentioned. The complete derivation and audits below concern only $N=2^n$ and $\mathbb Z_{2^n}$; finite Abelian extensions are orientation, and non-Abelian transforms are outside scope.

Required background. Controlled Operations supplies coherent control, branch-relative phase, controlled-phase semantics, and—through its prerequisites and review links—the register, tensor-order, and single-qubit gate conventions used here.

The Quantum Fourier Transform Contract

Fix an input Hilbert space with computational basis

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

The transform is a unitary map on this same $N$-dimensional space. A complete QFT claim therefore needs more than the phrase “apply a Fourier transform.” It must say:

• how a bitstring denotes the integer $x$;
• which qubit is written first in a ket and drawn first in a circuit;
• whether the forward exponential has positive or negative sign;
• whether the output wires are in mathematical or bit-reversed order;
• which controlled phases are present or omitted;
• which gate alphabet and cost currency are being counted;
• whether the output remains coherent or is measured immediately;
• which phase-sensitive evidence supports an exact or approximate claim.

The licensed output is another quantum state. For

$$\lvert\psi\rangle = \sum_{x=0}^{N-1} a_x\lvert x\rangle,$$

linearity gives

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

The Ten-Field QFT Record

Use this record before comparing two circuits or quoting an approximation or resource result. Every field needs a value; use “N/A” only with a reason.

1. Transform task and licensed claim — State whether the object is a forward QFT, inverse QFT, bit-reversed core, or declared approximation, and identify exactly what the evidence licenses.
2. Registers, dimensions, tensor order, and integer encoding — Give $n$, $N$, register names, ket order, most- and least-significant wires, and the map from bitstrings to integers.
3. Fourier sign, normalization, inverse, and phase convention — Give the matrix element, the root of unity, row and column orientation, and the sign used by the inverse.
4. Input state or subspace and preparation — Name the tested state or promised subspace and account for how it is supplied; arbitrary amplitude loading is not free.
5. Exact circuit, controlled phases, swaps, and access model — Specify time order, every controlled-phase index and wire pair, final swaps, and any coherent access assumed by the surrounding task.
6. Approximation rule, omitted gates, and error metric — Give the cutoff, enumerate omissions, and distinguish an operator norm or process metric from a basis-column fidelity or output distribution.
7. Output contract, measurement, and classical postprocessing — Say whether the output remains coherent, which observable is measured, how bits are interpreted, and which relabeling or estimator follows.
8. Resource currencies, connectivity, and synthesis assumptions — Separate logical gate count and depth from routing, native gates, Clifford+$T$ cost, wall-clock time, and physical error.
9. Verification data, tolerance, uncertainty, and reproducibility — Record exact or numerical reference construction, precision, runtime and version, matrix and wire order, tolerance, uncertainty, and a stable recipe or artifact identity.
10. Conclusion, stopping point, and canonical handoff — State pass or fail under the declared criterion and route algorithmic, compilation, classical-transform, or hardware questions to their owners.

The record prevents three common substitutions: a single input-state check for a worst-case unitary guarantee, uniform basis probabilities for relative-phase verification, and an abstract logical gate count for an end-to-end speedup.

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 is the site-wide sign and normalization cross-check.

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 test normalization, exponent sign, and matrix orientation at once. They do not test whether a circuit’s output wires have subsequently been permuted.

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 need separate contracts. 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 and audit 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).$$

Although the diagonal matrix is invariant under exchanging its two wires, the circuit record still names one control and one target so that access assumptions and gate order remain auditable.

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

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, Inverse Circuits, and Verification

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).$$

Verification should include several logically distinct checks:

• Matrix orientation: compare rows $y$ and columns $x$ with the declared analytic matrix.
• Unitarity: evaluate $U^\dagger U-I$ in a stated entrywise or operator norm.
• Bit order: compare the no-swap core with $B_nF_N$, not directly with $F_N$.
• Inverse reconstruction: test $F_N^\dagger U\lvert x\rangle$ on phase-sensitive inputs.
• Column phases: compare amplitude ratios, not just output probabilities.
• Approximate behavior: report a worst-case process metric separately from selected-state fidelity.

For a basis input, every ideal exact or truncated QFT column constructed from Hadamards and diagonal phases has uniform computational-basis probabilities. Those probabilities can therefore agree even when important relative phases are wrong. Exact algebra has no sampling uncertainty; a floating-point audit still needs a precision, runtime, construction, tolerance, and stable record identity.

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 unitary operator-norm bound with global phase fixed by the circuit matrices. It is not any of the following:

• a phase-optimized unitary distance;
• a channel or diamond distance;
• the fidelity of one basis column;
• total-variation distance between one measurement distribution;
• a phase-estimation or factoring success probability;
• a physical noise or calibration model.

A complete error budget also states how truncation combines with finite-alphabet synthesis, routing, and physical error. Bounds expressed in incompatible metrics cannot simply be added. The dedicated compilation owner must supply the conversion and native cost model.

Resources, Readout, and Canonical Handoffs

The exact circuit uses $O(n^2)$ logical gates, while a fixed or slowly growing cutoff reduces the controlled-phase count to $O(nm)$. Since $n=\log_2N$, those statements concern a coherent $n$-qubit register. They do not include arbitrary state preparation, oracle construction, repetitions, or extraction of a length-$N$ classical vector.

Keep the following currencies separate:

• logical counts of $H$, $CP_\ell$, and SWAP;
• a scheduled logical depth under a declared parallelism model;
• routing and extra swaps on a connectivity graph;
• native one- and two-qubit gates;
• Clifford+$T$ synthesis accuracy and $T$ count or depth;
• control latency and wall-clock duration;
• physical error rates and fault-tolerant overhead.

Circuit Model owns the general register and resource contract. Gate Decomposition owns finite-alphabet synthesis, topology, and native cost. The present page stops at the declared abstract QFT circuit and its coherent truncation error.

Phase Kickback owns the character-eigenstate use of $F_M^\dagger|k\rangle$ after its preparation convention is declared, including modular-addition phase transduction, target return, and quadrature verification. This page retains the transform definition, character-state preparation circuit, bit order, swaps, approximation, and QFT resource count.

Algorithmic Primitives owns the reusable algorithm-interface preview. Quantum Phase Estimation owns powered phase-gradient inputs, inverse-QFT decoding kernels, precision, controlled powers, aliasing, and success. Shor Algorithm owns periodic-state preparation, order finding, continued fractions, retry logic, cryptographic meaning, and end-to-end resources.

Fast Fourier Transform owns algorithms for a stored classical array, including grid, scaling, roundoff, and a readable coefficient vector. Fourier Transform owns continuous-transform analysis. Neither interface is replaced by applying a QFT to amplitudes.

A semiclassical inverse QFT used immediately before measurement can replace coherent two-qubit phases with ordered measurements and classical feedforward under specific terminal-use conditions. Mid-Circuit Measurement and Feedforward owns that dynamic-circuit semantics and timing; it is not an unconditional replacement for a coherent QFT.

Worked Audit: An Exact Three-Qubit QFT

This audit fixes every convention before comparing an analytic $F_8$ with a dense ideal circuit.

1. Transform task and licensed claim — Audit an exact positive-sign QFT on three qubits. Passing licenses equality of the declared ideal logical circuit and $F_8$ within floating-point tolerance; it licenses no hardware performance or algorithmic speedup.
2. Registers, dimensions, tensor order, and integer encoding — $n=3$, $N=8$, $Q=q_2\otimes q_1\otimes q_0$, with $q_2$ most significant, $q_0$ least significant, and $x=4x_2+2x_1+x_0$.
3. Fourier sign, normalization, inverse, and phase convention — Rows are $y=0,\ldots,7$, columns are $x=0,\ldots,7$, $(F_8)_{yx}=e^{2\pi ixy/8}/\sqrt8$, and $F_8^\dagger$ uses the negative exponent.
4. Input state or subspace and preparation — The audited column is $x=5=101_2$. It can be prepared from $\lvert000\rangle$ by $X$ on $q_2$ and $q_0$; those preparation gates are declared but excluded from the QFT ledger.
5. Exact circuit, controlled phases, swaps, and access model — In time order: $H_{q_2}$; $CP_2(q_1,q_2)$; $CP_3(q_0,q_2)$; $H_{q_1}$; $CP_2(q_0,q_1)$; $H_{q_0}$; then $\operatorname{SWAP}(q_2,q_0)$. This is an ideal explicit circuit, not black-box device access.
6. Approximation rule, omitted gates, and error metric — N/A: this is the exact circuit, no phase is omitted, and the exact operator difference is zero. Numerical maximum-entry residuals only witness roundoff in the dense construction.
7. Output contract, measurement, and classical postprocessing — The output remains coherent in mathematical order $q_2q_1q_0$. Computational-basis sampling gives $p(y)=1/8$ for every $y$ and is not a phase test. Verification uses amplitude ratios, the no-swap identity, and inverse reconstruction; no classical bit reversal follows the final SWAP.
8. Resource currencies, connectivity, and synthesis assumptions — The logical alphabet counts three Hadamards, three controlled phases—two $CP_2$ and one $CP_3$—and one SWAP, for seven gates and no QFT ancilla. Depth, routing, native-gate, and Clifford+$T$ costs are N/A because no scheduling, connectivity, or synthesis model is declared.
9. Verification data, tolerance, uncertainty, and reproducibility — Node.js v26.4.0 with V8 14.6.202.34-node.21 uses IEEE-754 binary64 complex pairs, unreduced machine angles, row-$y$/column-$x$ order, and the gate order above. The maximum circuit-matrix residual is $1.42\times10^{-15}$ and the maximum-entry unitarity residual is $2.22\times10^{-16}$. Both pass a common $2\times10^{-14}$ threshold; the embedded recipe applies the stricter $10^{-14}$ unitarity threshold and requires inverse infidelity below $10^{-14}$. There is no sampling uncertainty.
10. Conclusion, stopping point, and canonical handoff — Pass: the exact ideal circuit reproduces $F_8$, including phase and wire order. Compilation belongs to Gate Decomposition; phase-decoding performance belongs to Quantum Phase Estimation.

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

The following source-embedded record is LF-normalized UTF-8 text including its final line feed. Its SHA-256 is f3f7829886868d4a9413e9d6003fce71f47a69b8c34030d3eb3683824b7b7653.

artifact=qft-exact-n3-v1
runtime=Node.js v26.4.0
v8=14.6.202.34-node.21
precision=IEEE-754 binary64
matrix=rows y=0..7; columns x=0..7
tensor=q2,q1,q0
construction=unreduced angles; left-multiplied H then CP; final B3
amplitude_residual=1.415262216750919e-15
unitarity_residual=2.220446049250313e-16
amplitude_tolerance=2e-14
unitarity_tolerance=1e-14
inverse_infidelity_tolerance=1e-14

Worked Audit: A Truncated Six-Qubit QFT

The second audit separates a worst-case process bound from the behavior of one basis column.

1. Transform task and licensed claim — Compare the exact $F_{64}$ with the ideal truncated circuit $\widetilde F_{6,4}$. Passing licenses this declared approximation under a $0.50$ operator-norm budget, not an algorithmic or hardware claim.
2. Registers, dimensions, tensor order, and integer encoding — $n=6$, $N=64$, $Q=q_5\otimes q_4\otimes q_3\otimes q_2\otimes q_1\otimes q_0$, with $q_5$ most significant and $x=\sum_{j=0}^{5}2^jx_j$.
3. Fourier sign, normalization, inverse, and phase convention — The forward matrix has row $y$, column $x$, positive phase $e^{2\pi ixy/64}/8$, and identical final bit-reversal swaps in the exact and truncated circuits. The inverse is the conjugate transpose.
4. Input state or subspace and preparation — The phase-sensitive column test uses $x=45=101101_2$, prepared by $X$ on $q_5,q_3,q_2,q_0$. Preparation is outside the QFT gate ledger.
5. Exact circuit, controlled phases, swaps, and access model — The exact circuit has fifteen controlled phases. Both circuits have six Hadamards and three logical SWAPs in the explicit ideal access model.
6. Approximation rule, omitted gates, and error metric — Cutoff $m=4$ retains twelve controlled phases and omits exactly two $CP_5$ gates and one $CP_6$ gate. The acceptance metric is $\|F_{64}-\widetilde F_{6,4}\|_{\mathrm{op}}$ with fixed circuit phase; the selected-column fidelity is reported separately.
7. Output contract, measurement, and classical postprocessing — The output remains coherent in mathematical wire order. Both tested basis columns have uniform measurement probabilities, so the comparison uses the complex overlap and a worst-case singular value. No classical relabeling is needed because both circuits retain the same swaps.
8. Resource currencies, connectivity, and synthesis assumptions — In the declared alphabet where each $H$, $CP_\ell$, and logical SWAP costs one, the exact total is $6+15+3=24$ and the truncated total is $6+12+3=21$. Depth, routing, synthesis, and wall-clock costs are N/A without additional models.
9. Verification data, tolerance, uncertainty, and reproducibility — Wolfram Language 15.0.0 on Windows x86-64 constructs exact algebraic matrices and evaluates them at 80 digits; a dense binary64 evaluation gives the displayed rounded norm. The largest singular value is used, never a Frobenius or maximum-entry substitute. Exact and truncated unitarity residuals must be below $10^{-12}$; norm, bound, overlap, and fidelity comparisons use the tolerances in the embedded hashed record. There is no sampling uncertainty.
10. Conclusion, stopping point, and canonical handoff — Pass: the analytic upper bound is below $0.50$, and the dense norm is below that bound within tolerance. The basis-state fidelity is supporting evidence only. QPE and Shor success remain with their algorithm owners.

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 the acceptance statement comes from the operator-norm bound. A different input superposition can be more sensitive to coherent phase errors.

The following source-embedded record is LF-normalized UTF-8 text including its final line feed. Its SHA-256 is 83e6cf5b47af7347d3950704ff1486617026490144396c7d34afff97a77accc2.

artifact=qft-truncated-n6-m4-v1
runtime=Wolfram Language 15.0.0 for Microsoft Windows x86-64
precision=exact algebraic construction then N[...,80]
matrix=rows y=0..63; columns x=0..63
tensor=q5,q4,q3,q2,q1,q0
construction=exact Sqrt[2] and Exp[2 Pi I/2^l]; left-multiplied H then CP
cutoff=retain CP_l through l=4; identical final B6
metric=First[SingularValueList[N[F64-U64,80]]]
binary64_witness=0.48596035981
operator_norm=0.48596035980652777989654832415494
analytic_bound=0.49020390997307844
overlap=0.983227585701909050076704269056-0.145848034900037809369668202046i
fidelity=0.988008134569407552740334152322
unitarity_tolerance=1e-12
norm_reference_tolerance=5e-13
bound_slack_tolerance=1e-12
overlap_tolerance=5e-13
process_budget=0.50

Common Failure Modes

Changing the sign without changing the inverse. A negative-sign forward convention is valid, but it exchanges the roles of the matrices used here. Declare the sign at the matrix-element level and test the inverse on a phase-gradient state.

Calling one ordering convention “the endianness.” Ket order, wire order, integer significance, memory layout, and drawing order are separate choices. State all choices needed to interpret a measured string.

Reusing rotation notation ambiguously. The subscript on $CP_\ell$ sets the denominator $2^\ell$; it is not an axis label. Keep it distinct from Bloch rotations such as $R_z(\theta)$.

Dropping swaps silently. The no-swap core implements $B_nF_N$, not $F_N$. A terminal measurement can absorb $B_n$ in classical labels; a coherent downstream circuit cannot do so without being changed.

Verifying only probabilities. A QFT basis column and many incorrectly phased product states all yield the uniform distribution. Check amplitude ratios, recombine with an inverse, or use another interference-sensitive observable.

Leaving an approximate QFT unparameterized. Give $n$, cutoff $m$, every omitted phase, and a metric. “Small rotations were dropped” is not a reproducible circuit.

Replacing a process guarantee with one-column fidelity. A selected basis state can be unusually insensitive to an omission. Report its fidelity as a diagnostic, not as a substitute for a worst-case unitary or channel metric.

Mixing resource currencies. A SWAP counted as one logical gate cannot simultaneously be counted as three CNOTs in the same total. State the alphabet, connectivity, scheduling, and synthesis assumptions before comparing costs.

Treating the QFT as an output oracle for the FFT. The QFT transforms amplitudes and returns quantum samples or coherent states. It does not accept and print an arbitrary length-$N$ classical array in $O(\operatorname{polylog}N)$ work.

Inferring an algorithm or device result from the primitive. The transform circuit alone establishes neither phase-estimation precision, factoring success, end-to-end speedup, nor physical fidelity. Those claims require their canonical owners and additional evidence.

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 mixed primitive ledger is then 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.

Audit a Readout and Speedup Claim

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. Audit the inference.

Solution

Reject both conclusions.

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.

Complete a Ten-Field AQFT Record

Complete the full record for $n=4$, cutoff $m=3$, and input $x=11=1011_2$. Test operator-norm budgets $0.40$ and $0.10$.

Solution

1. Transform task and licensed claim — Compare the exact $F_{16}$ with the ideal cutoff-$3$ circuit on four qubits. Passing licenses only the declared ideal approximation under the stated operator-norm budget.
2. Registers, dimensions, tensor order, and integer encoding — $n=4$, $N=16$, tensor order $q_3\otimes q_2\otimes q_1\otimes q_0$, $q_3$ most significant, and $x=11=1011_2$.
3. Fourier sign, normalization, inverse, and phase convention — $(F_{16})_{yx}=e^{2\pi ixy/16}/4$ with rows $y$, columns $x$, positive-sign forward phase, and negative-sign inverse.
4. Input state or subspace and preparation — The column test uses $\lvert11\rangle=\lvert1011\rangle$, prepared by $X$ on $q_3,q_1,q_0$; preparation is excluded from the transform ledger.
5. Exact circuit, controlled phases, swaps, and access model — The exact circuit has four Hadamards, six controlled phases, and two final logical SWAPs. The ideal access model treats every declared $CP_\ell$ as exact.
6. Approximation rule, omitted gates, and error metric — Cutoff $m=3$ retains five controlled phases and omits the single $CP_4$. Because only one gate differs between otherwise unitary prefixes and suffixes, the operator norm is exactly $2\sin(\pi/16)=0.39018064403$.
7. Output contract, measurement, and classical postprocessing — Exact and approximate outputs remain coherent in the same mathematical wire order. Their basis probabilities are both uniform. Exact inverse reconstruction of the approximate column returns $11$ with probability $\cos^2(\pi/16)=0.96193976626$; no bit relabeling is required.
8. Resource currencies, connectivity, and synthesis assumptions — Exact and retained abstract totals are $4+6+2=12$ and $4+5+2=11$. Ancillas, depth, routing, native synthesis, and time are N/A because no such model is declared.
9. Verification data, tolerance, uncertainty, and reproducibility — Exact algebraic expressions are evaluated with Wolfram Language 15.0.0 at 30 digits and rounded to eleven decimal places. The source-embedded record below fixes wire order, cutoff, metrics, budget, and a $5\times10^{-13}$ comparison tolerance; its SHA-256 is c77a0a0633b8005f2edd75e0c3264d50041bb848238e83971a812f40c30cda19. There is no sampling uncertainty.
10. Conclusion, stopping point, and canonical handoff — The $0.40$ budget passes because $0.39018064403<0.40$. The $0.10$ budget fails, and any claim of an exact QFT fails. Algorithm-specific consequences require the QPE or Shor owner.

The phase-sensitive values are

$$2\sin\left( \frac{\pi}{16} \right) = 0.39018064403,$$

and

$$\cos^2\left( \frac{\pi}{16} \right) = 0.96193976626.$$

The following payload is LF-normalized UTF-8 text including its final line feed.

artifact=qft-aqft-n4-m3-x11-v1
runtime=Wolfram Language 15.0.0 for Microsoft Windows x86-64
precision=exact algebraic expressions then N[...,30]
tensor=q3,q2,q1,q0
cutoff=retain CP_l through l=3; identical final B4
omitted=one CP_4
operator_norm=2 sin(pi/16)=0.3901806440322565
column_fidelity=cos^2(pi/16)=0.9619397662556434
process_budget=0.40
comparison_tolerance=5e-13

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).