Quantum Fourier Transform in Cirq

What the QFT Does

The Quantum Fourier Transform maps computational basis states to frequency-domain states. On n qubits, it implements the unitary:

QFT|j> = (1/sqrt(N)) * sum_{k=0}^{N-1} exp(2*pi*i*j*k/N) |k>

where N = 2^n. This is the same transformation as the classical Discrete Fourier Transform, but applied directly to quantum amplitudes.

Why quantum computing needs a Fourier transform

Many quantum algorithms need to extract periodicity from a function. Shor’s algorithm factors large numbers by finding the period of a modular exponentiation function. Quantum phase estimation reads out a phase that has been encoded as a periodic pattern in qubit amplitudes. In both cases, the core computational task is the same: given a quantum state whose amplitudes encode a periodic signal, extract the frequency.

The classical Discrete Fourier Transform can find periodicities, but applying it to a quantum state would require first reading out all 2^n amplitudes. That is not possible: measuring a quantum state collapses it, yielding only a single outcome per measurement. Even with repeated state preparation, tomography of a full state vector requires exponentially many measurements.

The QFT solves this by operating directly on the quantum state. It transforms the amplitudes in-place so that the frequency information is encoded in the computational basis amplitudes themselves. After the QFT, a single measurement has a high probability of returning a value related to the period.

The exponential speedup

The classical FFT (Fast Fourier Transform) runs in O(N log N) time on N input values. When N = 2^n, that is O(n * 2^n) operations. The QFT circuit uses only O(n^2) quantum gates on n qubits to achieve the same transformation on a 2^n-dimensional state vector. This is an exponential reduction in circuit depth.

A critical caveat: the QFT itself does not give an end-to-end exponential speedup in isolation. You cannot simply load classical data into a quantum state, apply the QFT, and read out the Fourier transform. The speedup arises because the QFT operates on quantum states that were already prepared by a quantum process (like modular exponentiation in Shor’s algorithm). The QFT is a subroutine, not a standalone algorithm.

Intuition: Why Hadamard Then Controlled Phases?

The QFT circuit structure is not arbitrary. Each layer of gates has a clear physical meaning.

Hadamard creates the frequency superposition. When you apply a Hadamard gate to qubit i, you create an equal superposition of |0> and |1> on that qubit. This superposition will hold the Fourier coefficient for one “frequency bit.” Specifically, qubit i will encode the i-th bit of the frequency index k in the Fourier sum.

Controlled phase rotations encode cross-bit phase relationships. After the Hadamard on qubit i, the controlled-phase gates CZ^(1/2^k) between qubit i and qubit j accumulate the fine-grained phase that depends on the relationship between frequency bit i and input bit j. Each controlled rotation adds a phase of exp(2*pi*i / 2^k) conditioned on both qubits being |1>. This is the mechanism that ties all n bits of the input together into the correct Fourier phase.

After all rotations on qubit i, that qubit is done. Once you have applied the Hadamard and all controlled rotations targeting qubit i, that qubit holds its correct contribution to the Fourier transform. You never need to touch it again (until the final swap).

The SWAP layer corrects bit reversal. The natural output of the QFT decomposition produces the result in bit-reversed order: the most significant bit of the frequency index ends up on the last qubit, and the least significant bit ends up on the first qubit. The SWAP layer at the end puts the qubits back in the standard order. Some implementations omit the swap layer and instead account for the reversal in the classical post-processing step.

Circuit Structure

The QFT circuit on n qubits follows a systematic pattern:

1. Apply a Hadamard gate to the first qubit.
2. Apply controlled phase rotations from the first qubit to every subsequent qubit, with angles 2*pi/2^k for increasing k.
3. Repeat the pattern for each subsequent qubit (with fewer controlled rotations each time, since earlier qubits are already processed).
4. Swap the qubit order at the end (the QFT outputs in reversed bit order).

Gate count

For n qubits, the QFT circuit contains:

• n Hadamard gates (one per qubit)
• n(n-1)/2 controlled phase rotations* (qubit 0 gets n-1 rotations, qubit 1 gets n-2, and so on)
• floor(n/2) SWAP gates (to reverse the output ordering)

The total gate count is n + n*(n-1)/2 + floor(n/2), which is O(n^2). For 3 qubits, that is 3 Hadamards + 3 controlled phases + 1 SWAP = 7 gates total.

The 3-qubit QFT circuit

Here is what the 3-qubit circuit looks like when printed in Cirq:

                  ┌───────┐
0: ───H───@────────@──────────────────────×───
          │        │                      │
1: ───────@^0.5────┼─────H────@───────────┼───
                   │          │           │
2: ────────────────@^0.25─────@^0.5───H───×───
                  └───────┘

Qubit 0 gets the Hadamard first, then controlled-Z rotations with exponents 1/2 (from qubit 1) and 1/4 (from qubit 2). Qubit 1 then gets its own Hadamard and a controlled-Z rotation with exponent 1/2 from qubit 2. Finally, qubit 2 gets a Hadamard. The SWAP at the end reverses the qubit order.

Implementation in Cirq

Cirq does not bundle a specific CRk gate, but CZPowGate(exponent=2/2**k) gives the equivalent controlled phase rotation. This applies a phase of exp(i * pi * exponent) when both qubits are in |1>.

import cirq
import numpy as np

def qft_circuit(qubits):
    """Construct the QFT circuit on the given qubits."""
    n = len(qubits)
    circuit = cirq.Circuit()

    for i in range(n):
        # Hadamard on qubit i
        circuit.append(cirq.H(qubits[i]))

        # Controlled phase rotations
        for j in range(i + 1, n):
            k = j - i + 1
            # CZPowGate with exponent 2/2^k gives phase exp(i*pi*2/2^k) = exp(2*pi*i/2^k)
            circuit.append(cirq.CZPowGate(exponent=2 / 2**k)(qubits[i], qubits[j]))

    # Swap qubits to correct output ordering
    for i in range(n // 2):
        circuit.append(cirq.SWAP(qubits[i], qubits[n - 1 - i]))

    return circuit

# Build 3-qubit QFT
qubits = cirq.LineQubit.range(3)
qft = qft_circuit(qubits)
print(qft)

Verifying Against the DFT Matrix

We can extract the unitary matrix of our circuit and compare it to the theoretical DFT matrix. For n qubits, the DFT matrix is:

F[j,k] = (1/sqrt(N)) * exp(2*pi*i*j*k/N)

simulator = cirq.Simulator()
result = simulator.simulate(qft)

# Extract the circuit's unitary
unitary = cirq.unitary(qft)

# Build the 3-qubit DFT matrix
N = 2**3
dft_matrix = np.array([[np.exp(2j * np.pi * j * k / N) / np.sqrt(N)
                         for k in range(N)] for j in range(N)])

# Compare
if np.allclose(unitary, dft_matrix, atol=1e-10):
    print("Circuit unitary matches the DFT matrix.")
else:
    print("Mismatch detected.")
    print(f"Max difference: {np.max(np.abs(unitary - dft_matrix)):.2e}")

Testing with a Specific Input State

Let’s apply the QFT to the state |5> (binary 101) and check the output amplitudes.

# Prepare |5> = |101> on 3 qubits
# In Cirq's little-endian convention, qubit 0 is LSB
# |5> = |101> means qubit 0 = 1, qubit 1 = 0, qubit 2 = 1
prep = cirq.Circuit([cirq.X(qubits[0]), cirq.X(qubits[2])])
full_circuit = prep + qft

result = simulator.simulate(full_circuit)
state = result.final_state_vector

print("Output amplitudes after QFT|5>:")
for i, amp in enumerate(state):
    phase = np.angle(amp) / np.pi
    print(f"  |{i}> : magnitude={np.abs(amp):.4f}, phase={phase:.4f}*pi")

What Do the Output Amplitudes Mean?

The QFT of a computational basis state produces a uniform-magnitude state where only the phases vary. Each amplitude should have magnitude 1/sqrt(8) with phases that are multiples of 2pi5/8.

Let’s break down what this means concretely.

Uniform magnitude means every basis state is equally likely. If you measure the output of QFT|5> in the computational basis, each of the 8 possible outcomes (|0> through |7>) has equal probability 1/8. The measurement outcome alone does not tell you anything about the input. This is expected: a single computational basis state has a single well-defined frequency, and the QFT of a pure frequency spreads uniformly across all positions (just like a classical Fourier transform of a complex exponential produces a single delta function, but viewed from the dual domain, a delta function transforms into a uniform distribution of phases).

The phases encode the input. The amplitude of the |k> component is (1/sqrt(8)) * exp(2pii5k/8). The “5” from the input state appears directly in the phase progression. For k=0, the phase is 0. For k=1, the phase is 2pi5/8. For k=2, the phase is 2pi10/8, and so on. The rate at which the phase advances with k is proportional to the input value.

To extract the input, you use the inverse QFT. Since the QFT is unitary, it has a well-defined inverse. Applying QFT^(-1) to the output recovers the original |5> state. This is exactly the pattern used in quantum phase estimation (QPE): the phase kickback step encodes a phase into the amplitudes of the ancilla register, and then the inverse QFT converts those phases back into a computational basis state that can be measured directly.

In Shor’s algorithm, continued fractions finish the job. After the QFT step in Shor’s order-finding subroutine, you measure the output register and obtain a value close to a multiple of N/r, where r is the period you want to find. You then use the classical continued fractions algorithm to extract r from the measurement outcome. The QFT is what concentrates the measurement probabilities near these multiples of N/r.

Running on a Simulator

The statevector simulation above gives full access to amplitudes, which is useful for verification. In practice (and on real hardware), you only get measurement outcomes. Here is how to run the QFT with measurements and interpret the results.

# Add measurements to the circuit
measured_circuit = full_circuit + cirq.measure(*qubits, key='result')

# Run 10000 shots
sampler = cirq.Simulator()
samples = sampler.run(measured_circuit, repetitions=10000)

# Print the measurement histogram
histogram = samples.histogram(key='result')
print("Measurement results after QFT|5>:")
for state_val in sorted(histogram.keys()):
    count = histogram[state_val]
    binary = format(state_val, '03b')
    print(f"  |{binary}> ({state_val}): {count} counts ({count/100:.1f}%)")

Because QFT|5> produces a uniform superposition (all magnitudes equal), the histogram shows roughly equal counts for every basis state. Each outcome appears about 1250 times out of 10000 shots. The phases, which carry all the information about the input, are invisible to computational basis measurement.

This is why the QFT is always used as a subroutine inside a larger algorithm, never as a standalone operation. The surrounding algorithm structure (phase kickback in QPE, modular exponentiation in Shor’s) arranges things so that the QFT output has non-uniform magnitudes, concentrating probability on the basis states that encode the answer.

To see a non-trivial measurement distribution, you would need to apply the QFT to a state with periodicity in its amplitudes, not a single basis state. For example, if the input state had equal amplitudes on |0>, |2>, |4>, and |6> (period 2), the QFT output would concentrate probability on |0> and |4> (frequency = N/period = 8/2 = 4).

Common Mistakes

Building the QFT from scratch involves several easy-to-miss details. Here are the most common pitfalls.

Off-by-one in the phase exponent

The controlled rotation between qubit i and qubit j (where j > i) should use exponent 2/2**k where k = j - i + 1. A common mistake is using 1/2**k instead, which produces a phase that is off by a factor of 2. This happens because CZPowGate(exponent=e) applies a phase of exp(i * pi * e), not exp(2 * pi * i * e). The factor-of-2 convention in Cirq’s exponent parameterization trips up many people.

# CORRECT: exponent = 2/2^k
cirq.CZPowGate(exponent=2 / 2**k)  # phase = exp(i*pi*2/2^k) = exp(2*pi*i/2^k)

# WRONG: exponent = 1/2^k
cirq.CZPowGate(exponent=1 / 2**k)  # phase = exp(i*pi/2^k) -- half the intended angle

Forgetting the SWAP layer

Without the final SWAP gates, the QFT output is in bit-reversed order. The unitary will not match the standard DFT matrix, and any algorithm that depends on the QFT output being in normal order will produce wrong results. If you intentionally omit the SWAPs for efficiency (some implementations do this), you must account for the reversal in all subsequent operations.

Confusing CZPowGate with CXPowGate

CZPowGate applies a phase when both qubits are |1>. CXPowGate performs a controlled rotation around the X axis, which is a completely different operation. The QFT requires controlled phase gates, not controlled-X rotations.

# CORRECT: controlled phase
cirq.CZPowGate(exponent=2 / 2**k)

# WRONG: controlled X-rotation (different unitary entirely)
cirq.CXPowGate(exponent=2 / 2**k)

Qubit ordering conventions

Cirq’s LineQubit(0) is typically treated as the most significant qubit when you interpret the state vector, but this is a convention, not a rule. The Cirq simulator orders the state vector with LineQubit(0) as the most significant bit: the state |abc> corresponds to LineQubit(0)=a, LineQubit(1)=b, LineQubit(2)=c. If your convention differs, the SWAP layer and state preparation will need to be adjusted. Document your convention explicitly when writing QFT code.

Syntax Comparison with Qiskit

In Qiskit, the QFT is available as a library function. The main syntactic difference is how controlled phase gates are expressed:

# Qiskit equivalent (for comparison, not runnable in Cirq)
# from qiskit.circuit.library import QFT
# qft_qiskit = QFT(3)
#
# Qiskit uses cp(theta) for controlled phase:
#   circuit.cp(2*pi/2**k, control, target)
#
# Cirq uses CZPowGate(exponent=...):
#   cirq.CZPowGate(exponent=2/2**k)(control, target)
#
# Both produce identical unitaries. Cirq parameterizes by
# "turns" (fractions of a full rotation), while Qiskit
# uses radians directly.

Where QFT Appears in Real Algorithms

The QFT is a building block in several major quantum algorithms. Here is a brief overview of the role it plays in each.

Quantum Phase Estimation (QPE). QPE uses the inverse QFT as its final step. The phase kickback trick encodes an eigenvalue phase into the amplitudes of an ancilla register as a periodic pattern, and the inverse QFT converts that pattern into a binary representation of the phase that can be read out by measurement.

Shor’s Algorithm. The order-finding subroutine in Shor’s algorithm applies the QFT to extract the period of a modular exponentiation function. After the QFT, measurement yields a value close to a multiple of N/r, and the continued fractions algorithm recovers the period r. Factoring then reduces to computing GCD(a^(r/2) +/- 1, N).

HHL Algorithm (Harrow-Hasidim-Lloyd). HHL solves linear systems of equations Ax = b on a quantum computer. It uses QPE (which contains an inverse QFT) to decompose the input vector in the eigenbasis of A, then performs a conditional rotation to encode the eigenvalue inverses, and finally uses the QFT (within a second QPE step) to undo the decomposition.

Key Takeaways

• The QFT circuit uses O(n^2) gates for n qubits, giving an exponential speedup over the classical FFT’s O(N log N) on N = 2^n values.
• The speedup matters because the QFT operates on quantum states that already exist in superposition, avoiding the need to read out exponentially many amplitudes.
• Each layer of the QFT has a clear purpose: Hadamards create frequency superpositions, controlled phases encode cross-bit relationships, and SWAPs fix the bit ordering.
• Cirq’s CZPowGate is the natural building block for the controlled phase rotations in the QFT. Remember the factor-of-2 convention: use exponent=2/2**k, not 1/2**k.
• The swap layer at the end corrects for the reversed bit ordering inherent in the QFT decomposition.
• The QFT of a single basis state produces uniform measurement probabilities. The QFT becomes useful inside larger algorithms where the input state has periodic structure.
• Verifying the unitary against the DFT matrix is a useful sanity check when building custom algorithm circuits.