Fact-checked by Grok 2 weeks ago

Quantum Fourier transform

The Quantum Fourier transform (QFT) is a unitary linear transformation on the state space of an n-qubit quantum computer that generalizes the classical discrete Fourier transform, mapping an input state |j\rangle (where $0 \leq j < 2^n) to the superposition state \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n - 1} e^{2\pi i j k / 2^n} |k\rangle.^[1] First described by Don Coppersmith and popularized by Peter Shor in his 1994 quantum algorithm for integer factorization and discrete logarithms, the QFT serves as a core subroutine that enables efficient period-finding by transforming periodic quantum states into peaked frequency-domain representations.^[1] This algorithm achieves polynomial-time performance on a quantum computer, exponentially faster than the best known classical methods for large inputs.^[1] The QFT can be implemented using a circuit of depth O(n^2) consisting of controlled phase rotations and Hadamard gates, followed by bit reversal to reorder the output qubits, making it feasible on near-term quantum hardware despite noise challenges.^[1] Beyond Shor's algorithm, the QFT underpins a broad class of quantum algorithms, including those solving the hidden subgroup problem over abelian groups, such as Simon's algorithm for identifying hidden strings and Kitaev's phase estimation for eigenvalue approximation.^[2] These applications exploit the QFT's ability to concentrate probability amplitudes near solutions, providing quadratic or exponential speedups over classical counterparts.^[2]^[3]

Fundamentals

Definition

The Quantum Fourier Transform (QFT) is a unitary transformation in quantum computing that functions as the quantum analogue of the classical discrete Fourier transform, converting a quantum state encoding a periodic function into its frequency-domain representation. This transformation leverages the principles of quantum superposition and interference to achieve an exponential speedup in certain computations compared to classical methods.^[4] At a high level, the QFT operates on an input state |x⟩ consisting of n qubits, where x represents an integer from 0 to 2^n - 1, and outputs a superposition of basis states |y⟩ whose amplitudes encode the Fourier coefficients associated with x.^[5] This mapping allows quantum states to represent and manipulate frequency information in a distributed manner across multiple qubits, enabling efficient extraction of periodicities inherent in the input data.^[6] The QFT's primary motivation lies in its role within quantum algorithms that solve problems like period-finding, where classical approaches scale poorly but quantum implementations offer polynomial-time efficiency.^[7] Introduced in the context of quantum computing during the 1990s, it was first formalized by Peter Shor in 1994 as a crucial subroutine for factoring large integers.^[7]

Mathematical Formulation

The quantum Fourier transform (QFT) on an n-qubit system acts on the computational basis states as follows: for a basis state |j\rangle, where j \in \{0, 1, \dots, 2^n - 1\} is represented in binary across the n qubits, the QFT produces

\text{QFT} |j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n - 1} e^{2\pi i j k / 2^n} |k\rangle.

^[1] This transformation encodes the input state into a superposition with phases determined by the discrete exponential, analogous to the classical discrete Fourier transform but realized unitarily on a quantum register. In matrix form, the QFT operator U is a $2^n \times 2^n unitary matrix with elements

U_{jk} = \frac{1}{\sqrt{2^n}} \omega^{jk},

where \omega = e^{2\pi i / 2^n} is a primitive $2^n-th root of unity, and the indices j, k label the rows and columns corresponding to the binary-encoded basis states. This Vandermonde structure arises directly from the one-dimensional irreducible representations (characters) of the cyclic group \mathbb{Z}_{2^n}, which underlies the n-qubit clock register. For multi-qubit systems, states are expressed in Dirac notation using tensor products, such as |j\rangle = |j_{n-1} \dots j_0\rangle = \bigotimes_{l=0}^{n-1} |j_l\rangle, where each j_l \in \{0, 1\} is the l-th bit of j, and the qubits are typically ordered from most significant to least significant. The summation in the QFT formula traverses all possible binary strings for k, ensuring the output spans the full Hilbert space \mathbb{C}^{2^n}. The QFT diagonalizes the clock and shift operators associated with the cyclic group \mathbb{Z}_{2^n}. The shift operator X advances the register by one modulo $2^n, X |j\rangle = |j+1 \mod 2^n\rangle, while the clock operator Z applies phases, Z |j\rangle = \omega^j |j\rangle. In the Fourier basis provided by the QFT, these operators are simultaneously diagonalized via the characters of the group, transforming the regular representation into a direct sum of one-dimensional irreps.

Properties

Unitarity

The quantum Fourier transform (QFT) is a unitary operator on the Hilbert space of n qubits, meaning it satisfies QFT^\dagger QFT = I, where I is the identity operator and QFT^\dagger is the adjoint (Hermitian conjugate) of the QFT.^[8] This property ensures that the QFT maps orthonormal bases to orthonormal bases while preserving the structure of quantum states.^[9] To verify unitarity, consider the QFT matrix F with entries F_{jk} = \frac{1}{\sqrt{N}} \omega^{jk}, where N = 2^n and \omega = e^{2\pi i / N}. The (j,k)-th entry of F^\dagger F is given by

\frac{1}{N} \sum_{m=0}^{N-1} \omega^{m(k-j)},

which is the sum of a geometric series with ratio \omega^{k-j}. This sum equals N if k \equiv j \pmod{N} (yielding 1 after normalization by N), and 0 otherwise, due to the formula

\sum_{m=0}^{N-1} \omega^{mk} = N \delta_{k,0 \pmod{N}}.

Thus, F^\dagger F = I, confirming that the rows (and columns) of F are orthonormal.^[8]^[9] As a unitary operator, the QFT is invertible, with its inverse given by QFT^\dagger, which corresponds to the QFT using \omega^{-1} instead of \omega. This invertibility allows the QFT to be reversed exactly in quantum circuits, supporting reversible quantum computation without loss of information.^[10] Unitarity also implies norm preservation: for any quantum state |\psi\rangle, \| QFT |\psi\rangle \| = \| |\psi\rangle \|, maintaining the total probability of 1 across the state vector.^[11] Furthermore, the QFT preserves inner products in the computational basis, so \langle \phi | \psi \rangle = \langle QFT \phi | QFT \psi \rangle for any states |\phi\rangle and |\psi\rangle, ensuring that quantum superpositions and coherences are faithfully transformed without distortion.^[11]

Spectral and Shift Properties

The Quantum Fourier Transform (QFT) exhibits key spectral properties that extend beyond its unitarity, particularly in diagonalizing specific quantum operators. The QFT diagonalizes the cyclic shift operator X, defined on an n-qubit computational basis as X |j\rangle = |j + 1 \mod 2^n\rangle for j = 0, \dots, 2^n - 1, yielding eigenvalues \omega^k where \omega = e^{2\pi i / 2^n} and k = 0, \dots, 2^n - 1. This diagonalization arises because the eigenbasis of the QFT consists of states that are simultaneous eigenvectors of both the shift and clock operators, allowing the QFT to transform the shift into a diagonal phase matrix. Such a property underpins the efficiency of QFT in algorithms involving periodic structures, like order-finding and phase estimation, by revealing the underlying frequency components of shift-invariant operations. A direct analogue of the classical discrete Fourier transform's shift theorem applies to the QFT, linking spatial shifts to phase modulations in the frequency domain. For a state representing a function f shifted by m positions, the QFT output is \widehat{f \circ \sigma_m}(k) = e^{2\pi i m k / 2^n} \hat{f}(k), where \sigma_m denotes the shift and \hat{f} is the unshifted QFT. This modulation property converts additive shifts in the position basis into multiplicative phases, enabling quantum algorithms to detect hidden shifts efficiently without exhaustive search. It is particularly valuable in problems where the shift encodes unknown parameters, as the phase factors amplify interference patterns in the Fourier basis. The QFT's formulation inherently imposes periodicity on inputs over $2^n points, mirroring the discrete nature of quantum registers and leading to aliasing for non-periodic signals, where higher frequencies wrap around the spectrum. This periodicity ensures the transform operates within a finite cyclic group, but it requires careful encoding to mitigate artifacts in applications involving aperiodic data. Complementing these, the QFT obeys a convolution theorem: the transform of a cyclic convolution f * g equals the pointwise (Hadamard) product of the individual transforms, \widehat{f * g} = \hat{f} \odot \hat{g}. In quantum contexts, this facilitates operations like multiplication by converting convolutions to simpler multiplications in the Fourier domain, supporting scalable quantum arithmetic routines.^[12]

Implementation

Quantum Circuit Design

The standard quantum circuit for the Quantum Fourier transform (QFT) on n qubits is constructed using Hadamard gates and controlled-phase rotation gates, realizing the unitary operator that performs the QFT on the computational basis states.^[13] The qubits are typically labeled from 0 to n-1, with qubit 0 as the least significant bit. The circuit construction proceeds iteratively from the least to the most significant qubit. First, a Hadamard gate H is applied to qubit 0, creating a uniform superposition in that register. Then, controlled-phase rotation gates are applied: qubit 0 serves as the control for phase rotations on qubits 1 through n-1, with the rotation angle for the gate targeting qubit j given by $2\pi / 2^{j+1}. This process repeats for subsequent qubits; for qubit 1, a Hadamard gate is applied, followed by controlled-phase rotations on qubits 2 through n-1 with angles $2\pi / 2^{j} for target qubit j > 1. In general, for control qubit k (where $0 \leq k < n), a Hadamard is applied, followed by controlled-phase gates targeting qubits j > k with phase e^{2\pi i / 2^{j-k+1}}. At the end, swap gates may be included to reverse the qubit order, as the output frequencies appear in bit-reversed order relative to the input.^[13] The phase rotation gates R_m are diagonal unitaries defined as

R_m = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^m} \end{pmatrix},

for m \geq 2, and implemented as controlled operations where the control qubit determines whether the phase is applied to the target. Each qubit receives one Hadamard gate, and the total number of controlled-phase gates is n(n-1)/2, leading to an overall decomposition requiring O(n^2) elementary gates. The Hadamard and controlled-phase gates can be further decomposed into more primitive operations if needed, such as using controlled-NOT and single-qubit rotations for the phases.^[13] In circuit diagrams, the QFT is represented as a linear array of n qubit wires, with Hadamard gates placed at the start of each wire. The controlled-phase gates form an upper-triangular structure: vertical control lines connect each qubit k to all subsequent targets j > k, with phase labels indicating the R_m gate for m = j - k + 1. This results in a dense network of controls, emphasizing the iterative buildup of phase factors from lower to higher bits. Swap gates, if used, appear as crossing pairs at the circuit's output to reorder the qubits.^[13] For fault-tolerant quantum computing, where precise rotations are costly, the QFT circuit can be approximated by truncating small phase angles (e.g., setting R_m \approx I for large m) or removing distant controlled interactions, reducing the gate count to O(n \log n) while maintaining sufficient accuracy for applications like phase estimation. Such approximations preserve the essential Fourier structure with bounded error and are optimized for metrics like T-gate depth in Clifford+T libraries.

Computational Complexity

The exact quantum Fourier transform (QFT) on n qubits requires \Theta(n^2) single-qubit and controlled-phase gates in its standard implementation, comprising n Hadamard gates, n(n-1)/2 controlled-phase gates, and n/2 swap gates to reverse the output order.^[14] ^[13] This quadratic gate complexity arises from the need for each qubit to interact with all others through controlled rotations, reflecting the all-to-all connectivity inherent in the transform. Recent advancements have improved the exact QFT to \Theta(n \log^2 n) gates using recursive partitioning, though the classical standard remains the baseline for most analyses.^[14] Approximate versions of the QFT mitigate this overhead by truncating controlled rotations with sufficiently small phase angles, bounding the diamond norm error to at most \epsilon while reducing the gate count to O(n \log n).^[15] Such approximations are particularly valuable in fault-tolerant settings, where the T-gate count—a measure of non-Clifford operations—can be lowered from O(n \log^2 n) to O(n \log n) using measurement-based circuits and a shared phase gradient state, enabling practical implementations with controlled error. Further optimizations as of October 2025 have reduced the T-depth in approximate QFT implementations.^[15]^[16] These reductions maintain the transform's utility in algorithms while trading precision for efficiency. The QFT operates on n logical qubits to perform a $2^n-point transform, encoding the input state in the computational basis of these qubits without additional logical qubits for the core operation.^[14] In fault-tolerant quantum computing, however, implementing the required single-qubit rotations demands auxiliary qubits (ancillas) to encode approximate rotations via Clifford and T gates, with the total number scaling as O(n \log(1/\epsilon)) depending on the error tolerance and encoding scheme.^[17] The circuit depth of the standard exact QFT is O(n), as the controlled-phase gates on each target qubit must be applied sequentially but can proceed in parallel across qubits.^[13] With enhanced parallelism via ancilla qubits or measurement feedback, the depth can be reduced to O(\log n + \log \log(1/\epsilon)) for approximate QFTs, facilitating faster execution on near-term hardware.^[18] In comparison to the classical fast Fourier transform (FFT), which requires O(N \log N) operations for an N-point transform with N=2^n, the QFT achieves an exponential speedup by evaluating the transform over superpositions in O(n^2) = O(\log^2 N) gates, enabling the processing of exponentially larger inputs on logarithmic resources.^[19] This advantage is most pronounced when only a subset of Fourier coefficients is needed, as full measurement of the QFT output would collapse the speedup.^[19]

Examples and Applications

Basic Qubit Examples

The one-qubit Quantum Fourier Transform (QFT) is equivalent to the Hadamard gate H, which acts on the computational basis states as H |0\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle) and H |1\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle).^[20]^[21] This transformation creates an equal superposition for |0\rangle and a superposition with a relative phase for |1\rangle, illustrating the core idea of the QFT in spreading the amplitude across basis states with phase factors.^[21] On the Bloch sphere, the initial state |0\rangle lies at the north pole (along the positive z-axis). Applying the Hadamard gate rotates this state to the equator, specifically to the point (1, 0, 0) in Cartesian coordinates, representing the superposition \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle); similarly, |1\rangle at the south pole rotates to (-1, 0, 0). This visualization highlights how the QFT introduces coherence and phase without changing the purity of the single-qubit state. For two qubits, the QFT is a 4×4 unitary matrix with entries U_{k,j} = \frac{1}{2} \exp\left( \frac{2\pi i \, k j}{4} \right) for k, j = 0, 1, 2, 3, where the phase factors involve e^{i \pi / 2} = i.^[21] Applying this to basis states produces superpositions such as QFT |00\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle), QFT |01\rangle = \frac{1}{2} (|00\rangle + i |01\rangle - |10\rangle - i |11\rangle), QFT |10\rangle = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle), and QFT |11\rangle = \frac{1}{2} (|00\rangle - i |01\rangle - |10\rangle + i |11\rangle).^[21] To compute this step-by-step using the standard QFT circuit (which includes Hadamard gates on each qubit and a controlled-phase gate with angle \pi/2 controlled by the higher qubit on the lower one), consider the input |00\rangle. First, apply a Hadamard to the least significant qubit (q0): |00\rangle \to \frac{1}{\sqrt{2}} (|00\rangle + |01\rangle). Next, the controlled-phase gate (control q1=0, target q0) applies no phase shift, preserving the state. Then, apply a Hadamard to the most significant qubit (q1): this yields \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle) in the tensor product, but accounting for the bit ordering, it matches \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle), verifying the formula.^[21] Similar computations for other inputs introduce the appropriate phases from the controlled gate when the control qubit is |1\rangle, aligning with the matrix entries.^[21] For visualization in the two-qubit case, the probability amplitudes for QFT |00\rangle are all \left|\frac{1}{2}\right|^2 = \frac{1}{4} across the four basis states, forming a uniform distribution; for QFT |01\rangle, the amplitudes \frac{1}{2}, \frac{i}{2}, -\frac{1}{2}, -\frac{i}{2} yield equal probabilities of \frac{1}{4} but with complex phases that encode frequency information.^[21] This can be represented as a bar chart of probabilities or a phasor diagram showing the rotating phases $1, i, -1, -i.^[21]

Role in Quantum Algorithms

The quantum Fourier transform (QFT) plays a pivotal role in Shor's algorithm, a groundbreaking quantum procedure for integer factorization developed by Peter Shor in 1994. In this algorithm, a superposition of modular exponentiations creates periodic states, and the QFT efficiently extracts the period by transforming the state into the frequency domain, enabling the probabilistic identification of factors in polynomial time on a quantum computer—a task intractable for classical computers on large inputs.^[22] The QFT is equally central to the quantum phase estimation (QPE) algorithm, first introduced by Alexei Kitaev in 1995 as part of his work on quantum measurements and the Abelian stabilizer problem. QPE uses the QFT to convert approximate phase kicks—arising from repeated applications of a unitary operator on its eigenvector—into a binary expansion of the eigenvalue's phase, achieving exponential precision speedup over classical methods. This makes QPE a foundational subroutine in diverse quantum algorithms, including those for Hamiltonian simulation and eigenvalue solving in quantum chemistry.^[23] For the hidden subgroup problem (HSP) over abelian groups, the QFT provides an efficient quantum algorithm by enabling Fourier sampling of the group's characters, which reveals the hidden subgroup through measurement outcomes. As detailed in foundational analyses, this approach solves the abelian HSP in polynomial time, directly underpinning cryptographic primitives like Shor's factoring and discrete logarithm problems while offering a framework for broader symmetry-based computations.^[24] Recent advancements since 2020 have integrated the QFT into variational quantum algorithms (VQAs) for approximate Fourier analysis in quantum machine learning. These developments leverage QFT-based expansions to decompose loss functions or circuit outputs into frequency components, improving optimization landscapes and enabling tasks like signal processing and pattern recognition with enhanced expressivity on noisy intermediate-scale quantum devices.^[25]^[26] As of 2025, further progress includes variational noise mitigation techniques applied to QFT circuits for improved fidelity under coherent and incoherent noise,^[27] and hybrid Quantum Fourier Neural Operators that exploit the QFT's efficiency for scientific computing tasks such as solving partial differential equations.^[28]

Relations to Other Transforms

Connection to Classical DFT

The classical discrete Fourier transform (DFT) is a mathematical operation that decomposes a finite sequence of equally spaced samples of a function into a sum of complex sinusoids, represented by the formula

X_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \exp\left( - \frac{2\pi i j k}{N} \right),

where N = 2^n, x_j are the input values, and X_k are the frequency-domain coefficients for k = 0, \dots, N-1. This transform is efficiently computed using the fast Fourier transform (FFT) algorithm, which requires O(N \log N) operations. The quantum Fourier transform (QFT) serves as the quantum analog of the classical DFT, applying the same mathematical structure to quantum states in a Hilbert space of dimension N = 2^n. It maps a computational basis state |j\rangle to \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \exp\left( 2\pi i j k / N \right) |k\rangle, preserving the unitary nature through normalization and leveraging the linearity of quantum mechanics.^[1] Unlike the classical DFT, which processes a vector of N classical inputs sequentially, the QFT exploits quantum superposition to evaluate the transform across all $2^n points in parallel within a single circuit execution, achieving an effective complexity of O(n^2) = O((\log N)^2) gates compared to the classical O(N \log N).^[1] Key differences arise in output handling: the classical DFT yields coefficients X_k directly accessible for further computation, whereas the QFT encodes the transform as amplitudes in the output quantum state, which cannot be read arbitrarily due to the no-cloning theorem and requires measurement to extract probabilistic information. This quantum parallelism enables exponential speedup in certain applications but introduces challenges in readout and error propagation not present in classical processing.^[1] Historically, the QFT was developed as an adaptation of the Cooley-Tukey FFT algorithm for quantum circuits, originally discovered internally by Don Coppersmith in 1994^[29] and formalized in the context of quantum algorithms by Peter Shor, who tailored it to exploit quantum linearity for period-finding tasks.^[1] This evolution shifted the focus from classical divide-and-conquer recursion to a gate-based decomposition suitable for qubit registers, maintaining fidelity to the classical transform while harnessing quantum effects.

Relation to Quantum Hadamard Transform

The quantum Fourier transform (QFT) on a single qubit, corresponding to n=1, is precisely the Hadamard gate H, defined by the matrix

H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix},

which performs the 2-point discrete Fourier transform.^[30] For multiple qubits, the tensor product of Hadamard gates H^{\otimes n} applied to the all-zero state |0\rangle^{\otimes n} generates a uniform superposition \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} |k\rangle. This uniform superposition is exactly the output of the QFT when applied to the same input state |0\rangle^{\otimes n}, making H^{\otimes n} |0\rangle^{\otimes n} a special case of the QFT restricted to the zero-frequency input. In contrast to the Hadamard transform, which produces only real-valued \pm 1/\sqrt{2} entries and lacks phase information beyond sign flips, the full QFT incorporates complex phases e^{2\pi i j k / 2^n} to encode frequency components across the basis states. These phases, implemented via controlled rotation gates in the QFT circuit, enable the transform to distinguish different input frequencies, a capability absent in the phase-free Hadamard operations.^[1] In quantum circuits, the Hadamard gate frequently serves as the initial operation in the QFT implementation, applied to each output qubit before subsequent controlled-phase gates introduce the necessary frequency-dependent phases; however, the reverse—using the full QFT to approximate a multi-qubit Hadamard—is not generally efficient due to the additional phase complexity.^[1]

Generalizations

QFT over Abelian Groups

The quantum Fourier transform (QFT) over a finite abelian group G generalizes the standard QFT on the cyclic group \mathbb{Z}_{2^n} by mapping states in the group element basis to the dual space spanned by the irreducible characters of G. Specifically, for a basis \{|g\rangle : g \in G\}, the QFT_G acts as

\text{QFT}_G |g\rangle = \frac{1}{\sqrt{|G|}} \sum_{\chi \in \hat{G}} \chi(g) |\chi\rangle,

where \hat{G} is the dual group consisting of all characters \chi: G \to \mathbb{C}^\times (homomorphisms to the multiplicative group of unit-modulus complex numbers), and |\chi\rangle denotes the basis state corresponding to \chi.^[31] This unitary transformation diagonalizes the convolution operation on functions over G, analogous to how the discrete Fourier transform diagonalizes circulant matrices on \mathbb{Z}_N. The characters form an orthonormal basis under the inner product \langle \chi, \psi \rangle = \frac{1}{|G|} \sum_{g \in G} \overline{\chi(g)} \psi(g) = \delta_{\chi,\psi}, ensuring the QFT is unitary.^[32] For abelian groups that are direct products of cyclic groups, such as G = \mathbb{Z}_p \times \mathbb{Z}_q with p and q primes, the characters are tensor products of the individual cyclic characters: \chi_{(k,\ell)}((m,n)) = e^{2\pi i (k m / p + \ell n / q)} for k = 0, \dots, p-1 and \ell = 0, \dots, q-1. Thus, the QFT on [G](/page/G) decomposes as a tensor product [\text{QFT}_G = \text{QFT}_{\mathbb{Z}_p} \otimes \text{QFT}_{\mathbb{Z}_q}](/page/Tensor_product), applied to the respective registers encoding elements of each factor. This structure simplifies computation, as the overall transform requires only the circuits for the component QFTs. More generally, any finite abelian [G](/page/G) is isomorphic to a direct sum \bigoplus_i \mathbb{Z}_{N_i} by the fundamental theorem of finite abelian groups, allowing the QFT to be expressed via the character table of G, which tabulates \chi_j(g) for all j, g \in G.^[31]^[32] The quantum circuit for the QFT over such groups generalizes the cyclic case by incorporating group-specific phase gates derived from the character table. For G = \mathbb{Z}_p \times \mathbb{Z}_q, the circuit applies the standard QFT phases e^{2\pi i k / p} and e^{2\pi i \ell / q} via controlled-phase rotations between qubits representing the coordinates, with the total gate count scaling as O(\log p \cdot \log q + \log q \cdot \log p) for the tensor product structure. In general, for G with |G| = 2^n, the circuit depth is O(n) and size O(n^2), using Hadamard gates for the \mathbb{Z}_2 factors and controlled rotations for higher-order terms, though approximate versions can reduce depth to O(\log n). These circuits enable efficient implementation on quantum hardware for groups arising in cryptographic contexts.^[31] A primary application of the abelian QFT is in solving the hidden subgroup problem (HSP) over non-cyclic groups, where an oracle provides access to cosets of an unknown subgroup H \leq G. By applying the QFT to the state \sum_{g \in G} |g\rangle |f(g)\rangle (with f constant on cosets and distinct otherwise), Fourier sampling yields measurements peaked on the annihilator H^\perp = \{\chi \in \hat{G} : \chi(h) = 1 \ \forall h \in H\}, from which H can be recovered using O(\log^2 |G|) samples. This extends Shor's algorithm (HSP on \mathbb{Z}_N \times \mathbb{Z}_N) to arbitrary finite abelian G, with polynomial-time solvability.^[31]

QFT over Finite Fields

The quantum Fourier transform (QFT) over finite fields extends the standard QFT to the additive group of a finite field \mathbb{F}_{q^n}, where q = p^m with p prime and m, n \in \mathbb{N}, enabling quantum computations in non-binary settings such as coding theory. This generalization relies on the abelian group structure of the field's additive group but leverages the field's multiplicative properties for character definitions. As a prerequisite, it builds on the broader framework for QFT over finite abelian groups, where characters provide the Fourier basis.^[33] The formulation employs additive characters \psi_a(x) = \exp(2\pi i \cdot \mathrm{Tr}(a x)/p) for a, x \in \mathbb{F}_{q^n}, with \mathrm{Tr}: \mathbb{F}_{q^n} \to \mathbb{F}_p denoting the field trace function, which is a \mathbb{F}_p-linear map. These characters form an orthogonal basis for functions on the additive group, satisfying \sum_{x \in \mathbb{F}_{q^n}} \psi_a(x) \overline{\psi_b(x)} = q^n \delta_{a,b}. The QFT is then defined on computational basis states labeled by field elements, transforming a state |v\rangle as

\mathrm{QFT} |v\rangle = \frac{1}{\sqrt{q^n}} \sum_{w \in \mathbb{F}_{q^n}} \psi_v(w) |w\rangle,

where \psi_v(w) = \exp(2\pi i \cdot \mathrm{Tr}(v w)/p) and multiplication v w is in the field; this acts on the full space of dimension q^n. For vector spaces over the field, such as (\mathbb{F}_{q^n})^k, the transform tensorizes accordingly, but the core operation remains on individual field components.^[33] Implementing the QFT over \mathbb{F}_{q^n} poses circuit challenges, as it requires q-ary quantum gates to directly manipulate field elements or embedding into qubit registers via a basis representation, such as treating \mathbb{F}_{q^n} as an n-dimensional vector space over \mathbb{F}_q. The resulting circuit complexity is O((q n)^2) gates in the general case, though optimizations for prime fields or characteristic 2 reduce it to O(n^2 \log^2 p) using tensor products of smaller QFTs and linear transformations. These implementations demand precise control over phase gates corresponding to the trace evaluations, limiting efficiency on current qubit hardware without approximation. Applications of the QFT over finite fields include quantum Reed-Solomon codes, which adapt classical Reed-Solomon error-correcting codes from \mathbb{F}_{2^k} to quantum settings using cyclic discrete Fourier transforms over the field for encoding and syndrome computation in the frequency domain.^[34] Emerging research post-2010 has extended this to quantum algorithms for decoding generalized Reed-Solomon codes and hidden structure problems in finite fields, enhancing quantum error correction beyond binary alphabets.

References

[1]
[quant-ph/9508027] Polynomial-Time Algorithms for Prime ... - arXiv
Aug 30, 1995 · ... Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. ... View PDF · TeX Source · view license.
[2]
Quantum algorithms and the Fourier transform - Journals
(2016) Discrete quantum Fourier transform using weak cross-Kerr nonlinearity and displacement operator and photon-number-resolving measurement under the ...
[3]
Intro to Quantum Fourier Transform | PennyLane Demos
Apr 15, 2024 · The quantum Fourier transform (QFT) is one of the most important building blocks in quantum algorithms, famously used in quantum phase estimation and Shor's ...Defining the Quantum Fourier... · Building the Quantum Fourier...
[4]
[1911.03055] Quantum circuit for the fast Fourier transform - arXiv
Nov 8, 2019 · Namely, our FFT is defined as a transformation of the tensor product of quantum states. It is essentially different from the so-called quantum ...
[5]
What is Quantum Fourier Transform - QuEra Computing
The Quantum Fourier Transform (QFT) is the quantum counterpart to the classical Fourier transform and plays a fundamental role in various quantum algorithms.
[6]
Algorithms for quantum computation: discrete logarithms and factoring
This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is ...
[7]
[PDF] 1 The quantum Fourier transform and periodicities
The quantum Fourier transform (QFT) can be viewed as a generalisation of the Hadamard ... The latter sum is just the geometric series with α = ωk−j, divided by N.
[8]
[PDF] Quantum Fourier Transform (QFT) - People @EECS
Quantum Fourier Transform (QFT). Quantum Computation is all about QFT. Why ... (geometric series with sums to since . 1. 1. 1. 0. 1 1 1. 0,. 1. 1. 1 jl jk. l j k.
[9]
[PDF] Lecture Notes on Quantum Algorithms - UMD Computer Science
Apr 17, 2025 · using the inverse of the reversible circuit for ... Applying the inverse quantum Fourier transform over Zp × Zp, we obtain the state.
[10]
[PDF] Lecture 4 1 Unitary Operators and Quantum Gates - People @EECS
The colums of U form an orthonormal basis. • U preserves inner products, i.e. (~v,~w)=(U~v,U~w). Indeed, (U~v ...
[11]
https://people.eecs.berkeley.edu/~vazirani/s05cs191/lectures/lecture4.pdf
[12]
https://arxiv.org/pdf/quant-ph/9708016.pdf
[13]
A Faster Quantum Fourier Transform
### Summary of Gate Complexity for Quantum Fourier Transform (QFT)
[14]
Approximate Quantum Fourier Transform with $O(n \log(n))$ T gates
Mar 13, 2018 · In this paper, we show how to obtain approximate QFT with the T-count of O(n \log(n)). Our approach relies on quantum circuits with measurements and ...
[15]
None
Nothing is retrieved...<|separator|>
[16]
Fast parallel circuits for the quantum Fourier transform - IEEE Xplore
Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time ...
[17]
[PDF] A Comparison of Quantum and Traditional Fourier Transform ...
Nov 23, 2020 · The quantum Fourier transform (QFT) can calculate the Fourier transform of a vector of size N with time complexity O(log2 N) as compared to ...
[18]
[PDF] Quantum Fourier Transform Revisited - arXiv
Sep 23, 2020 · The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix.
[19]
[PDF] Quantum arithmetic with the Quantum Fourier Transform - arXiv
May 2, 2017 · Abstract. The Quantum Fourier Transform offers an interesting way to perform arithmetic operations on a quantum computer.
[20]
[PDF] Algorithms for Quantum Computation: - Discrete Log and Factoring
This paper gives algorithms for the discrete log and the factoring problems that take random polynomial time on a quantum computer (thus giving the first ...
[21]
Quantum measurements and the Abelian Stabilizer Problem - arXiv
Nov 20, 1995 · We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm.
[22]
The Quantum Fourier Transform and Extensions of the Abelian ...
Nov 30, 2002 · First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show ...
[23]
Fourier expansion in variational quantum algorithms | Phys. Rev. A
Sep 6, 2023 · The Fourier expansion of the loss function in variational quantum algorithms (VQAs) contains a wealth of information yet is generally hard to access.
[24]
Fourier Analysis of Variational Quantum Circuits for Supervised ...
This allows us to provide an algorithm which computes the exact spectrum of any given circuit and the corresponding Fourier coefficients.Missing: approximate 2020-2025<|control11|><|separator|>
[25]
[2003.03011] Quantum Fourier Transform Revisited - arXiv
Mar 6, 2020 · In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition.
[26]
Quantum Fourier transform is the building block for creating ... - Nature
Nov 15, 2021 · This study demonstrates entanglement can be exclusively constituted by quantum Fourier transform (QFT) blocks.Missing: primary | Show results with:primary
[27]
None
Summary of each segment:
[28]
[PDF] 1 Fourier Transform over Finite Abelian Groups - People @EECS
Given a finite abelian group G with n elements, we want to study the Fourier transform over it. Usually, we are interested in the following two cases: (1) G ...
[29]
[PDF] arXiv:quant-ph/0308148v1 27 Aug 2003
The quantum Fourier transform on abelian groups. Let G be a finite abelian group. To emphesize that our group is abelian we use the addition as the group ...