L19 Nth root of Unity and Quantum Fourier Transform

Overview

Hiu-Yung Wong reviews the Nth roots of unity, defining ω = e^(i2π/N) and using geometric-series sums to explain when complex phases cancel or reinforce. He then builds the normalized discrete Fourier transform (DFT), shows how its matrix uses powers of ω, and introduces the quantum Fourier transform (QFT) as a quantum gate whose unitarity follows from orthogonality of its columns.

Key takeaways

For ω = e^(i2π/N), the N roots of unity are ω^k for k = 0, …, N−1, and ω^N = 1.
The complete root sum Σₖω^k is zero because it is a geometric series with numerator 1 − ω^N = 0.
More generally, Σₖω^(kℓ) equals N when ℓ = 0 and cancels to zero for nonzero ℓ within the nonrepeating index range.
The normalized DFT uses matrix entries (1/√N)ω^(−kj), combining every input component with an index-dependent complex phase.
A uniform normalized N-component vector transforms to a vector with y₀ = 1 and all other outputs zero, demonstrating phase cancellation in the DFT.
The QFT's unitarity can be established by showing its columns are orthonormal, with the root-of-unity sum providing the required cancellation.

Chapters

0:00 Nth Roots of Unity: Solving x^N = 1

The equation x^N = 1 has N complex roots, not just the real value 1.
The roots are e^(i2πk/N), with integer k ranging from 0 to N−1.
For N = 2, the roots are 1 and −1; for N = 4, complex roots are also required.

3:30 Euler's Formula and the Four Roots for N = 4

Euler's formula, e^(iθ) = cos θ + i sin θ, converts the N = 4 roots into 1, i, −1, and −i.
The special case e^(iπ) = −1 gives Euler's identity e^(iπ) + 1 = 0.
The four roots correspond to points spaced 90 degrees apart on the unit circle.

9:00 Root Spacing on the Unit Circle and the Definition of ω

Increasing N divides the full 2π rotation into N equal angular steps.
The notation ω = e^(i2π/N) names the first root after 1 and depends on the chosen N.
All roots can be written compactly as 1, ω, ω², …, ω^(N−1).

12:00 Verifying the Root Property ω^N = 1

Raising ω = e^(i2π/N) to the Nth power gives e^(i2π) = 1.
Therefore each listed power ω^k is an Nth root of unity.
The index range from 0 through N−1 supplies exactly N roots.

15:20 Summing All Nth Roots with a Geometric Series

The sum 1 + ω + ω² + … + ω^(N−1) is a geometric series with ratio ω.
Its value is (1 − ω^N)/(1 − ω), which equals zero because ω^N = 1 and ω ≠ 1.
On the unit circle, the zero sum represents cancellation among the complex root vectors, whether N is even or odd.

22:00 Powers of Roots Produce Constructive or Destructive Interference

For integer ℓ, the sum Σ from k = 0 to N−1 of ω^(kℓ) is another geometric series.
When ℓ is nonzero in the relevant range, the phases cancel and the sum is zero.
When ℓ = 0, every term is 1, so the sum is N, a constructive-interference case used later in quantum algorithms.

30:00 The Last Root Is the Inverse Phase ω⁻¹

The final listed root, ω^(N−1), equals ω^(-1) because ω^N = 1.
Positive powers of ω rotate counterclockwise around the unit circle; ω⁻¹ represents one step in the opposite direction.
This identity and the root-sum properties provide tools for analyzing Fourier transforms.

35:54 Representing the Discrete Fourier Transform as a Vector Map

The classical DFT maps an N-component input vector x = (x₀, …, xₙ₋₁) to an N-component output vector y.
Each output yₖ combines contributions from every input component xⱼ.
The transform applies a phase weight based on both indices, using powers of the Nth root of unity.

39:00 DFT Phase Weights and 1/√N Normalization

The lecture writes the normalized DFT as yₖ = (1/√N) Σⱼ xⱼω^(−jk).
The factor 1/√N keeps the transform normalized rather than allowing the summed components to grow with N.
The phase ω^(−jk) makes each input's contribution depend on its position j and the output index k.

43:45 The DFT Matrix: Powers of ω by Row and Column

In matrix form, the DFT entry at row k and column j is (1/√N)ω^(−kj).
The first row and first column contain powers with exponent zero, so their entries are all 1/√N.
Multiplying the DFT matrix by x reproduces the weighted sum for each output component yₖ.

48:28 A Uniform Input Transforms to a Single Nonzero Component

For x = (1/√N)(1, 1, …, 1), the zero-frequency output y₀ equals 1.
For every k ≠ 0, the output is a sum of nontrivial powers of ω and vanishes by the root-of-unity cancellation property.
The result is (1, 0, …, 0), illustrating how a DFT concentrates a uniform vector into one component.

55:45 Defining the Quantum Fourier Transform on Basis States

A quantum gate is specified by its action on basis states, which determines its action on superpositions by linearity.
The QFT maps a basis state |j⟩ to a normalized superposition of all N basis states with phase weights built from powers of ω.
The lecture connects the QFT's phase-weighted matrix structure to the classical DFT, while using the transform in a quantum state space.

58:00 QFT Matrix Entries and Checking the Basis-State Action

The QFT matrix is presented with entries formed from powers of ω and an overall 1/√N factor.
To verify a matrix element, the calculation applies the operator to a basis vector and takes its inner product with another basis vector.
Orthogonality makes the inner product vanish except when the relevant basis indices match, selecting the corresponding phase term.

1:07:00 QFT Unitarity from Orthogonal Columns

A quantum gate must be unitary, meaning U†U = I; equivalently, its columns must be orthonormal.
Each QFT column contains powers of ω scaled by 1/√N, and the column inner products reduce to root-of-unity sums.
Complex conjugation reverses the phase sign, allowing the column products to be evaluated using the earlier cancellation result; the detailed proof continues in the next class.

Transcript excerpt

0:07 The first thing we want to review is the so-cal nth root of unity. So what is this? Basically, the question is to ask what is um x for x to the power n = 1, right? This one, maybe if is a kindergartner or elementary school student, then they will say one; one to the power of n is one, right? But if we look, look at it carefully, we will find that it's not that simple. And if have if you have learned about complex lumber and those analysis, you'll find that it is pretty complicated. First,

0:57 what if n= to two? What is x? Then it basically asks x² = 1. So what are the possible value of x? +-one right x = 1 or -1 what if n = 4? The question is x to the power four power of 4 equals to 1. What can be the value of x? >> Okay, continue. Plus minus one. And then someone say what? I

1:45 what else? >> Minus R. So indeed you do have four roots. Okay. All right. So basically you have when in general x n = to one it has n root here has n roots. Okay. So what are they? Right. So we are not going to prove them. We will just assume you learned them before. But if you forgot, you need to me memorize it now. X equals to E to the power

2:33 I 2 pi / by N and then times K in the exponential in the exponent where K equals to 0 1 2 3 all the way to N minus one. This is the root. All these take to the power n will give you one. They are the roots of x to the power n = 1.

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.