Quantum Fourier Transform and Phase Estimation

Introduction and context

The quantum Fourier transform (QFT) and quantum phase estimation (QPE) are two central primitives in quantum algorithms. The QFT changes a computational-basis description into a frequency- or phase-based description. QPE uses controlled applications of a unitary operator and an inverse QFT to estimate an eigenphase. Together, these ideas support algorithms for periodicity finding, eigenvalue estimation, order finding, quantum simulation, and several applications in number theory and physics.

The classical discrete Fourier transform (DFT) maps a sequence of complex amplitudes into frequency components. A direct classical implementation generally requires O(N²) operations for N data points, although the fast Fourier transform reduces this to O(N log N). The QFT is not simply a faster method for reading every Fourier coefficient. Rather, it is a unitary transformation on the amplitudes of a quantum state and can be implemented using O(n²) elementary gates, where N = 2ⁿ. Its usefulness comes from combining it with interference, oracle operations, and measurement.

Learning objectives

By the end of this chapter, you should be able to:

1. Define the QFT and inverse QFT for an n-qubit register.
2. Construct the QFT circuit using Hadamard and controlled-phase gates.
3. Explain the role of bit reversal and approximate QFT circuits.
4. Describe QPE and derive its phase-precision requirements.
5. Apply QFT and QPE to eigenvalue and periodicity problems.
6. Identify implementation limitations, noise sources, and best practices.

1. Fourier analysis in a quantum setting

For N computational basis states, the QFT is the unitary operator F_N defined by

where x and y are integers from 0 to N − 1, i = √−1, and N is normally a power of two for an n-qubit register. By linearity, if

then

The amplitudes a_x and b_y are generally complex. The transformation preserves total probability because F_N is unitary. The inverse transform is

The sign of the exponent distinguishes the forward and inverse transforms. Applying the inverse after the forward transform returns the original state: F_N⁻¹F_N = I.

Fourier phases and periodicity

Suppose a state has amplitudes with a regular periodic structure. The QFT causes constructive interference at frequencies compatible with that period and destructive interference elsewhere. This does not mean that a measurement reveals all amplitudes. Measurement returns one sample, but the algorithm can arrange that useful frequency information has high probability.

For example, the two-qubit state

has amplitudes separated by two positions. Its four-point QFT is

Thus the periodic spacing in the input is reflected in a structured distribution in the Fourier basis. This example is small, but the same interference principle underlies order-finding algorithms.

2. Constructing the QFT circuit

Let N = 2ⁿ and write the binary expansion of x as x₁x₂…xₙ. A useful factorized form is

where 0.x_jx_{j+1}…x_n denotes the binary fraction

The output qubits appear in reverse order relative to the conventional circuit layout. Final SWAP gates are therefore often used to restore the expected order.

The standard exact circuit contains:

• one Hadamard gate on each qubit;
• controlled-phase gates between pairs of qubits;
• optional SWAP gates to undo bit reversal.

A controlled-phase gate with angle θ can be written as

For qubits separated by a suitable binary position, the angle is θ = π/2^k, where k is a positive integer determined by their separation. The circuit uses approximately n(n − 1)/2 controlled-phase gates and n Hadamard gates, plus floor(n/2) SWAP gates. Therefore its two-qubit-gate count is O(n²), and its depth is O(n) when operations on disjoint pairs are scheduled in parallel.

Why the circuit works

A Hadamard creates a superposition containing a phase contribution from a computational-basis bit. Controlled-phase gates add fractional phase information from less significant bits. Together, these operations produce the binary fractions in the factorized expression above. The QFT is therefore not a collection of independent Hadamards: the controlled phases are essential for encoding correlations between binary digits.

Inverse QFT

The inverse QFT is constructed by reversing the QFT circuit and replacing every gate with its adjoint. Hadamard gates are self-adjoint, while

Thus the inverse circuit applies the controlled rotations in reverse order with negative angles, followed by reverse-order SWAP operations if they were present in the forward circuit.

3. Important properties and distinctions

Unitarity

The QFT preserves inner products and probabilities. It is a basis change, not a measurement. The classical Fourier transform of a list of numbers and the QFT of a quantum state are mathematically related but operationally different.

No automatic speed-up for data loading

If N arbitrary classical values must first be loaded into a quantum state, state preparation may require substantial resources. A QFT circuit of O((log N)²) gates does not imply that an arbitrary N-element classical data set can be Fourier transformed and read out in that time. Reading N independent Fourier coefficients also requires many measurements.

Bit reversal

The natural QFT circuit produces qubits in reversed order. A state labelled by binary fraction bits may therefore appear as q_n…q_1 instead of q_1…q_n. Omitting the final SWAPs is acceptable only when the rest of the algorithm accounts for this reversal.

Approximate QFT

Small-angle controlled rotations contribute increasingly little phase. An approximate QFT omits rotations below a chosen threshold. If rotations with angle less than approximately 2π/2^m are omitted, the circuit has fewer gates, with an approximation error that depends on n and m. The value of m should be selected from the algorithm's required phase precision and the device's noise level; it should not be chosen solely to minimize gate count.

4. Phase estimation

Phase estimation determines an unknown phase associated with an eigenvalue of a unitary operator. Let U be unitary and suppose an eigenstate |ψ⟩ satisfies

where 0 ≤ φ < 1. The objective is to estimate φ using a t-qubit precision register. The eigenstate register is assumed to be available, or to have sufficient overlap with the desired eigenstate.

The QPE procedure

The standard QPE circuit has four stages:

1. Prepare the precision register in |0⟩^{⊗t} and the eigenstate register in |ψ⟩.
2. Apply a Hadamard gate to each precision qubit.
3. Apply controlled-U^{2^j} operations, one for each precision qubit j.
4. Apply the inverse QFT to the precision register and measure it.

After the Hadamard gates and controlled powers, the ideal state is

The inverse QFT converts this phase progression into a computational-basis value close to 2^tφ. If φ has an exact t-bit binary representation, the result is exact in the ideal noiseless circuit. Otherwise, measurement gives a distribution concentrated near the nearest t-bit approximations.

Precision and probability

Let M = 2^t and let m be the measured integer. The phase estimate is

For the standard QPE circuit, if a nearest M-grid point is used, the estimate is within approximately 1/(2M) of φ with high probability. A commonly used rigorous guarantee is that the estimate is within 1/M with probability at least 4/π² ≈ 0.405, and success probability can be increased by using additional precision qubits, repeated measurements, or suitable classical post-processing. The exact probability distribution is peaked rather than uniformly bounded, so “t bits” should be interpreted as a resolution statement, not a guarantee that every run returns the same rounded value.

To obtain absolute phase resolution at most ε, choose t so that

or equivalently

If a nearest-grid error of at most ε is required, the stronger grid condition 1/(2·2^t) ≤ ε gives

These statements assume ideal gates, a correctly prepared eigenstate, and an appropriate interpretation of the measured peak.

Eigenstates versus superpositions

If the second register begins in a superposition

where U|ψ_r⟩ = e^{2πiφ_r}|ψ_r⟩, QPE produces a superposition of estimates associated with the phases φ_r. Measurement samples an eigenphase with probability approximately |c_r|², subject to finite precision and interference effects. Consequently, QPE does not generally return every eigenvalue in one run.

Controlled powers

The operation U^{2^j} is a major implementation cost. If U is a known circuit, repeated squaring is not automatically available at the circuit level; the controlled powers must be designed or synthesized. In Hamiltonian simulation, U may have the form

where H is a Hermitian Hamiltonian, τ is an evolution time, and an eigenvalue E of H gives the phase

To recover E without ambiguity, τ must be chosen so that the relevant energy range maps to a unique phase interval, or additional measurements must resolve phase wrapping.

5. Worked example: exact phase estimation

Assume

The phase is φ = 5/8 = 0.101₂. Use t = 3 precision qubits. Since M = 2³ = 8,

The inverse QFT therefore maps the precision register ideally to |101⟩, which is the binary representation of 5. Measuring gives m = 5, and

This is exact because the phase has three or fewer binary fractional bits. In practice, controlled-U² and controlled-U⁴ must be implemented accurately, and state preparation must produce the intended eigenstate.

6. Worked example: selecting precision

Suppose an application requires phase resolution ε = 0.01. Using the conservative condition 1/2^t ≤ ε,

Thus at least seven precision qubits are required for a grid spacing no larger than 0.01. The register has M = 128 possible grid points and spacing 1/128 ≈ 0.0078125. This does not eliminate statistical error, gate error, or eigenstate-preparation error; it only establishes the digital resolution of the phase register.

7. Periodicity and order finding

A periodic state has the form of a superposition over values separated by a period r. Applying the QFT produces peaks near integer multiples of N/r. If N is not an exact multiple of r, the peaks are broadened and occur near the best rational approximations to those multiples.

In order finding, one seeks the smallest positive integer r satisfying

for a chosen integer a relatively prime to N. A quantum circuit creates a periodic function related to a^x mod N, applies the QFT to the input register, and measures a value c close to a multiple of Q/r. A classical continued-fraction procedure then attempts to recover the denominator r from c/Q, where Q is the size of the Fourier register. The procedure requires verification because a convergent may correspond to a divisor or an incorrect candidate.

The quantum part identifies frequency information; classical post-processing interprets that information. This is a representative hybrid quantum–classical workflow.

8. Applied case: illustrative molecular-energy estimation

Background

Consider an illustrative quantum-chemistry experiment in which a prepared trial state has large overlap with an eigenstate of a molecular Hamiltonian H. The goal is to estimate its energy.

Problem

The experiment implements an approximate time-evolution unitary U = e^{−iHτ}. The desired energy lies in a known interval, but the experiment must avoid phase ambiguity caused by the periodicity of e^{−iEτ}.

Analysis and approach

The team first chooses τ so that the expected energy interval maps into a phase interval shorter than one full cycle. They then use t precision qubits in QPE. If the target absolute phase resolution is ε_φ, the digital register must satisfy 2^t ≥ 1/ε_φ. The corresponding energy resolution is

provided the phase-to-energy mapping is unwrapped correctly. The experiment repeats QPE to identify the dominant peak and uses calibration data to estimate systematic phase offsets.

Outcome

The measured peak provides an energy estimate, but the final uncertainty combines finite phase resolution, imperfect controlled time evolution, state-preparation infidelity, measurement sampling, and phase wrapping. Increasing t alone may not improve the result if gate noise dominates.

Learning points

1. QPE estimates eigenphases, not arbitrary expectation values.
2. The time scale τ determines the conversion between phase and energy precision.
3. Eigenstate overlap controls the probability of observing the desired energy.
4. Algorithm design must balance precision qubits against controlled-evolution cost and noise.

9. Implementation, limitations, and best practices

Hardware limitations

QFT and QPE require coherent phase relationships. Errors in controlled rotations, crosstalk, decoherence, and readout reduce the visibility of Fourier peaks. QPE can be particularly demanding because high-precision bits require large powers U^{2^j}, which increase circuit depth or simulation time.

Iterative and semiclassical alternatives

Instead of using a large precision register, iterative phase estimation can estimate one phase bit at a time, using repeated experiments and classical feedback. Semiclassical inverse-QFT methods replace some coherent qubit interactions with measurement and feed-forward. These methods reduce qubit requirements but generally increase the number of circuit executions and require reliable classical control.

Best practices

• Define the required phase or energy error before selecting t.
• Account for bit reversal explicitly in circuit software and documentation.
• Verify controlled powers independently on small test cases.
• Use eigenstate-preparation diagnostics rather than assuming perfect overlap.
• Select τ to prevent or identify phase wrapping.
• Use approximate QFT only after estimating its effect on the target success probability.
• Repeat measurements and report confidence or uncertainty, not only the most frequent bit string.
• Validate results against classical simulation for small instances.

Governance and responsible interpretation

Quantum outputs should not be presented as exact merely because the circuit is mathematically exact. Experimental estimates need uncertainty reporting, calibration records, and reproducible circuit specifications. In applications such as chemistry or materials science, an energy estimate should be compared with a defined reference method and error tolerance. Claims of computational advantage must distinguish asymptotic algorithmic complexity from the full costs of state preparation, fault tolerance, data loading, error correction, and measurement.

Chapter Summary

The QFT is the unitary transformation F_N|x⟩ = 1/√N ∑_y e^{2πixy/N}|y⟩, with the inverse obtained by changing the sign of the exponent. An n-qubit QFT can be built from Hadamard and controlled-phase gates, with optional swaps to correct bit reversal. Its principal algorithmic value is that periodic structure and phase information become measurable frequency patterns.

QPE estimates φ when U|ψ⟩ = e^{2πiφ}|ψ⟩. Hadamard gates, controlled powers of U, and an inverse QFT convert an eigenphase into an integer close to 2^tφ. The number of precision qubits determines the digital resolution, while state preparation, controlled-unitary accuracy, sampling, and noise determine practical reliability. QFT and QPE support order finding, eigenvalue estimation, Hamiltonian simulation, and hybrid quantum–classical algorithms. Effective use requires careful treatment of phase wrapping, resource costs, approximation error, and uncertainty.

Key Terms

Quantum Fourier transform: A unitary transformation that maps computational-basis amplitudes into Fourier-basis amplitudes.

Inverse QFT: The adjoint of the QFT, implementing the reverse basis transformation.

Fourier phase: A complex phase factor of the form e^{2πixy/N} in the QFT.

Controlled-phase gate: A two-qubit gate that applies a phase rotation only when both qubits are in the control condition.

Bit reversal: The reversal of qubit order produced by the natural QFT circuit arrangement.

Approximate QFT: A QFT implementation that omits sufficiently small controlled rotations.

Eigenstate: A state |ψ⟩ that satisfies U|ψ⟩ = λ|ψ⟩ for an operator U.

Eigenvalue: The scalar λ associated with an eigenstate; for a unitary, |λ| = 1.

Eigenphase: The number φ such that a unitary eigenvalue is e^{2πiφ}.

Quantum phase estimation: An algorithm for estimating the eigenphase of a unitary operator.

Precision register: The qubit register that stores the binary estimate of a phase.

Controlled power: A controlled application of U^{2^j} in phase estimation.

Phase resolution: The smallest digital spacing represented by a phase register.

Phase wrapping: The ambiguity caused by phases being equivalent modulo one full cycle.

Periodicity: Repetition of a function or amplitude pattern at a fixed interval.

Order finding: Finding the smallest r such that a^r ≡ 1 mod N.

Continued fractions: A classical method used to recover rational approximations from measured Fourier data.

Hamiltonian simulation: The implementation of time evolution generated by a Hamiltonian.

State-preparation overlap: The squared magnitude of the component of an initial state along a target eigenstate.

Review Questions

Short Answer Questions

1. State the definition of the QFT on a computational-basis state.
2. Why are controlled-phase gates required in an exact QFT circuit?
3. What is bit reversal, and how can it be corrected?
4. What information does QPE estimate from a unitary operator?
5. Why can a superposition input to QPE produce several possible phase estimates?

Long Answer Questions

1. Explain how Hadamard and controlled-phase gates construct an n-qubit QFT, including the role of binary fractions.
2. Compare the forward QFT and inverse QFT in terms of gate order and phase signs.
3. Derive the relationship between the number of precision qubits and phase resolution in QPE.
4. Explain how periodicity produces peaks after a QFT and how this principle is used in order finding.
5. Discuss the principal practical limitations of QPE on noisy quantum hardware.

Analytical / Application Questions

1. A unitary has eigenphase φ = 3/16. Determine the minimum number of precision qubits needed to represent the phase exactly and identify the expected measurement result.
2. An energy-estimation experiment uses U = e^{−iHτ}. Explain how an inappropriate choice of τ can cause phase wrapping and propose two ways to address it.
3. A device cannot support a large coherent precision register but can execute many repeated circuits. Compare standard QPE with an iterative or semiclassical alternative for this situation.

Multiple Choice Questions with Answers

Question 1

Which expression defines the QFT of a computational-basis state |x⟩ for dimension N?

A. 1/N ∑_y e^2πixy/N|y⟩

B. 1/√N ∑_y e^2πixy/N|y⟩

C. 1/√N ∑_y e^−2πixy/N|y⟩

D. √N ∑_y e^2πixy/N|y⟩

Correct Answer: B. 1/√N ∑_y e^2πixy/N|y⟩

Question 2

Which gate is used to create the basic superposition in the standard QFT circuit?

A. Pauli-X

B. Pauli-Z

C. Hadamard

D. SWAP

Correct Answer: C. Hadamard

Question 3

What is the main purpose of final SWAP gates in a conventional QFT circuit?

A. To reverse qubit order

B. To remove all phases

C. To increase measurement probability

D. To implement controlled-U operations

Correct Answer: A. To reverse qubit order

Question 4

If a unitary satisfies U|ψ⟩ = e^2πiφ|ψ⟩, what does QPE estimate?

A. The number of qubits in |ψ⟩

B. The eigenphase φ

C. The gate depth of U

D. The amplitude of every basis state

Correct Answer: B. The eigenphase φ

Question 5

A QPE precision register has t = 3 qubits. What is its phase-grid spacing?

A. 1/3

B. 1/6

C. 1/8

D. 1/9

Correct Answer: C. 1/8

Question 6

For φ = 5/8 and t = 3, which integer is ideally measured by QPE?

A. 3

B. 4

C. 5

D. 8

Correct Answer: C. 5

Question 7

Which operation is applied immediately before measurement in standard QPE?

A. The forward QFT on the eigenstate register

B. The inverse QFT on the precision register

C. A measurement of the eigenstate register

D. A final Pauli-X on every qubit

Correct Answer: B. The inverse QFT on the precision register

Question 8

What is a principal effect of omitting small-angle rotations in an approximate QFT?

A. The circuit becomes non-unitary by definition

B. The circuit uses fewer gates with some approximation error

C. The QFT changes into a classical FFT

D. All bit reversal is automatically eliminated

Correct Answer: B. The circuit uses fewer gates with some approximation error

Question 9

In order finding, the measured Fourier value is used with which classical method to seek the period?

A. Gradient descent

B. Gaussian elimination

C. Continued fractions

D. Monte Carlo integration

Correct Answer: C. Continued fractions

Question 10

For U=e^−iHτ, an energy eigenvalue E maps to which phase relation, modulo one?

A. φ=E+τ

B. φ=Eτ/(2π)

C. φ=2πEτ

D. φ=τ/E

Correct Answer: B. φ=Eτ/(2π)