L20 Quantum Fourier Transform II
Watch on YouTube →
Overview
Hiu-Yung Wong derives the Quantum Fourier Transform (QFT) matrix from roots of unity and proves it is unitary by showing its columns have unit norm and are mutually orthogonal. He then relates the inverse QFT to complex conjugation and transpose, works through one- and two-qubit examples, and builds the circuit from Hadamard gates, controlled phase shifts, and swaps, ending with the pattern for an n-qubit QFT.
Key takeaways
- The QFT matrix with entries ω^(-kj)/√n is unitary because its column inner products reduce to a roots-of-unity sum: equal columns give 1, and distinct columns give 0.
- The inverse QFT is the conjugate transpose of the forward QFT, so under Wong's convention its entries use positive rather than negative exponents.
- For one qubit, the QFT is exactly the Hadamard matrix; for two qubits, the transform also requires a controlled phase shift and a final swap.
- An n-qubit bit-reversal operation is implemented with floor(n/2) pairwise swaps, leaving the center qubit unchanged when n is odd.
- The general QFT circuit applies Hadamards, then controlled phase shifts whose angles follow powers-of-two denominators, and finally reverses the qubit order.
Chapters
- Defines an n-dimensional QFT matrix using the root of unity ω = e^(i2π/n), with entry (k,j) equal to ω^(-kj)/√n.
- Frames unitarity as U†U = UU† = I and proposes proving it by checking that every pair of columns is orthonormal.
- A column indexed by a contains entries proportional to 1, ω^(-a), through ω^(-(n-1)a).
- Uses Euler's formula, e^(iθ) = cos θ + i sin θ, to show that complex conjugation changes e^(iθ) into e^(-iθ).
- Consequently, the conjugate of ω^(-kj) is ω^(kj), which supplies the sign change needed when forming U†.
- The derivation connects the matrix proof to the geometric behavior of complex phases on the unit circle.
- Computes the inner product of columns a and b as (1/n) times the sum of ω^(j(a-b)) over j = 0 to n-1.
- When a = b, all n terms equal 1, so the inner product is n/n = 1.
- When a ≠ b, the roots-of-unity sum cancels to zero, establishing orthogonality and proving the QFT is unitary.
- Because the QFT is unitary, its inverse equals its conjugate transpose: U⁻¹ = U†.
- Transposition swaps row and column indices, while complex conjugation reverses the sign of the exponent.
- Under Wong's convention, the inverse QFT has entries ω^(kj)/√n, differing from the forward QFT only in the exponent sign.
- Some references label the positive-exponent matrix as the QFT, while Wong uses the negative-exponent matrix as the QFT.
- The two naming conventions describe the same pair of forward and inverse transforms with their labels exchanged.
- For algorithms such as Shor's, check the author's exponent convention rather than relying on the transform's name alone.
- A one-qubit system has n = 2 computational basis states, so its QFT is a 2×2 matrix.
- Using ω = e^(iπ) = -1 gives the normalized matrix 1/√2 [[1, 1], [1, -1]].
- This matrix is the Hadamard gate, but Wong cautions that the two-qubit QFT is not simply two Hadamard gates applied by a tensor product.
- For two qubits, n = 2² = 4 and ω = e^(iπ/2) = i, producing four roots of unity: 1, i, -1, and -i.
- The first row and first column contain only 1s because one of their indices is zero.
- Entries in each column follow repeated powers of ω raised to the negative column index, yielding the periodic phase pattern in the 4×4 matrix.
- Defines an n-qubit reversal operation that maps |x₀x₁…xₙ₋₁⟩ to |xₙ₋₁…x₁x₀⟩.
- For four qubits, the transformation is |x₀x₁x₂x₃⟩ → |x₃x₂x₁x₀⟩.
- Implements the reversal with pairwise swaps: swap the outer qubits, then the next inner pair, continuing toward the center.
- For five qubits, reversal swaps positions 0 and 4, then 1 and 3, while the middle qubit remains unchanged.
- A sample basis input |10100⟩ becomes |00101⟩ after reversing the bit order.
- Wong distinguishes a swap-gate symbol from mere rewiring and notes that IBM Quantum diagrams may show each two-qubit swap explicitly.
- The two-qubit QFT circuit combines Hadamard gates, a controlled phase-shift gate, and a final swap.
- The controlled phase angle is derived from the four-dimensional transform, with a magnitude of 2π/4 and a sign determined by the chosen QFT convention.
- A controlled phase shift acts only when both qubits are |1⟩, so its matrix is diagonal and changes the phase of the |11⟩ basis state.
- Relates a single-qubit phase shift to a diagonal gate of the form diag(1, e^(iθ)); for n = 4, the phase factor is a fourth root of unity.
- Introduces S and T gates as commonly used phase gates, with T described as a square root of S under the conventional gate definitions.
- Explains that fault-tolerant architectures commonly require resource-intensive T-state distillation, motivating the use of T factories.
- Writes the circuit as a product of the swap, Hadamard, identity, and controlled-phase matrices, respecting right-to-left operator order.
- Uses tensor products such as I ⊗ H to construct 4×4 matrices from 2×2 single-qubit gates.
- Shows how row-by-column multiplication combines or subtracts matrix rows according to the Hadamard coefficients, recovering the two-qubit QFT matrix.
- Begins with a Hadamard gate on each qubit and ends with an n-qubit bit-reversal operation built from swaps.
- Each qubit receives controlled phase shifts from the lower-significance qubits; a qubit farther from a control receives a smaller rotation.
- The controlled rotations follow powers-of-two denominators, corresponding to factors such as e^(-i2π/2ᵈ) for separation d, with the sign tied to the selected QFT convention.
- A qubit with one lower-significance control receives one controlled rotation, while a qubit with two such controls receives two rotations.
- The final qubit in the sequence can receive controlled rotations from all n − 1 lower-significance qubits.
- Wong corrects an exponent slip during the derivation and emphasizes recognizing the repeated Hadamard, controlled-phase, and swap structure rather than memorizing a faulty index.
Transcript excerpt
0:07 Last time I was a little bit slow and then we left on uh this page. I decided to redo it so that uh as a refresh instead of just try to finish it, finish the rest. Right? So we want to prove that the quantum feria transform matrix the gate is unitary. Right? And we recall that what is unitary? We say uh u it means that u da u super slow okay equals to u u dagger equals to 1. Okay now we can prove this that is some of what you some of you did in uh the exam but my suggested solution for you was remember I say that you can also prove that every column
0:59 right is of remember right. So what does it mean? For example, what is the content of column A? Column A is just a vector, right? Do you still remember how to construct the quantum fer transform matrix? What is the most important Greek character? >> Yes. And that is omega, right? Very
1:47 good. So she said that the most important one is omega equals to e to the power i 2 pi cy n right and that's the nth roots of unity right so how do you construct the matrix again you have omega and then how you fill in the matrix no you fill in the matrix so for example what is elements the element on i row and J column >> omega to the power. >> Yes. Minus I J. Right. So just remind
2:37 you u qf right is just 1 / square n and then omega to power minus let me call it kj right for the k row and j column remember right so you should you should memorize this right so what is the uh the vector or what is the
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Quantum Computing, TCAD, Semicond by Hiu-Yung Wong.