L21 QFT, Quantum Phase Estimation, Shor's Algorithm
Watch on YouTube →
Overview
Hiu-Yung Wong connects the Quantum Fourier Transform (QFT) to Quantum Phase Estimation (QPE), showing how controlled phase gates and inverse QFT recover the phase of a unitary eigenvalue. He then introduces Shor's algorithm as a way to factor integers by finding the period of modular exponentiation, using N = 21 and a = 11 to demonstrate a period of 6 and explain the implications for RSA and post-quantum cryptography.
Key takeaways
- For an n-qubit QFT, controlled phase rotations use powers of an Nth root of unity with N = 2^n, and final swaps reverse the qubit order.
- QFT sign conventions vary across textbooks, so identify whether the matrix uses ω^(kj) or ω^(-kj) before interpreting a circuit.
- QPE estimates the phase φ of a unitary eigenvalue e^(2πiφ); n control qubits encode an integer approximation to 2^nφ.
- Shor's algorithm reduces factoring N to finding the period of f(x) = a^x mod N, then uses classical greatest-common-divisor calculations to recover factors.
- For N = 21 and a = 11, the modular sequence has period 6, and gcd(11^3 − 1, 21) and gcd(11^3 + 1, 21) yield the factors 7 and 3.
- Harvest-now, decrypt-later makes post-quantum cryptography relevant before large quantum computers exist, because encrypted data can be stored for future attacks.
Chapters
- The n-qubit QFT applies Hadamard gates and controlled phase shifts, followed by swaps that reverse bit order.
- Each controlled phase shift uses powers of an Nth root of unity, with N = 2^n.
- For each target qubit, the number and angles of controlled rotations depend on the less significant qubits.
- The IBM-style three-qubit circuit labels Q0 as least significant and Q2 as most significant.
- The circuit has Hadamard gates, controlled rotations with angles π/2 and π/4, and a final swap of Q0 and Q2.
- Q1 does not need to be swapped, so the three-qubit reversal effectively uses a two-qubit swap.
- The QFT maps the three-qubit basis state |000⟩ to an equal superposition of all eight computational basis states.
- Each output amplitude is 1/√8, giving each of the eight measurement results probability 1/8.
- The equal-amplitude result is compared with the Fourier-transform relationship between an impulse and a constant spectrum.
- Hiu-Yung Wong defines the QFT matrix elements using ω^(-kj), where ω is an Nth root of unity.
- Some textbooks use the opposite sign and call that transform the QFT, so the sign convention must be checked in equations or circuit definitions.
- The lecture's convention follows the discrete Fourier transform formula directly.
- A QFT circuit contains a number of controlled rotations that grows with the qubit count, alongside Hadamard and swap operations.
- The lecture distinguishes total gate count from circuit depth, since disjoint gates may execute in parallel.
- The transform is described as a change of basis whose interference can concentrate information into spectral peaks.
- A unitary operator has eigenvalues with magnitude 1, expressible as e^(iθ) or e^(2πiφ).
- QPE estimates the phase φ associated with an eigenvalue rather than measuring the complex eigenvalue directly.
- The phase representation makes the target a number between 0 and 1, modulo whole rotations.
- The Pauli-Z gate has eigenvalues +1 and -1, corresponding to phases 0 and 1/2 under the e^(2πiφ) convention.
- The QPE example uses two control qubits, Hadamard gates, controlled applications of Z, and an inverse QFT.
- The input eigenstate determines which of Z's two eigenphases the control register encodes.
- QPE applies controlled powers U^(2^j), including U and U² in the two-control-qubit example.
- For the |1⟩ eigenstate of Z, the measured control bits are 10, representing 2 out of 2² and therefore phase 1/2.
- Adding control qubits increases phase resolution because the measurement represents an integer approximation to 2^nφ.
- Phase kickback transfers the eigenphase information into the control register for measurement.
- An n-qubit QPE register begins in |0⟩ states and receives Hadamard gates to create a superposition.
- The controlled operations progress through powers of U from U^(2^0) to U^(2^(n-1)).
- An inverse QFT converts the accumulated phase into a measurable binary estimate.
- RSA security is tied to the difficulty of factoring a large composite modulus N = pq when only N is public.
- Multiplying known primes p and q is straightforward, while recovering them from a sufficiently large N is computationally difficult for classical methods.
- The example N = 21 = 3 × 7 illustrates the factoring task on a small scale.
- Shor's algorithm uses quantum period finding to obtain information that can be converted into factors of N.
- The algorithm combines Hadamard gates, a modular-arithmetic oracle, QFT-based interference, and classical post-processing.
- A quantum run can return an unhelpful measurement, so candidate factors are checked classically and the circuit can be run again.
- Post-quantum cryptography aims to replace schemes whose security relies on factoring, using other mathematical problems such as lattice-based methods or hash functions.
- The NIST standardization effort is presented as a route to selecting quantum-resistant cryptographic algorithms.
- Harvest-now, decrypt-later describes attackers storing encrypted data today in hopes of decrypting it with future quantum computers.
- Shor's reduction studies f(x) = a^x mod N, where N is the integer to factor and a is a chosen integer.
- The modular operation returns the remainder after dividing a^x by N; for example, 16 mod 6 = 4.
- Finding the period r of this function can enable classical post-processing to recover nontrivial factors of N.
- With N = 21 and a = 11, the modular sequence for x = 0 through 6 is 1, 11, 16, 8, 4, 2, 1.
- The first repeated value occurs at x = 6, establishing period r = 6 for 11^x mod 21.
- Because r is even, classical post-processing uses 11^(r/2) mod 21 = 8; gcd(8 − 1, 21) = 7 and gcd(8 + 1, 21) = 3.
- The example shows how quantum period finding can supply the key step, while classical arithmetic extracts the factors 3 and 7.
Transcript excerpt
0:07 to what it look like. You have n cubits from LSP to MSP. Each of them will get a harajama gate like this. And at the end you have a swap gate, n cubit swap gate. And what is so special is that for each of these cubits you will receive a control phase shift gate for the less significant cubit. For example, the second cubit will receive this control phase shift gate. The third cubit will receive one from the least significant, one from the next least significant uh cubit and they all phase shift gate control phase shift. And what is the angle they try to shift?
0:58 If you look at it, it actually is easy to understand. It is omega, the n root of unity. And this omega of course depends on what is the capital n. Now you can think in this way here. This one control this one. So you have 2 cubits. So it's n = 4 2 power two. Right? So you receive a -2 pi / 2 ^ 2. This one is the first cubit. You include you get entangle right? Or you have control it with another two cubit. So it is three cubit system. Capital n is three uh is 8 to the^ 8 to ^ 3 which is 8 and you will receive two one is -2i / n and
1:47 other is -2i / n * 2 okay so for the last one naturally you can expect I'm going to do the phase shift of the n fluid of unity of 2 to power n cubit because it's and handle mine throughout the whole system right and I am going to receive the control facility from each of the less silicon cubit from me so there are n minus one of them right so naturally
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.