Day 593: Simon's Algorithm Introduction

Learning Objectives

• •Define Simon's problem (hidden period/subgroup)
• •Prove the classical $\Omega(2^{n/2})$ lower bound
• •Derive the quantum algorithm's $O(n)$ query complexity
• •Understand the classical post-processing (linear algebra over $\mathbb{Z}_2$)
• •Recognize the connection to period-finding and Shor's algorithm
• •Implement Simon's algorithm computationally

Today's Schedule (7 hours)