Period-Finding (Simon's Algorithm over Z_N): Lecture 15 of Quantum Computation at CMU

Item: Period-Finding (Simon's Algorithm over Z_N): Lecture 15 of Quantum Computation at CMU
Rating: 5
Author: PostSingularity Institute

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYXNatural computing

🎙 Ryan O'Donnell 👥 14K 📅 October 30, 2018 ⏱ 82 min 👁 3K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

period-findingSimon's algorithmquantum Fourier transformShor's algorithmhidden subgroup problem

Summary

This lecture, part of a quantum computation course at CMU, covers the period-finding problem, which is a generalization of Simon’s algorithm over the integers modulo N. The instructor, Ryan O’Donnell, begins by setting up the problem: given a function f that is L-periodic (with L dividing N), the goal is to determine L. He notes the classical difficulty is mitigated when N is not a power of two, but the quantum algorithm works for any N and even when L does not perfectly divide N, which is crucial for Shor’s factoring algorithm. The algorithm follows the quantum Fourier sampling paradigm: prepare a superposition of inputs, apply the function, measure the output register to collapse to a coset of the period, then apply the quantum Fourier transform and measure. The measurement yields a random multiple of N/L, from which L can be deduced. The lecture includes a proof that the measurement probabilities are independent of the specific color measured, simplifying the analysis. The instructor emphasizes that this is the key quantum component of Shor’s algorithm, with the rest being classical number theory. The lecture is technical and assumes prior knowledge of quantum circuits and the Fourier transform.

196 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a thorough and rigorous explanation of the period-finding algorithm, building on previous lectures on Simon’s algorithm and the quantum Fourier transform. The argumentation is solid, with clear derivations and proofs, such as the lemma showing that Fourier coefficients are invariant under translation up to a phase. The instructor also addresses potential issues, such as the classical hardness when N is a power of two, and explains how the algorithm extends to more general cases. The value lies in its direct relevance to Shor’s algorithm, making it a cornerstone for understanding quantum factoring.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with precise mathematical definitions and proofs. The instructor references Shor’s original work and the course materials, but no external sources are cited in the video itself. The title accurately reflects the content, focusing on period-finding as a generalization of Simon’s algorithm. The lecture is part of a formal course, ensuring academic quality. No comments were provided for analysis.

173 words

Title / Content Match

The title accurately describes the lecture content, which focuses on period-finding as a generalization of Simon's algorithm over Z_N.

Quality & Reliability

9/10

Lecture by a renowned professor at CMU, part of a formal course, with rigorous mathematical derivations and references to Shor's algorithm. The content is well-structured and technically accurate.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Course website — Course materials and lecture notes.
Diderot discussion board — Course discussion platform.
Panopto — Video recording service.

Concurring Sources

Shor's algorithm - Wikipedia — General reference for Shor's algorithm and period-finding.
Quantum Fourier transform - Wikipedia — Reference for the quantum Fourier transform used in the algorithm.

Contribution & Novelties

This lecture provides a clear and rigorous exposition of the period-finding algorithm, which is a key component of Shor’s factoring algorithm. It builds on Simon’s algorithm and generalizes it to the integers modulo N, highlighting the importance of the quantum Fourier transform. The lecture also addresses practical issues such as the case when the period does not perfectly divide N, which is essential for Shor’s algorithm.

Pour aller plus loin :

Shor’s algorithm — Overview of the factoring algorithm that uses period-finding.
Quantum Fourier transform — The quantum version of the discrete Fourier transform used in the algorithm.
Hidden subgroup problem — General framework that includes period-finding and Simon’s problem.

110 words

Radar Profile

The radar profile shows high scores across all dimensions, indicating a technically deep and reliable lecture. The balance between information quantity, quality, and technical level is excellent, making it a valuable resource for advanced learners.

Reliability 9/10