Sumários
week 11 - The adversary method and HSP
13 Maio 2024, 16:30 • André Souto
Presentation of techniques to prove lower bounds for quantum query complexity.
Focus on the adversary method technique: motivation, idea, proof sketch and examples.
The hidden subgroup problem. Definition, motivation and description of other problems previously mentioned as HSP. The QFT for a generic group, and the solution for HSP.
Week 10 - Grover search algorithm
6 Maio 2024, 16:30 • André Souto
Recap of Shor's algorithm. Another example.
Grover search: motivation, use, considerations, presentation, discussion of why it works and proof of the bounds.
Examples.
Week 9 - Breaking RSA with Shor's algorithmQuantum Fourier Transformation and phase estimation
29 Abril 2024, 16:30 • André Souto
History of Shor's algorithm.
Discrete log and RSA as motivations for Period Finding algorithm.
Period finding algorithm: easy case and hard case (continued fractions).
Shor's algorithm for breaking RSA.
Examples.