Simon's Algorithm | Exponential Speedup & Precursor to Shor
Quick Technical Answer:
Simon's algorithm finds a hidden period s for a 2-to-1 function f(x) = f(y) ⇔ x ⊕ y ∈ {0^n, s} in O(n) quantum queries, providing an exponential speedup over classical algorithms that require O(2^{n/2}) queries.
Formula / Unitary:
f(x) = f(y) \iff y = x \oplus s, \quad s \cdot y = 0 \pmod 2
Simulate this in Itachi Quantum Studio
Inspect state amplitudes, 3D Bloch sphere vector, and OpenQASM code live.
Frequently Asked Questions
Why did Simon's algorithm inspire Peter Shor?
Simon's use of quantum interference to extract a hidden period in an abelian group (Z_2^n) inspired Peter Shor to formulate order-finding over modular integers (Z_N^*).